# Questions tagged [turing-machines]

Questions about Turing machines, a theoretical model of mechanical computation capable of simulating any computer program.

1,945 questions
Filter by
Sorted by
Tagged with
51 views

### Why Linear bounded automata requires Nondeterministic Turing machine ? Why not Deterministic Turing machine?

Going through the topic of LBA, i.e., Linear bounded automata. I found that LBA requires the NTM with some constraints on tape. I found the same information from different sources. But I did not get ...
1k views

### What are the options of head movement for a Turing machine?

I find several contradictory definitions regarding the head movements of the Turing machine. In some places, it is only L / R. While in some other formal definition; it is L / S / R. Which one is ...
39 views

### Prove for the theorem “Every non deterministic Turing maching has an equivalent deterministic Turing machine”

I know that a Deterministic TM single tape has an equivalent Deterministic TM multiple tape, but I can't get how a Deterministic TM multiple tape can simulate a non-deterministic TM(The mecanisme). ...
99 views

### What does “lookahead” refer to?

I keep hearing about lookahead parsers, LL parsers, LR, LALR, etc... but no clear explanation behind the etymology of this word. What does "lookahead" refer to? How does this relate to LL, ...
49 views

### How to add two positive or negative integers using the same Turing Machine

I want two know how can I add two positive or negative integers using the same Turing Machine I am using unary numbers in the following way: 0 = 1; 1 = 11; 2 = 111; 3 = 1111 ... I know how to add two ...
37 views

### How are useless states created NFA to DFA

So I understand how to convert an NFA to a DFA, however my question is, on a conceptual level, how and why are useless states created, and how can you (if there is a way) convert an NFA to a DFA ...
25 views

### A genral Turing model with one tape to define sublinear space (L,NL,..)

A genral Turing model with one tape to define sublinear space (L,NL,..) Normally to define sub-linear space complexity we need special Turing models with many tapes, at least two: a read-only tape and ...
35 views

### Do languages in $\mathsf{coRE} \setminus \mathsf{R}$ have Turing machines?

What can we say about languages in $\mathsf{coRE} \setminus \mathsf{R}$? Are there Turing machines for these languages? I know that $\overline{HP} \in \mathsf{coRE}$ doesn't have a Turing machine, and ...
27 views

### Proof that languages are Turing-recognizable iff computably-enumerable

A very small question on this proof, which I found as Theorem 3.21 in Sipser's, and in my lecture notes. In the "only if" direction, we assume that a Turing machine $M$ recognizes some ...
28 views

### Incomputable sets of low degree vs Rices theorem?

I have heard that there are sets that are not computable, but are lower in degree than the halting problem. How does this not contradict Rice's theorem? Are there any concrete examples of such sets?
27 views

### How can we construct a TM with a Halt1 Oracle that decides if a TM halts on all inputs?

Can we construct an explicit Turing Machine with a Halt1 oracle that decides if a standard Turing Machine halts on all inputs? By a Halt1 oracle I mean that we have the ability to decide if Turing ...
64 views

### Halting problem for turing machines with one input

My question is: Is there a simple construction similar to Turing's 'liar' program that shows that Turing machines plus a halting oracle cannot decide if a given Turing machine halts on all inputs. ...
35 views

### Turing machine M' from M

Let M be a Turing machine not necessarily halting on every input. Construct Turing machine Mā² which halts on w if ww ā L(M) and does not halt otherwise.
48 views

### Blank symbol on output tape

A unary Turing Machine X has input alphabet Ī£ and tape alphabet Ī. We represent the blank symbol belonging to the tape alphabet as _ . Given as input 11111 X writes 1_1_11_1 as output. Is the blank ...
119 views

### What are analog and digital in computer science?

I once thought that any analog computer is any computer which "doesn't need electrical current to work". I once thought that any digital computer is any computer which "does indeed need ...
58 views

34 views

### $A \leq_p {\overline{A}} \Leftrightarrow {\overline{A}} \leq_p A$

I want to prove that $$A \leq_p {\overline{A}} \Leftrightarrow {\overline{A}} \leq_p A$$. Does anyone have a Idea how to solve this ?
77 views

### How to prove the language of all Turing Machines that accept an undecidable language is undecidable?

I want to prove that $L=\{\langle M \rangle |L(M)\text{ is undecidable}\}$ is undecidable I am not sure about this. This is my try : Suppose L is decidable. Let $E$ be the decider from $L$. Let $A$ be ...
54 views

### If $A\in RE$ then $f(A)\in RE$

Let $A\in RE$, and define$f(A) = \{y |\ y= f(x),\ x\in A\}$ for some computable function $f$. Then $f(A)\in RE$. I can't figure out why this is true. Since $f$ is computable there is a Turing machine ...
47 views

### Rice's Theorem for Turing machine with fixed output

So I was supposed to prove with the help of Rice's Theorem whether the language: $L_{5} = \{w \in \{0,1\}^{*}|\forall x \in \{0,1\}^{*}, M_{w}(w) =x\}$ is decidable. First of all: I don't understand, ...
26 views

### Relations between deciding languages and computing functions in advice machines

I'm trying to understand implications of translating between functions and languages for P/Poly complexity. I'm not sure whether the following all makes sense. Giving it my best shot given my current ...
45 views

### Intuition for Church-Turing thesis for Turing machines

I can very clearly see "why" mu-recursion is a universal model of computation, i.e. why the Church-Turing thesis -- that any physically computable algorithm can be executed with mu-recursion ...
215 views

### Is English Turing-complete?

Is English Turing-complete? Intuitively it makes sense that English is Turing complete, since you can talk someone through building a Turing machine. But I also think there might be some operators ...
31 views

### Decidability for $\exists w´, w´´\in L:$ so that |w´´| - |w´| is prime

I tried to decide wheter the given Language $L = \{ \langle M \rangle | M \space is \space TM \space and \space \exists \space wĀ“,wĀ“Ā“\in L(M):|wĀ“Ā“|-|wĀ“| \space is \space prime \}$ is recursive or ...