Questions tagged [computability]
Questions related to computability theory, a.k.a. recursion theory
2,140 questions
2
votes
0
answers
29
views
Two Turing machines that accept each other’s indices
I just learned about Kleene’s recursion theorem; the one that states that for any computable $Q$ there is an $e$ such that $\varphi_e(x)\simeq Q(e,x)$. Applying this to a Turing machine that halts if ...
- 121
1
vote
0
answers
114
views
A supplement to "FROM FREGE TO GÖDEL A Source Book in Mathematical Logic, 1879-1931" for developments on type theory and computation
(I cross-posted this on Math SE because the answering rate is relatively slower here, and I was really desperate for any suggestions
If you feel the post on math SE misses any good material or sources,...
- 141
4
votes
1
answer
719
views
Are oracle machines for the halting problem just impossible to build but logically valid, or are they also introducing logical inconsistencies?
On Wikipedia in the article for oracle machines it says the following:
A machine with an oracle for the halting problem can determine whether
particular Turing machines will halt on particular inputs,...
- 55
1
vote
0
answers
35
views
Can iteratively strengthened sound theories emulate an oracle for a noncomputable set?
A countable but not computable set $X$ can be computed by a Turing machine that has access to an oracle $O_X$ that can decide whether $x$ is in $X$.
Suppose we keep querying $O_X$ for different ...
- 121
2
votes
1
answer
101
views
Can every countable set be expressed as the difference of two recursively enumerable sets?
I have two related questions about the structure of countable sets in computability theory, which I believe are equivalent.
...
- 123
7
votes
1
answer
280
views
What are the fundamental arguments for the correctness of the Church-Turing thesis?
I'm interested in gathering some solid arguments in favor of the Church-Turing thesis, which states that anything computable by an algorithm can be computed by a Turing machine. I understand that ...
- 207
0
votes
0
answers
41
views
Properties of the sequence and its generators listing Gödel numbers of programs with a particular syntactic property
Given a Gödel numbering of programs in a Turing complete language, consider a sequence of the Gödel numbers of programs that have a particular syntactic property (or more generally, non-(non-trivial ...
- 213
0
votes
1
answer
113
views
Halting Problem with Restricted Input
I was reading through the proof for the halting problem and saw that that the "pathological" program that makes program H return the wrong result needs to have H inside it, where H is a ...
5
votes
2
answers
667
views
Proving the non-regularity of a language
Consider the Language $L=\{aba:a\in0^{+}, b\in \{0,1\}^{+}\}$ over the alphabet $\{0,1\}$
Claim:- $L$ is a non-regular language
Proof:- Suppose $L$ is regular. Then by pumping lemma there exists a ...
- 179
-1
votes
1
answer
107
views
What's the difference between lexicographic order and canonical lexicographic order?
I've encountered this question since I studied the Cardinality of SD, deriving from the statement that the set of syntactically valid Turing machines is infinite and there exist a canonical ...
- 1
1
vote
2
answers
160
views
Reduction Using Universal TM of Fixed Size
$L = \{ <M> | |L(M)|=\infty \wedge |<M>|<k \}$, for some $k>1000$.
It seems to me that $L \notin RE \cup CoRE$, and I would like to prove it.
However, it seems that the classic ...
- 322
4
votes
1
answer
239
views
Does every infinite recursive language contain a non-recursive RE subset?
Let $L \in R$ be an infinite recursive language. Is it always possible to find a subset $L' \subseteq L$ such that $L' \in \mathbb{RE} \setminus R$?
In other words, can every infinite decidable ...
- 181
2
votes
2
answers
164
views
Is the language 𝐿 = { ⟨ 𝑀 ⟩ ∣ 𝑀 runs an even number of steps for every input } in RE?
I'm trying to understand the classification of the following language:
$$
L = \{ \langle M \rangle \mid M \text{ runs for an even number of steps on every input } w \in \Sigma^* \}
$$
That is, the set ...
- 181
4
votes
0
answers
60
views
Complexity-theoretic view of Algebraic Numbers
Imagine an input-less Turing machine $M$ that runs potentially forever, outputting a string of 0's, 1's, and "."s. $M$ can then be associated with the real number $x_M$ whose binary ...
- 141
3
votes
1
answer
135
views
Is L={⟨M⟩∣L(M)∈P}in RE, when P is a non-trivial property and Z∈P is infinite and in RE or R?
Let $Z \subseteq \Sigma^*$ be an infinite language such that $Z \in \text{RE}$ or $Z \in \text{R}$.
Let $P \subseteq RE$ be a non-trivial language property
Now define the language:
$$
L = \{\langle M \...
- 181