All Questions
Tagged with recursion-theory or computability
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
718
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
52
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
12
votes
2
answers
902
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$, ...
- 1,081
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
0
votes
1
answer
260
views
How does one transform a decision problem into a function problem?
Given an alphabet $A$, define a formal language $L\subseteq A^*$. This is a decision problem by definition, regardless of which subset it is. Let's make a strong assumption saying that $L$ is ...
- 307
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
2
votes
1
answer
110
views
is every non-trivial language in RE reducible to every language not in (RE union co-RE)?
I would like to know if every non-trivial language in RE is reducible to every language not in (RE union co-RE)?
- 21
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{...
-2
votes
1
answer
77
views
Are there known formal systems where logic and operators emerge purely from recursive structure?
I’m exploring whether there are any existing formal systems that do not assume logic, types, or operators, but instead allow them to emerge solely from recursive structural transformations.
In the ...
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
2
votes
1
answer
89
views
prove\disprove : $L_1 \cup L_2 \notin RE$ and $L_1 \cap L_2 \notin RE$ $\implies$ $L_1 \notin R$
On the one hand, I feel like I don’t have enough information or tools to prove this. Because if
$L_1 \cup L_2 \notin RE$, from my perspective, it only means at least one of them is $ \notin RE$; ...
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
1
vote
2
answers
134
views
DSW, exercise 2.4.7. How to transform a forward-branching program into a straghtline one
This is an exercise from Computability Complexity and Languages by Davis, Sigal, Weyuker.
First, a quick overview of the language $\mathscr{S}$:
it has input variables $X_1,X_2,...$, local variables $...
- 11
2
votes
0
answers
104
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
1
vote
1
answer
137
views
Barry Cooper's Proof of Rice's Theorem
I have been studying Rice's Theorem, and I came across the following proof, which I am trying to understand in more detail:
[Rice's Theorem]
If $A$ is an index set --- $\neq \emptyset$ or $\mathbb{N}$ ...
-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. ...
0
votes
2
answers
104
views
Constructing an undecidable language
Suppose you construct a language $L$ by flipping a coin for every $x\in\{0,1\}^*$ to decide whether it's in $L$. After doing this, $L$ is now fixed but presumably there exists no compact description ...
- 23
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 ...
0
votes
0
answers
32
views
How does an LBA recogniser for accepting computation histories work when a TM M loops infinitely for an input string w
In Sipser's book on Theory of Computation, the LBA $B_{M,w}$ is designed to accept all (if any) accepting computation histories of the string $w$ when run on the TM $M$. The LBA $B_{M,w}$ is described ...
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
-1
votes
1
answer
68
views
Is it possible to reduce H_0 to A_0?
I am trying to understand whether it is possible to construct a Turing Machine (TM) that accepts an input if and only if it halts on that input. My question is closely related to the halting problem.
...
- 55
2
votes
0
answers
89
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
31
views
Designing a 3-state Turing Machine Equivalent to a Given Machine [duplicate]
Assume we have a Turing machine $M = (Q, \Sigma, \Gamma, \delta, q_0, B, F)$, where $|Q| = k$, that recognizes the language $L(M)$.
I want to design another Turing machine $M'$ that satisfies $L(M') = ...
- 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
2
votes
1
answer
145
views
Problems which require an arbitrary amount of states to be decided
Given some $n \in \mathbb{N}$, can one define a concrete computable decision problem which cannot be solved by a Turing machine with less than $n$ states, 1 tape and the tape alphabet $\{0, 1, B\}$? ...
- 133
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
2
votes
1
answer
88
views
Showing that there exists a verifier for $\overline{E_{TM}}$
Using the definition from Sipser of a verifier as a machine that always halts (e.g. accepts or rejects a given input), I believe the language $\overline{E_{TM}}$ (e.g. the language consisting of ...
- 123
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 ...
2
votes
0
answers
68
views
I know the following language is undecidable by reduction to HP bar. But how does it relate to L_EQ?
The languages are defined as such (for standard Turing machines and over $\{0, 1\}^*$:
$$
L_3 \triangleq \{
(\langle M \rangle, x) \mid \text{$\forall M^\prime, [x\in L(M^\prime)] \lor [\langle M^\...
- 21
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
0
votes
1
answer
155
views
How to proof the existence of languages over {0,1}* that are neither semi-decidable nor co-semi-decidable
I am currently working on an assignment, and we have to prove the existence of languages over the alphabet {0,1} that are neither semi-decidable nor co-semi-decidable.
My intuition is that this can be ...
- 55
3
votes
1
answer
138
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
2
votes
1
answer
139
views
Does $\mathrm{REG_{CFG}} \leq_T \mathrm{HALTING}$?
Let $\mathrm{REG_{CFG}} = \{ G \text{ context-free grammar}\mid L(G) \text{ is regular} \}$.
Is it Turing-reducible to Halting problem?
Or say, is there a oracle machine with an oracle of Halting ...
- 41
0
votes
1
answer
118
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
0
votes
0
answers
98
views
Informal Description of a Deterministic Turing Machine for a Specific Language
I'm working on a problem that asks for an informal description of a deterministic Turing Machine (TM) for the following language:
$L=\{a^i b^j a^k b^l | i+j=k+l\}$
The challenge is to describe how a ...
- 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
0
votes
1
answer
208
views
Is $\text{logCLIQUE}\in \texttt{NSPACE($\log^2(n)$)}$?
I inspired by this question, $$\text{logCLIQUE}=\{\langle G\rangle:\text{G=(V,E) contains a clique of size $\log(|V|)$}\}.$$
Here $G$ is an undirected graph and it can be assumed that the number of ...
- 33