All Questions
Tagged with recursion-theory or computability
2,140 questions
2
votes
0
answers
28
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
4
votes
1
answer
716
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
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
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
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
vote
2
answers
159
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
2
votes
2
answers
162
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
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
3
votes
1
answer
79
views
Is the language L = { <M> | L(M) = L' } always undecidable when L' ≠ ∅?
Let $L' \subseteq \Sigma^*$ be a fixed, non-empty language.
Define the language:
$$
L = \left\{ \langle M \rangle \;\middle|\; L(M) = L' \right\}
$$
That is, $L$ contains the descriptions of Turing ...
- 181
3
votes
2
answers
110
views
What exactly $y$ is in Pumping Lemma when string is partitioned into $w=uyw$?
Pumping Lemma : For any regular language $\mathbb{L}$, there exists an integer $P$, such that for all $x\in \mathbb{L}$ with $|x|\geq P$, there exists $u, y, w \in \Sigma^*$, such that $x = uyw$, and
...
- 1,561
0
votes
1
answer
66
views
Question in proof of NOTALLNFA in NSPACE(n)
Let us consider the language
ALLNFA={⟨A⟩∣A is an NFA and L(A)=Σ∗}
and its complement
NOTALLNFA={⟨A⟩∣A is an NFA and L(A)≠Σ∗}.
In the context of showing that $\text{NOTALL}_{\text{NFA}}$ is in $\textsf{...
1
vote
0
answers
55
views
Defining an algorithm via Gödel numbers
Gödel managed to sneak self-reference into Principia Mathematica (PM). He showed that PM—and all other sufficiently expressive formal systems—contain unsolvable problems (aka unprovable theorems).
...
- 211
1
vote
1
answer
89
views
General-Purpose Electronic Analog Computer Example?
I'm curious as to whether there are any functional examples of or research about General-Purpose Analog Computers out there at the moment.
So any computing system that can:
store pure analog values
...
- 111
2
votes
0
answers
103
views
Busy beaver with Turing Machine
Basic setups:
A Turing machine M operates on a doubly infinite tape. The tape is divided into cells. Each cell can hold either a 0 or a 1 (meaning, we will consider only TM’s with two symbols). The ...
- 97
-4
votes
2
answers
144
views
is this the false assumption in a proof of the undecidability of the halting problem?
However given that Th can be constructed, we can construct a second machine Td1 such that :
Td1(Ti , D.N. of Ti) =
HALT if Ti does not halt on its own D.N. OR Ti=Td1
LOOP if Ti halts on its own D.N. ...
1
vote
0
answers
75
views
How to validate Bennett's reversible computation?
A reversible Turing machine ($\mathsf{RTM}$) is a Turing machine ($\mathsf{TM}$) whose transition function is a bijection, so that each instantaneous description ($\mathtt{ID}$) has at most one ...
11
votes
1
answer
2k
views
What's stopping us from smuggling complexity and uncomputability into standard models of computation?
Here is the definition of a ($k$-tape) Turing machine from Arora and Barak; everywhere else I've seen it has been effectively the same.
A finite alphabet $\Gamma$ with distinguished $\square$ blank ...
- 113
2
votes
0
answers
88
views
Is the language of Turing machines recognizing regular languages recursively enumerable?
Can we determine whether the following language is recursively enumerable?
$$L = \{\langle M \rangle \mid L(M) \text{ is a regular language}\}$$
Here, $\langle M \rangle$ denotes the encoding of a ...
- 367
0
votes
0
answers
67
views
Encoding Turing Machines with $\mathbb{1}^*$
Is there an encoding (enumeration) method for Turing machines where the encoding uses only the alphabet $\{1\}$, i.e., the encoding is in $\mathbb{1}^*$ (the language of strings consisting only of the ...
- 367
0
votes
1
answer
82
views
rice's theorem: what if never halts?
Let $P$ be any nontrivial property of the language of a Turing machine. Prove
that the problem of determining whether a given TM’s language has property $P$ is undecidable.
Proof: (from sipser's book)
...
- 101
0
votes
1
answer
78
views
Computability, Totality, and Range of Two Turing Machine-Dependent Functions
I am analyzing two functions that are defined in terms of an effective enumeration $(M_n)_{n \in \mathbb{N}}$ of all Turing machines. For a given input $x$, the notation $M_n(x) \downarrow$ means that ...
7
votes
1
answer
1k
views
Are any two recursive languages reducible to one another?
Given two recursive languages A and B with alphabets $\Sigma$ and $\Delta$ respectively, is there always a computable function $f:\Sigma^*\rightarrow\Delta^*$ such that $x\in A \iff f(x)\in B$?
(other ...
- 75
3
votes
1
answer
137
views
Infinitely-taped (& "headed"!) Turing Machine: "Stronger" Than Standard
Multi-taped Turing machine are equivalent to the standard single-taped variety; that much I know and can prove to a level of rigor that satisfies me; so long as there are finitely many tapes, I can ...
- 43
0
votes
1
answer
117
views
Informal Description of a Non-Deterministic Turing Machine (NTM) for a Language
I need help describing a Non-Deterministic Turing Machine (NTM) for the following language:
$L=\{(ww^c)^n | n>1$ and $w,w^c\in\{a,b\}^*\}$. If $w=w_1...w_k$ then $w^c=w_1^c...w_k^c$ where $w_i^c=b$ ...
- 1
2
votes
1
answer
181
views
Implementing a TM with FIFO Machine
I am attempting to simulate a TM on a FIFO machine. My initial approach is the following:
\begin{align*}
\text{Starting string:} & \quad \text{uabv}\rightarrow bv\#ua \\
\text{Step 1:} & \quad ...
- 21