Questions tagged [computability]
Questions related to computability theory, a.k.a. recursion theory
2,139 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
-2
votes
0
answers
34
views
What if Turing was wrong about the nature of decider machines? [closed]
What if there was a way to redefine decider machines such that they didn't succumb to the problems Turing thought they had?
I wrote a paper on this, and I'd like feedback. Here's the abstract:
This ...
4
votes
1
answer
664
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,...
1
vote
0
answers
23
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 ...
2
votes
1
answer
78
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.
...
7
votes
1
answer
226
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 ...
0
votes
0
answers
28
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 ...
0
votes
1
answer
76
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
643
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 ...
-1
votes
1
answer
79
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
vote
2
answers
112
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 ...
4
votes
1
answer
210
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 ...
2
votes
2
answers
129
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 ...
4
votes
0
answers
37
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 ...
3
votes
1
answer
89
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 \...
12
votes
2
answers
858
views
A variant of the halting problem for subsets of Turing machines
Suppose we have some subset $S$ of Turing machines with the property that, for every partial recursive function, at least one machine in $S$ computes that function.
Question: for any such subset $S,ドル ...