Questions tagged [turing-machines]
Questions about Turing machines, a theoretical model of mechanical computation capable of simulating any computer program.
2,106
questions
1
vote
1answer
18 views
How are two registers are enough to simulate a Turing machine?
The paper A universal cellular automaton in the hyperbolic plane says:
Our simulation consists in simulating the execution of a register machine. It is known that two registers are enough to simulate ...
0
votes
1answer
20 views
Question about reduction Proof
I've recently seen a proof that the set of Turing machines $L = \{encode(M) |L(M) \text{is closed under reversal}\}$ is not decidable.
The proof used following idea:
Reduce from the $A_{TM}$ problem ...
0
votes
1answer
13 views
Show that the Turing Reduction is transitive: if $A\leq_{T}B$ and $B\leq_{T}C$ then $A\leq_{T}C$
I am struggling with this question, because I came up with an relatively easy proof for mapping reduction:
if $A\leq_{M}B$ and $B\leq_{M}C$ then $A\leq_{M}C$. We know that $w \in A$ $\Leftrightarrow$ ...
1
vote
2answers
41 views
Prove that { $\langle M \rangle$ : $M$ is a TM and $L(M)$ is decidable} is undecidable
So I want to prove that $$ \big\{\langle M \rangle : \text{ M is a TM and } L(M) \text{ is decidable} \big\}$$ is undecidable.
To do so I want to reduce it from$\ \overline{A_{TM}}$ with a function ...
2
votes
1answer
34 views
Does $NP^{SAT}=NP^{NP}$?
Does $NP^{SAT}=NP^{NP}$?
We can see easily that $NP^{SAT}\subseteq NP^{NP}$, because $SAT \in NP$.
But is the other side $NP^{NP}\subseteq NP^{SAT}$ also true? If yes, how can we prove it?
-4
votes
0answers
59 views
Turing machine A that when given any program B as input can determine whether or not B produces “hello world”
“It is not possible to create a computer program A that when given any program B as input can determine whether or not B produces “hello world” as its first statement”. This problem is a variant of ...
-4
votes
0answers
21 views
Show (by construction) that language ALLDFA = {(A)|A is a DFA and L(A) = sigma*} is decidable
Show (by construction) that language ALLDFA = {(A)|A is a DFA and L(A) = E'} is decidable. That is, construct a Turing machine that decides ALLDFA Give a short argument why your TM always halts. The ...
-5
votes
3answers
173 views
Does the Linz Ĥ specify a computation that never halts when the embedded halt decider is a UTM?
When we hypothesize that the halt decider embedded in Ĥ is simply a Universal Turing Machine (UTM) does this define a computation that never halts when Ĥ is applied to its own Turing machine ...
-2
votes
0answers
31 views
Rice's theorem extension
I've tried to solve this question below but I got stuck.
Let $P$ be a non-trivial property. Proof that the extension of Rice's theorem is true:
If $L_1$ $\in$ $P,$ $and $ $L_2$ $\in$ $RE$ $\setminus$ $...
0
votes
0answers
18 views
Turing machine sequence of configurations
hello I have written the sequence of configurations for the following Turing machine for input 00 but my answer has been marked wrong and I'm not sure where I have gone wrong I have fried it 3 times.
...
0
votes
1answer
37 views
Proof that R (decidable languages) is not closed under homomorphism
After searching the internet for a bit, I found that the same proof came up over and over again.
The thing is, it seems like the proof is incomplete. Here's the proof:
However, the recursive ...
1
vote
2answers
54 views
What is appearance checking in the context of formal grammars?
As I did not find any definition of the term "appearance checking" although it is widely used, I am eager to ask as what it can be defined.
Perfect would be an example using a context free ...
2
votes
1answer
24 views
Language in $R \setminus \mathit{NP}$
I am wondering whether the language $$L_{\textrm{hanoi}} = \{\langle k,s \rangle \mid \text{$s$ is a solution of Tower of Hanoi problem on $k$ rings}\}$$ is in $R\setminus \mathit{NP}$.
I want to ...
0
votes
1answer
30 views
How to prove that this language is not recursive enumerable?
I need to prove that the following language is not recursively enumerable, while its compliment is recursive enumerable:
$L := \{w \in \{0,1\}^* |$ TM $M$ with $w = \langle $ M $\rangle$ does not ...
0
votes
1answer
30 views
Is a Turing Machine a Well-formed formula?
Today i wrote something about the bijection between turing machines and recursive functions. And i describe a Turing Machine as a Well-formed formula because it seems like a WFF to me.
But is it ...
0
votes
1answer
34 views
Reduction of Turing-machine language
How to show that the following language is undecidable using reduction on the halting problem?
$L: = \{w \in \{0,1\}^* |$ TM $M$ with $w = \langle M \rangle$ does not accept any input $\}$
When TM ...
0
votes
1answer
43 views
Reduction of the diagonalization language to the universal language
I'm going through Jeffrey D. Ullman's Introduction to Automata Theory, Languages, and Computations. The author reduces an instance of the membership problem in $L_d$ (diagonalization language) to a ...
1
vote
1answer
24 views
Slowdown in making nondeterministic Turing machines deterministic
For every nondeterministic Turing machine, must there exist an equivalent deterministic one that runs in no more than twice the time?
Why or why not?
Can anyone explain?
1
vote
1answer
18 views
Is there a mapping reduction for every two language $A$ and $B$ to some language $C$?
One of my friend told me that there is a language $C$ for every two languages $A$ and $B$ s.t $A \leq_{m} C$ and $B \leq_{m} C$ , he simply define two languages $A’=\{0w|w \in A\}$ and $B’=\{1w|w \in ...
1
vote
1answer
37 views
How to draw Turing machine for multiplying a number by 2 in base 10
I'm trying to design a turing machine that given a number in base 10 multiplies it by 2.
The problem seems trivial if the number is represented in binary so what I've thought is try to convert it from ...
1
vote
0answers
30 views
Prove that characteristic function $f_w$ in write protected input turing machine behave as a 2FSA
Write protected input turing machine is a single-tape TM that cannot write on the input portion of the tape. I almost prove that these TMs can only recognize regular languages but i have a problem in ...
1
vote
1answer
24 views
How to design a turing machine for a context-free grammar? what are the steps?
How to design a Turing machine for a context-free grammar? what are the steps? for example, What are the steps to design a Turing machine for the following grammar with alphabet $\{a,b\}$.
$S\...
0
votes
1answer
23 views
How can we solve halting problem efficiently?
I was doing exercises regarding the halting problem and there is this question where I am stuck
Ques: it goes like suppose if you can decide the halting problem with a query "Is <tm,s> ...
-2
votes
1answer
33 views
Turing machine that accepts $a^{n^2}$
How do you make a TM that accepts the following language?
$$ \{ a^{n^2} \mid n \ge 0 \} $$
0
votes
0answers
48 views
Is the language of Turing Machine encodings decidable is this instance?
I have an exercise question as follows:
L is a set of all Turing Machine encodings for which the Turing Machine halts after a number of steps less than or equal to the minimum value among |w| and 1000,...
0
votes
1answer
21 views
What does “satisfactory definition” mean?
I am reading the book Artificial Intelligence (A modern approach) by Stuart Russell and Peter Norvig. While reading the book, I saw the below sentence in the book.
The Turing Test, proposed by Alan ...
1
vote
0answers
20 views
Language of all words of the form $ww$ is in $\mathsf{NTIME}(n)$
Show that the language $\{ ww \mid w \in \{0,1\}^* \}$ is in $\mathsf{NTIME}(n)$.
I have a doubt first of all how can I prove that. Secondly, what does NTIME mean? Can we use a $k$-Tape Turing ...
1
vote
1answer
32 views
Turing machine generating $a^b$ for given a and b
I want to draw an state diagram for a Turing machine such as:
If "a" and "b" are the inputs, output in tape will be $a^b$.
I saw many Turing machines that output:
$a+b$ $~~$ ,$~~$ $...
0
votes
0answers
32 views
Prove language is not Turing-recognizable using contradiction
Show that the language L = {<M>| M is a TM and does not accept <M>} is not Turing-recognizable.
Note: Prove by contradiction. No need for reduction.
This is the problem I am trying to ...
0
votes
0answers
24 views
Would a “TM starting with a blank tape will ever write a nonblank symbol anywhere before halting” be decidable?
Would a "TM starting with a blank tape will ever write a nonblank symbol anywhere before halting" be undecidable?
0
votes
0answers
18 views
Does TM $M$ on input $\epsilon$ ever moves its head 5 consecutive time to right?
Is language $L$ decideable ?
$$L = \{ \langle M \rangle | M \text{ on input $\epsilon$ moves it's head five consecutive time to right}\}$$
I think it is not but i am not sure about it. My reason :
if ...
1
vote
1answer
23 views
Complement of equality problem of Turing machine is recognisable or not
Complement of equality problem of Turing machines is unrecognisable or not-recognizable but How?. As per my knowledge it is recognisable if you can decide its accept condition but not Reject and ...
0
votes
0answers
24 views
Understanding the Space Hierarchy Theorem and its proof
This is what I've learned from the SHT and the sketch of its proof. I would appreciate pointing out any mistake.
The intuition behind the Space Hierarchy Theorem is that
"there are Turing ...
1
vote
1answer
44 views
Is every decidable language recognizable by a Turing Machine space-bounded by some f(|w|)?
The negative answer to decidable = non-contracting grammar? suggests the following question:
Is there a decidable language that can be recognized only by a space unrestricted Turing Machine (i.e. ...
0
votes
0answers
24 views
Proof that a function is not computable by a Turing Machine
I am going through a problem that I am asked to prove if there is a Turing machine that can compute f for every input a.
The function is the following :
$$f(a) = \begin {cases} 1 & if \ there \ is\...
1
vote
2answers
57 views
Are decidable set/languages EQUIVALENT to type 1 grammars (non-contracting)?
Suppose a Turing Machine (TM_G) that generates natural numbers following < or, equivalently, it generates words in lexicographical order.
Then, that language/set is decidable. Because it is trivial ...
1
vote
1answer
72 views
What does a non-deterministic guess “look like”?
I have been trying to understand the solution to the following problem:
"Show that if $L_2$ and $L_3$ are Turing recognisable, then so is $L_2L_3 = \{w_1w_2 : w_1 \in L_2,w_2\in L_3\}$:
which ...
0
votes
1answer
26 views
What subset of TMs are there where the halting problem is decidable?
Halting problem is not decidable in general, but are there interesting/useful subsets where it IS decidable? Bonus points if that subset is actually helpful.
Example:
If we know BB(x), then the ...
0
votes
0answers
17 views
Purpose of Acceptance Problem
I am confused about the purpose/statement of the Acceptance problem:
$A_{TM} =\{\langle M\rangle\,s |$ Turing machine $M$ accepts $s\}$
It can be shown that $A_{TM}$ is uncomputable, so we know that, ...
0
votes
0answers
18 views
How to show that if 0 < $\alpha$ < 1, RP$_\alpha$ = RP using reliability amplification [duplicate]
Let $0 \le \alpha \le 1$. The complexity classs $\mathsf{RP}_\alpha$ consists of all languages $L$ for which we can find a probabilistic polynomial time Turing machine which satisfies the following ...
0
votes
1answer
27 views
Proving undecidability of a language with mapping reductions
I'm referring to questions like this one:
Mapping reduction to show NeverHalt is undecidable
I understand with Turing reductions, you have to use oracle calls of the unknown language you're trying to ...
-1
votes
1answer
37 views
How can i prove that this language is not turing-recognizable?
I'm having difficulty understanting how can i prove that
L = { w | w0 is the representation of a turing machine M with input {0, 1} and M don't accept w }
is not turing-recognizable
The solution I ...
1
vote
1answer
29 views
Proving Undecidability with reductions - Why do some proofs not use an Oracle?
I'm specifically referring to this group of questions here: https://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf
So as I've learnt it, say we want to prove a new Language L is ...
0
votes
1answer
37 views
Turing decidable languages
On an old worksheet I came across the question
If L1 and L2 are two Turing decidable languages, then show that 𝐿1∪𝐿2 and 𝐿1𝑜𝐿2 are Turing decidable languages (high-level description with stages ...
0
votes
1answer
20 views
Turing Machine that triples a unary format number?
I managed to figure out how to double a unary format number however I have had no such success in tripling it. An input tape would be of the following format Λ111Λ and the output would be like ...
0
votes
0answers
86 views
Can a Turing machine start on a blank?
Couldn't find a definitive answer anywhere so asking here. I have a Turing machine and the start state can go straight to the end state without passing through any of the other five states via
Blank -...
1
vote
1answer
27 views
What are the differences between Oracle Turing Machine and PAC?
I am having difficulty understanding the difference between PAC and Oracle Machines. I cannot compare these two in terms of uncertainty and physical effort.
The degree of uncertainty we can tolerate ...
0
votes
1answer
56 views
Time complexity of $L=\{a^nb^n | n \ge 1\}$
Consider the following language:
$$L=\{a^nb^n | n \ge 1\}$$
I constructed the following Turing Machine:
\begin{eqnarray}
T &=& (Q, \Sigma, \Gamma, \delta, q_0, B, F) \nonumber \\
Q &=& ...
0
votes
1answer
37 views
Why if L and ¬L (Complement of L) are turing-recognized both are turing-decidable?
I can't understand this theorem:
If both L and L complement are turing-recognized, both are turing-decidable
Proof:
w is M input
if w ∈ L then M1 accepts w and M accepts w
if w ∉ L then M2 accepts w ...
0
votes
1answer
96 views
Derive Turing Machine with high level description
So I have been going over Turing machines for my revision and came across an old worksheet with the question:
Derive a Turing Machine using high level description with stages to decide on the ...
