Questions tagged [turing-machines]

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

Filter by
Sorted by
Tagged with
1
vote
2answers
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 ...
5
votes
2answers
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 ...
0
votes
0answers
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). ...
1
vote
1answer
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, ...
1
vote
0answers
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 ...
1
vote
2answers
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 ...
1
vote
0answers
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 ...
1
vote
2answers
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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?
0
votes
1answer
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 ...
0
votes
1answer
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. ...
0
votes
0answers
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.
1
vote
0answers
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 ...
0
votes
3answers
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 ...
1
vote
1answer
58 views

Cannot understand reductions from the halting problem and its complement

When I was going through the reductions from $HP$ and $\overline{HP}$ in this handout, I do not understand how everywhere the following claim is made: $$⟨M,x⟩ \in \overline{HP} ⇒ \text{M does not halt ...
3
votes
1answer
88 views

Disprove unrealistic speed-up of total Turing machines

Let $T_1$ be a total Turing machine deciding language $L_1$, and let $I_1$ and $I_2$ be two separate inputs to $T_1$. Further, let $I_{c}$ be $I_2$ concatenated to $I_1$ with some separation symbol in ...
-1
votes
1answer
66 views

Is this Language decidable?

As the title says; is this language decidable and how do you prove it? $$L =\{\langle M\rangle \mid M \text{ is a Turing Machine and there is an input that } M \text{ halts on} \} $$
1
vote
1answer
78 views

Church–Turing thesis and infinite Turing machines

What exactly is the definition of church turing thesis? It's really confusing. I want to prove the following statement: A Turing machine with infinitely many states is more powerful than a regular ...
1
vote
0answers
26 views

Understanding the equivalence of a Turing machine and an enumerating machine

The normal argument for a decidable language to build an enumerating machine is given as follows: Let $M$ be a Turing machine which decides a language $L$, and let $s_1,s_2,\ldots$ be a list of all ...
0
votes
0answers
18 views

Building an enumerating machine with a Turing machine

I have a Turing machine say M with a state diagram which decides a particular language... I wanted to build an enumerating machine for the same.. Since its decidable.. I can use the following logic ...
0
votes
0answers
65 views

what is the function of a turing machine

The main question asked me to build a certain turing machine such that given a word w over {0,1}* the turing machine accepts all such words and ends in accept state with the tape string = the word ...
0
votes
1answer
86 views

Computational power of a Turing Machine with infinite states

Consider a turing machine with infinite states. This machine is identical to a regular machine. Only that number of states could be infinite. Does this machine has more computational power than a ...
-1
votes
1answer
48 views

Does the set ALL_TM contain all Turing Machines?

ALL_TM = { TM | A valid TM } This was a question on my exam. As my choice of answer I went with yes, since the set of all Turing Machines is countable, ( you can produce a binary string for each and ...
0
votes
1answer
43 views

Universal Turing Machine algorithm

First, I learned this based on these facts: Turing machine (TM) will be define with 7-tuple Notation, $M=\langle Q,G,b,S,d,q_0,F\rangle$. Any computation rules that can use to simulate any possible ...
0
votes
1answer
89 views

Algorithmic problem of regular, context-free, and recursively enumerable languages

Consider a language $L_1$ that is recursively enumerate, $L_2$ that is regular, and $L_3$ that is context-free. Are the following problems algorithmically decidable? Is $L_1 \cap L_2 = L_3$? Is $L_1 \...
-2
votes
1answer
46 views

running RAM on a given input

I understand how RAM commands work but I am unable to understand how we use a given input string and find the output. For instance, there's a Random Access Machine which has an input {0,1}*. The ...
0
votes
1answer
44 views

change turing machine to RAM

How can we convert a given Turing Machine into a Random Access Machine? I understand that we can use the transition function to come up with a sort of algorithm but how can we translate all of it into ...
1
vote
1answer
33 views

Why is the following language undecidable?

I'm currently learning for my exams this semester and tried to solve some old exams from the last years. The question is to show, that L ist undecidable. $L=\{w|T(M_w)\neq\emptyset \land \forall x \in ...
0
votes
0answers
46 views

Why is it impossible to iterate over all TMs with $n$ states and $k$ symbols that halt after $m$ steps on $\epsilon$?

Define $\{\sigma(n,k,m,i)\}_{i=1}^{l_m}$ an ordered set of all TMs with $n$ states and $k$ symbols that halt after $m$ steps on $\epsilon$ There are $(2kn)^{kn}$ TMs with $n$ states and $k$ symbols, ...
0
votes
1answer
55 views

Is the problem that determines whenever the word member $\in$ L(M) decidable or not?

Given a Turing machine M on alphabet {m,e,b,r} we're asked to determine if member $\in$ L(M). You must realize that M is not one specific machine and can be any turing Machine with the same alphabet. ...
0
votes
0answers
30 views

Why is there no contradiction when using pumping lemma on a^N b^N a^2N, when k=2?

I have question where it asks: Using the pumping lemma on a^N b^N a^2N, why can you not reach a contradiction when k=2? Here's what I've done, but I do reach a contradiction... u=a^r v=a^s x=a^t b^N a^...
0
votes
1answer
62 views

Provide a polynomial time algorithm that decides whether or not the language recognized by some input DFA consists entirely of palindromes

Everything needed to know is in the question statement. I believe that the DFA has to be acyclic (meaning its language is finite), which can be checked in polynomial time. However, finding all paths ...
1
vote
3answers
95 views

Are files download times actually unknowable due to the halting problem?

When downloading a file from the internet to our computer we are usually prompted with an estimate of how long it will take for the file to be downloaded. From the Halting Problem, we know that $\...
0
votes
0answers
46 views

Existence of a loop in a Turing machine?

Consider a Turing Machine which (1) reads all its input and (2) accepts inputs arbitrarily large. Can we conclude that there must be a loop in the finite-state control as its inputs get larger?
0
votes
0answers
37 views

examples for languages of natural numbers

I need to find examples for language $L_i$ $i\in[1,3]$ of natural numbers that is: $L_1\in$ $RE \backslash R$ $L_2\in$ $coRE\backslash R$ $L_3\in$ $\overline{ R \cup RE}$ My idea was in any case ...
1
vote
1answer
49 views

Speedup with multi-head Turing Machine

What sort of speedup can a Turing machine with more than one head give vs a one-headed machine (I do not mean multiple tapes, I mean multiple heads operating on the same tape making concurrent edits ...
0
votes
0answers
47 views

Is a or free SAT formula NP complete?

Let $L$ be the languague which contains all satisfiable formulas which do not have the or symbol $\lor $. Or more precise $$L=\{\phi | \phi \text{ is a satisfable formula which is only using the ...
0
votes
0answers
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 ?
1
vote
1answer
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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, ...
1
vote
1answer
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 ...
3
votes
2answers
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 ...
0
votes
3answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
37 views

Confusion about definition of languages accepted by Turing Machine, very basic question

I'm studying for an upcoming exam and my book gives the following definition: Let $M$ be a Turing machine, then the accepted language $T(M)$ of $M$ is defined as $T(M) = \{x \in \Sigma^* \mid z_0 x \...
1
vote
1answer
38 views

Is {<M>: L(M) ∈ NP} ∈ NP?

Intuitively I think the answer is no since I don't think every certificate can be checked in polynomial time but I don't know how to give a formal proof. Is the statement true? Why or why not?
0
votes
1answer
28 views

How to define a TM which writes all the tape alphabet, when the number of states is independent of the tape alphabet size?

Given tape alphabet $\Gamma = \{\gamma_1 ,...,\gamma_n\}$ I wish to define a single-taped TM which given the input $\varepsilon$ writes the string $\gamma_1 \gamma_2...\gamma_n$ on the tape, and the ...
0
votes
1answer
81 views

What undecidable language $B$ is reducible to its complement?

I encountered a problem which asks to give an example of an undecidable language $B$ such that $B \leq_m \overline{B}$... However, I could find it hard to construct an example ... my difficulty is ...

1
2
3 4 5
39