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
1answer
7 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
19 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
37 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 ...
-1
votes
1answer
53 views

Prove that a language is decidable

I need some help to prove that the language is decidable. $K$ = {$N$ : $N$ is a DFA (Sigma = {a, b, c}) and $L$($N$) contains at least one word in which there is no a}. It tried to make an algorithm ...
1
vote
2answers
108 views

Turing Machine - Analyze brackets

For a practical task, we are asked to provide the transition table for a Turing machine that validates the number of open brackets is equal to the number of closing brackets. The only tape symbols ...
0
votes
1answer
27 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
19 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
51 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. ...
1
vote
1answer
57 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 ...
0
votes
0answers
32 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
2answers
233 views

How to prove that {<M1, M2> : M1 and M2 are two DFAs and L(M1) $\neq$ L(M2)} is in NL?

My idea is to find a turing machine which recognizes this language in $\log N$ space, could anyone give me some clue on how to find such turing machine?
1
vote
1answer
119 views

How to translate automaton (Turing machine) into the program of high level programming language?

Every program in high level ("industrial") programming language can be expresses as some Turing machine. I guess, that there exists universal algorithm for doing that (e.g. one can take the Cartesian ...
0
votes
3answers
86 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 ...
2
votes
4answers
444 views

To what extent is an x86 machine equivalent to a Turing Machine?

To what extent is the abstract model of computation specified by the x86 language Turing complete? The above question is related to this question: Is C actually Turing-complete? In theoretical ...
1
vote
1answer
263 views

Trading States for Symbols with a Turing Machine

Show that for each string $w ∈ \{0, 1\}^∗$ there exists a stay-put Turing machine $$M_w = (Q, \{0, 1\}, \Gamma, \delta, s, q_{\mathit{accept}}, q_{\mathit{reject}})$$ with $|Q| ≤ 5$ states that ...
1
vote
0answers
41 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
2answers
634 views

turing machine for the language L ={w#w' where w<w'}

I'm blocked with a question for a long time. L ={X=w#w' where w < w' and w,w' in {0,1}* } So i'm trying to find : 1-a deterministric turing maching for the language L. 2-a non deterministic for ...
1
vote
1answer
89 views

Prove a TM problem is NP-complete

Question: Show that $T_{NP}$ is NP-complete, where $$T_{NP} = \{m\#w\#^c\mid M_m\text{ is an NTM};M_m(w)\text{ has an accepting computation of $\leq$ c steps}\}$$ This question looks weird to me ...
0
votes
1answer
60 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 ...
3
votes
1answer
86 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
62 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
2answers
1k views

Show that the single-tape TMs that can not write on the portion the portion of the tape containing the input string recognize only regular languages

Show that the single-tape TMs that can not write on the portion the portion of the tape containing the input string recognize only regular languages. The first part of the answer in a book said that: ...
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 ...
1
vote
1answer
60 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 ...
0
votes
1answer
62 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 ...
0
votes
0answers
11 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 ...
-1
votes
0answers
28 views

If a language has an alternate enumerator then is L a decidable language

Let L be a non trivial language above alphabet sigma and L is not empty of sigma^* An alternate Enumerator for Language L is an enumerator that prints an infinite series of words: w1,w2,... in which: ...
3
votes
3answers
2k views

Show a TM-recognizable language of TMs can be expressed by TM-description language of equivalent TMs

I am studying "An Introduction to the Theory of Computation" by Sipser -- there is a problem *3.17 (p.161) which I can not solve. Any hints (not answers) from which side to attack it? Let $B=\{M_1,...
4
votes
1answer
174 views

Who was the first to show that there is a Universal Turing-Machine that uses a binary alphabet?

The title says it all, I think. We know there are universal Turing-machines that only use a binary alphabet. But who proved this first? Turing himself showed the existence of a universal Turing ...
1
vote
1answer
833 views

How would a Turing Machine recognize n consecutive characters

I have difficulties understanding how a TM could count number of characters. I have this problem where the input is made out of characters $\{a, b\}$ and I need to accept if there are $n$ characters ...
-1
votes
1answer
46 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 ...
1
vote
1answer
58 views

Design a Turing Machine which accepts strings $x \# y$ where $x \ge y$

Imagine you are designing a TM where $x$ and $y$ are binary representation( $x \ge y$). the TM should accept $1101\#1001$ and reject strings such as $110\#10001$, as well as it could reject if you ...
0
votes
1answer
32 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 \...
0
votes
1answer
27 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
77 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 \...
1
vote
2answers
227 views

Can I apply Rice's theorem to decide decidability status of these languages?

I came across these languages: A Turing machine prints a specific letter. A Turing machine computes the products of two numbers I was guessing whether I can apply Rice's theorem to decide upon above ...
0
votes
1answer
40 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 ...
7
votes
6answers
6k views

The first Turing machine

Does anyone know how efficient was the first Turing machine that Alan Turing made? I mean how many moves did it do per second or so... I'm just curious. Also couldn't find any info about it on the web....
-2
votes
1answer
43 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
210 views

Proving decidability of language

Prove or disprove: The following language $L$ is decidable: $\{ \langle M, t\rangle: M \text{ is a Turing machine and } \forall w \in \{0,1\}^* [M(w) \text{ halts in at most } t \text{ steps} ]\}$ ...
1
vote
1answer
31 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
1answer
31 views

Mapping reduction from $A_{TM}$ to $INFINITE_{TM}$ same as to $ALL_{TM}$?

I was trying to solve a problem with a mapping reduction from $A_{TM}$ to $INFINITE_{TM}$, and came across a solution that was 100% identical to another solution I saw for $A_{TM} \leq_M ALL_{TM}$. ...
1
vote
3answers
93 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
43 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, ...
1
vote
1answer
51 views

Why there is no Turing Machine that accepts the Diagonal Language?

Given the diagonal language $$L_d = \{ i : \sigma_i \notin L(M_i) \}$$ Where $M_i$ are all Turing Machines and $\sigma_i$ are all the words, if you put in in a Matrix like this: $$\begin{array} {|c|c|...
0
votes
1answer
51 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. ...
1
vote
1answer
81 views

How to conceive a Turing machine that is the intersection of the languages of two Turing machines?

We have $ M = (Q,Σ,Γ,δ,q_0,q_a,q_r) $ and $ M′= (Q′, Σ , Γ′, δ′,q_0′,q_a′,q_r′)$. We want to construct a standard Tm that recognize L(M) ∩ L(M′). How do I go about it? I don't have much more ...
0
votes
2answers
111 views

Decidable questions of undecidable problems

Even if there is no general algorithm to decide if any program will halt, but there could be properties or meta-questions about the programs that is decidable. For example, given program $A$ and a ...
0
votes
1answer
52 views

Oblivious Machines and Input Dependency

So I know the Oblivious Turing Machines head position depends on the size of the input word and a number of steps. Can it be modified in such a way that it's not dependent on the size of the input ...

1
2 3 4 5
38