Skip to main content

Questions tagged [computability]

Questions about Turing computability and recursion theory, including the halting problem and other unsolvable problems. Questions about the resources required to solving particular problems should be tagged (computational-complexity).

Filter by
Sorted by
Tagged with
-3 votes
0 answers
42 views

On existence / computability of mathematical objects like √2 [closed]

numbers like √2 or 1/9 are mathematical objects but they are abstract concepts (because we could not calculate them). It is not a natural nubmer but rather an infinite sequence of fraction digits. ...
spsy's user avatar
  • 95
2 votes
1 answer
90 views

$\omega$-consistency in Goedel's completeness

To prove $PA\not\vdash \lnot \Delta$, where $\Delta$ is the Goedel's sentence, satisfying: $$PA\vdash \Delta\leftrightarrow \lnot Prv(\overline{\Delta})$$ Why cannot we say: If $PA\vdash \lnot \Delta$,...
Y.X.'s user avatar
  • 4,223
3 votes
1 answer
64 views

Is there a function $f :A^{<\mathbb{N}}\to E$ such that $f (s{}^\frown a)=h(f(s),a,|s|)$ for any $s\in A^{<\mathbb{N}}$ and $a\in A$?

Given a set $A$, define $A^{<\mathbb{N}}:=\cup _{n\in\mathbb{N}}A^n$ with $A^0:=\{\emptyset\} $ and $A^n$ being the $n$-fold cartesian product of $A$. For any $s:=(s_0,\cdots,s_{n-1})\in A^n\...
rfloc's user avatar
  • 1,209
3 votes
1 answer
195 views

Examples of index set not Turing equivalent to the Halting Problem?

By definition, a set $I \subseteq \mathbb{N} $ is an index set if $\forall i,j ((i \in I \land \varphi_i = \varphi_j) \implies j \in I)$. Thanks to the Rice's Theorem, we know that, said $F$ a family ...
NON's user avatar
  • 91
4 votes
1 answer
588 views

Busy Beaver argument and Gödel's incompleteness theorem

By Gödel's incompleteness theorem, it should not be possible to prove the consistency of ZFC within ZFC (if it is consistent). It is well known that the Busy Beaver function is uncomputable, and that ...
user22476690's user avatar
2 votes
0 answers
89 views

Is the set of primitive recursive reals recursively enumerable?

Let's define a primitive recursive real as a real which is the output of a primitive recursive function (the function that computes its binary expansion for instance). The set of primitive recursive ...
holmes's user avatar
  • 443
2 votes
2 answers
49 views

Reading on incomparable Turing degrees

I remember seeing in grad school a very nice proof that there were two incomparable Turing degrees by progressively constructing two sequences that couldn't be computed from each other. Can anyone ...
TomKern's user avatar
  • 3,079
0 votes
0 answers
19 views

Computability of composite function - special case

I was just thinking, but could not get to an answer: if I have two functions $f : \Sigma^* \to \Sigma^*$ and $g : \Sigma^* \to \Sigma^*$, one of which is computable, say $g$. If I know that $f \circ ...
Guilherme Ottoni's user avatar
3 votes
1 answer
62 views

Algorithm for Determining Truth of First-Order Sentences in Complex Numbers

Following my previous question Decidability in Natural Numbers with a Combined Function, I realized that there is a spectrum regarding the hardness of deciding whether a first-order sentence is true ...
Toobatf's user avatar
  • 87
-1 votes
1 answer
90 views

Decidability in Natural Numbers with a Combined Function [closed]

It is well known that there is no algorithm to determine whether a given first-order sentence is true in the structure of natural numbers with both addition and multiplication. In contrast, Presburger ...
Toobatf's user avatar
  • 87
1 vote
1 answer
23 views

Relationship between relative PA degree and Turing reducibility.

According to Reverse Mathematics, Definition 2.8.24 by Dzhafarov–Mummert, we say that a function $f \in 2^\omega$ has PA degree relative to $g \in 2^\omega$ if the collection of $f$-computable ...
T. Asai's user avatar
  • 104
1 vote
0 answers
63 views

Can you write a non-recursive/non-iterative but computable function?

According to here a single loop and four basic arithmetic operation is enough to simulate a Turing machine. My question is what if we unroll the loop and use only composition of four function. $\...
raoof's user avatar
  • 113
0 votes
1 answer
60 views

First-Order Logic with triangle formula algorithm [closed]

Is there an algorithm that, given a sentence in first-order logic over a signature with equality and a relational symbol $R$ of arity $3$ (where $R(x, y, z)$ is true if and only if a triangle can be ...
Toobatf's user avatar
  • 87
0 votes
1 answer
32 views

Why is the input and output of a P.C function bounded by the number of steps?

In Turing Computability by Soare,definition 1.6.17 states the following: We write $\phi_{e,s}(x) = y$ if $x, y, e < s$ and $y$ is the output of $\phi_e(x)$ in $< s$ steps of the Turing program $...
Konrad Wozniak's user avatar
0 votes
1 answer
105 views

Why doesn't this diagonal argument work?

I have a question about the standard rules for computing p.r. terms (see below). It seems pretty clear that these rules could be used to define a p.r. operation that evaluates any p.r. term of the ...
nontology's user avatar
1 vote
0 answers
76 views

What is the largest known "computational" ordinal

I am interested in the computational implementation of ordinals. What I mean by that, is a data structure T and a function/algorithm "compare" that takes two arguments of type "T" ...
Ivan's user avatar
  • 11
2 votes
0 answers
54 views

Implications of having access to the Busy Beaver oracle

Apologies if I'm asking a naïve question as I've only recently learned about the concept. What would be the practical implications (if any) of having access to a magical black box providing the ...
mavzolej's user avatar
  • 1,472
4 votes
1 answer
58 views

Ramsey's Theorem and Weihrauch reducibility

Let $\text{RT}^n_k$ denote (infinite) Ramsey's theorem for $n$-tuples and $k$ colors. Let $\leq_W$ denote Weihrauch (i.e., uniform) reducibility. It is known that, for fixed $k \geq 2$, if $n > m \...
Gavin Dooley's user avatar
  • 1,122
1 vote
0 answers
25 views

Prove that the set of RAMs which do not calculate the identity function is not recursively enumerable.

"Let $M_0,M_1,...$ be a Gödel Numbering of RAMs. Prove that $B\notin\text{RE}$ and $\overline{B}\notin\text{RE}$, whereas $B=\{i\in\mathbb{N}\;|\;M_i\text{ calculates the function id}:\mathbb{N}\...
arlidenCasper's user avatar
1 vote
0 answers
34 views

Wainer hierarchy, ordinal free definition below $f_{\epsilon_0}$

Is it possible to define Wainer hierarchy below $f_{\epsilon_0}$ in a way that would not refer to ordinals at all?
Jii's user avatar
  • 173
1 vote
0 answers
81 views

A question on a generalization of recursively inseparable sets

$\mathbb{N}$ denotes the set of natural numbers $0,1,2,\ldots$ In what follows all sets are subsets of $\mathbb{N}$. The classical definition that two sets $S_1$ and $S_2$ are recursively inseparable (...
Nellina's user avatar
  • 11
3 votes
1 answer
160 views

What's the difference between coding in second-order arithmetic and first-order arithmetic?

I am trying to understand the difference in developing coding in first-order arithmetic and second-order arithmetic. I have read various kinds of phrases like "coding can be done in $I\Sigma_0$&...
IllogicalUser's user avatar
3 votes
2 answers
143 views

Confused about Cooper's book's proof of Selman's theorem on enumeration reducibility

Here is an excerpt of Barry Cooper's book Computability Theory (2004), bottom half of page 179, which is short enough that I can copy it verbatim: THEOREM 11.1.13 (Selman's Theorem, 1971) For any $A,...
Gro-Tsen's user avatar
  • 5,631
2 votes
2 answers
227 views

What does it mean when the transition function of a NFA returns an empty set?

Given a NFA, $N = (Q, \Sigma, q_0, \partial, F_Q)$, where $\partial$ is the transition function $Q \times (\Sigma \cup \{ \varepsilon \} ) \to \mathcal{P}(Q) $. So $\partial(q, a)$ returns a set, ...
linear_combinatori_probabi's user avatar
0 votes
1 answer
38 views

Non-Classifiable Countable Math Objects

I was studying the classification of finite simple groups when I came up with this problem. Are there countable math objects that cannot be fully classified? Let the set be $A$, that is: 1.Exists a ...
Ma Ye's user avatar
  • 258
4 votes
1 answer
81 views

Graphs of recursive functions

Recently I've been studying the relationship between recursiveness of a function and recursiveness of its graph (i.e. recursiveness of the characteristic function of the graph). First, we have ...
blargoner's user avatar
  • 3,291
1 vote
1 answer
42 views

Can a non trivial computable function have an uncomputable root

Can a non trivial computable function have an uncomputable root, and how would you show this. Formally, Given $f$ a computable function and $r$ a real uncomputable number. Then $f(r) \neq 0 \vee ( \...
Sam Coutteau's user avatar
0 votes
1 answer
29 views

Transition in lemma proof in maximum set proof

(Sorry if it doesn't render MathJax right, I haven't figured out how it works here) I've been reading a lot of proofs of existence of maximal set and here is the problem. I'm working with proofs that ...
Alexander Pehtelev's user avatar
1 vote
1 answer
78 views

Since corollaries of ZFC are r.e.,why there are Turing degrees that are not r.e.?

for any Turing degree a and A∈a,and a fixed x,we can just put the formula “x∈A” into the Turing machine which examines whether a formula is a corollary of ZFC.It halts iff ZFC proves “x∈A”.So we got ...
jtxsxlm's user avatar
  • 11
2 votes
0 answers
76 views

Are the models of PA recursively enumerable?

Is there a Turing machine (TM from now on) which lists every model of PA (without the induction axiom schema, so just addition and multiplication)? More specifically, can such a TM list all infinite ...
nicholasbelotserkovskiy's user avatar
1 vote
0 answers
38 views

Coding for Kleene's closure of any countable alphabet (with textbook reference)

If $S$ is a countable alphabet, I suppose there exists an explicit and effective (i.e. computable) injection from $S^*$ to the set $\mathbb{N}$ of natural numbers. Could you provide a textbook showing ...
m. edovard's user avatar
0 votes
0 answers
47 views

textbook proving a theorem of computability theory (r.e. sets)

This is a well-known result of computability theory "A recursively enumerable union of recursively enumerable sets is still recursively enumerable" Could you point me to a textbook where ...
m. edovard's user avatar
0 votes
1 answer
57 views

Factorial for Natural Number Object

It is Awodey Exercise 17 in Chapter 9. It asks to define factorial as an arrow $N \to N$ for a natural number object. Awodey page 246 and 247 defines how to add a natural number by recursion. That is, ...
Y.X.'s user avatar
  • 4,223
1 vote
1 answer
63 views

Show that $\text{TOT} \equiv_m \text{INF}$.

Let $\text{INF} = \{x \in \mathbb{N}:\operatorname{Dom}\phi_x\text{ is infinite}\}$ and $\text{TOT} = \{x \in \mathbb{N} : \operatorname{Dom}\phi_x = \mathbb{N}\}$. We need to show that $$\text{INF} \...
Sai Nallani's user avatar
15 votes
3 answers
2k views

A seemingly contradictory function - where's the issue?

I have constructed a function of seemingly contradictory nature. Let $f$ be a function which, given an input $n\in \mathbb{N}$, lexicographically searches through all strings and finds the $n$th pair $...
volcanrb's user avatar
  • 3,054
1 vote
1 answer
99 views

Is there a real number which is computable but impossible to compute?

There exist numbers like Chaitin's constant which can be defined in natural language but for which it can be proven that there exists no finite algorithm to compute it to arbitrary precision, can a ...
codebender's user avatar
2 votes
1 answer
62 views

Does $\omega_1^{\text{CK}}$ allow to compute the halting problem of $\alpha$-th-order Turing machines for any $\alpha < \omega_1^{\text{CK}}$?

This page contains the following text (see the section “Higher-order busy beaver functions”): At least, under any reasonable formulation of the notion of a higher-order Turing machine, well-orderings ...
lyrically wicked's user avatar
1 vote
1 answer
79 views

Is there a way to measure the number of Turing Machines for which the Halting problem can be solved?

The Halting problem means that there is no algorithm which correctly determines whether an arbitrary program will halt. However, there may be a program which is able to correctly predict whether one ...
Electro-blob's user avatar
1 vote
1 answer
84 views

Sets proofing in computability

I have some thoughts about diagonalisation (I hope I use the right term). I've tried taking the sequence of c.e. sets A1,A2,... where Ai is a subset of Ai+1 But I'm stuck what to do next, how to proof ...
Alexander Pehtelev's user avatar
1 vote
1 answer
121 views

"Non-standard" witnesses to a $\Sigma_1^0$ statement

I'm in the midst of confusion about non-standard integers. It is my understanding that for example, in ZFC the Riemann hypothesis is equivalent to a $\Pi_1^0$ statement $(\forall y) \phi(y)$ where $\...
George C's user avatar
  • 1,645
0 votes
0 answers
30 views

How to prove that the following function F is primitive recursive

I have this Function: f(x): N→N The function returns the smallest number n which is a presentation as a product of multiplying primes. Also, n must be bigger or equal to x. (There must be at least ...
ella's user avatar
  • 1
6 votes
2 answers
117 views

Can we implement $\omega^{CK}_1$ using $\omega^{CK}_2$ as an oracle?

Let $\omega^{CK}_1$, $\omega^{CK}_2$ denote the first two admissible ordinals greater than $\omega$. Suppose we have an unknown well-ordering of $\mathbb{N}$ of the order type $\omega^{CK}_2$ as an ...
user23013's user avatar
  • 161
0 votes
1 answer
79 views

Questions about part of the proof of the general Halting Problem based on the string procedure [closed]

When reading mcs.pdf, it says in chapter 8.2: $P_s$ definition When a string $s \in \text{ASCII}^*$ is actually the ASCII description of some string procedure, we’ll refer to that string procedure as ...
An5Drama's user avatar
  • 416
0 votes
0 answers
84 views

A question on binary strings and bit swapping.

I consider binary strings over the bit-alphabet $\{0,1\}$. A binary string $S$ is balanced if the number of occurrences in $S$ of the bit $0$ is the same as the number of occurrences of the bit $1$; $...
Nellina's user avatar
  • 11
3 votes
2 answers
222 views

Proving a corollary of Trakhtenbrot theorem

In Sets, Logic, Computation, Trakhtenbrot's theorem is stated as follows: Theorem 15.21 (Trakhtenbrot's Theorem). It is undecidable if an arbitrary sentence of first-order logic has a finite model (i....
John Davies's user avatar
3 votes
1 answer
170 views

It the following a computable function?

Suppose to have a family of computable sets $\mathcal{A} = \{A_n \mid n \in \mathbb{N}\}$, then consider the function: \begin{align*} f: \mathbb{N} \times \mathbb{N}& \longrightarrow \mathbb{N}\\ (...
NON's user avatar
  • 91
2 votes
1 answer
169 views

Help in understanding proof for: There exists recursive $f$ such that for all $e$, if $R_e$ is well-founded then $f(e) \in O$ (G.E. Sacks book)

I am trying to read G.E. Sacks's book on Higher Recursion Theory. Let: $$ R_e(x,y) \iff \{e\}(x,y) \text{ is defined } $$ be the $e$th recursively enumerable binary relation. In Lemma 4.3, we have ...
Link L's user avatar
  • 735
1 vote
1 answer
74 views

Showing the weakness of the least modulus on a delta 2 approximation

I am working through Turing computability by Soare, and have been stumped on an exercise asking you to show the weakness of the least function for a $\Delta_2$-approximation. Let $A$ be a set, and $\{...
Konrad Wozniak's user avatar
2 votes
0 answers
52 views

Kreisel's proof that for every $\Pi^1_1$ closed set $F$, its perfect kernel $F_p$ is $\Sigma_2^1$

I'm trying to read Kreisel's paper "Analysis of the Cantor-Bendixson Theorem by Means of the Analytic Hierarchy" 1959. From what is written in the paper, I'm missing something simple. Here ...
Dariusz's user avatar
  • 51
3 votes
1 answer
87 views

Proof that $x \in O \wedge y \in H_x$ is $\Pi_1^1$

I am trying to read G.E. Sacks's book on higher order recursion theory, and he has this result (where $O$ is Kleene's $O$ and $H_x$ is a hyperarithmetic set, i.e. where we have sets of the form $H_{2^...
Link L's user avatar
  • 735

1
2 3 4 5
49