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).
2,432
questions
2
votes
1
answer
38
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$,...
- 4,223
3
votes
1
answer
63
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\...
- 1,209
3
votes
2
answers
192
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 ...
- 91
4
votes
1
answer
587
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 ...
- 159
1
vote
0
answers
87
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 ...
- 433
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 ...
- 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 ...
- 139
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 ...
- 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 ...
- 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 ...
- 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.
$\...
- 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 ...
- 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 $...
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 ...
- 27
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" ...
- 11