Questions tagged [turing-machines]
Questions about Turing machines, a theoretical model of mechanical computation capable of simulating any computer program.
1,803
questions
0
votes
1answer
22 views
How to enumerate all Turing machines?
Why is this true: “There are countably many Turing Machines”
In the top answer for this question a description of how to enumerate all Turing machines is given.
It all is clear except for one part: ...
-2
votes
0answers
15 views
Elements of Theory of Computation 2nd Turing Machine
What is the answer to the question below ?
Elements of Theory of Computation 2nd Turing Machine Question Page 193 4.1.8
1
vote
1answer
24 views
How does an enumerator for machines for languages work?
In Dexter C. Kozen - Theory of Computation (2006, Springer) page 319 exercise 127 he says :
"A set of total recursive functions is recursively enumerable (r.e.) if there exists an r.e. set of indices ...
0
votes
1answer
16 views
How do you represent an r.e. complexity class with a list of TMs?
In this book ‘Theory of computation’ By Dexter Kozen on page 313,exercise 127 he says "A set of total recursive functions is recursively enumerable (r.e.) if there exists an r.e. set of indices ...
0
votes
1answer
23 views
Methods for enumerating an enumerable set of languages? [closed]
Given an enumerable collection of languages, what are the different ways you can enumerate them? Ex: I've heard you can enumerate them by the machines that compute them--how do you do this tho? What ...
0
votes
1answer
16 views
Can a DTM simulate an enumerator E?
An enumerator is defined as a 7-tuple:
https://en.wikipedia.org/wiki/Enumerator_(computer_science)
A Deterministic Turing machine is defined as a 7-tuple:
https://en.wikipedia.org/wiki/Turing_machine
...
0
votes
1answer
61 views
“problematic” non-halting inputs for turing machines
Let us start this question out, by defining for a turing machine, the set of words it doesnt halt on.
Define: $P(M)=\{w\in\Sigma^*|M$ doesnt halt on $w \}$
We know that the $HALT$ problem is $RE\...
2
votes
1answer
47 views
Expressing functions using the arithmetic dictionary
i have seen in the "logic to cs" class i take - a theorem that states: "every recursive (computable) function $f$ can be expressed using the arithmetic dictionary {$C_0, C_1, f_+(,), f_x(,), R_\le(,)$}...
0
votes
1answer
38 views
Check if language is decidable
I would like to determine if the following language is decidable or not.
L = { w $\in$ $\Sigma^*$ | $T(M_w)$ is recognized by a Turing machine with at most 42 states}.
I know that every finite ...
2
votes
1answer
122 views
Combining 2 problems in NP into one
Say I have a deterministic turing machine which solves decision problem S with oracle access to both problems B, C that are in $NP$.
Can S be solved with oracle access to only one problem in $NP$?
...
1
vote
1answer
22 views
Is reaching in less lines semi-decidable?
Assuming we have two programs $p_1$ and $p_2$ and two line numbers $n_1$ and $n_2$. Does $p_1$ reach $n_1$ in less computational steps than $p_2$ reaches $n_2$? By reduction from Halting, this is ...
0
votes
2answers
19 views
Turing Recursive Definition vs General Perception
So what confuses me is that let's consider a function f. According to a definition from a text book it asserts that f is called recursive, if there is a Turing machine that computes it (for all input ...
1
vote
1answer
27 views
How should we define the behavior of a Turing machine where the head tries to move left from the leftmost tape position?
If we have a Turing machine in a model with a tape that is infinite only to the right and assume at some point the head tries to move left from the leftmost position.
How should we define the ...
-1
votes
0answers
35 views
is Etm mapping reducible to Atm?
is Etm mapping reducible to Atm?
As i know Atm is not mapping reducible to Etm, but how about the Etm mapping reducible to Atm?
0
votes
2answers
94 views
Is $MIN_{TM}$ not in $\overline{RE\cup coRE}$
Given the language:
$MIN_{TM}$= $\{ \langle M,k\rangle: there\ exists\ a\ TM\ D\ s.t.\ L(M)=L(D)\ and\ D\ has\ less\ than\ k\ states \}$
I need to prove if this language is in $R$ or $RE-R$ or $...
1
vote
1answer
36 views
Turing machine that can move right only $O(1)$ steps beyond input
I need to prove that a Turing machine that can move only $k$ steps on the tape after the last latter of the input word is not equal to a normal Turning machine.
My idea is that given a finite input ...
0
votes
0answers
14 views
Question on the decidable of Turing Machine
I am a bit confused about using the subset of the turning machine to prove the desirability of the turning machine.
If I have a Turing Machine M and we have already know M has a single halting state. ...
1
vote
1answer
38 views
Is solving a quadratic equation using Turing machine impossible?
I've just started Algorithms at university. There's a task to write an algorithm for a Turing machine to solve quadratic equations. The task doesn't specify if it's x^2+bx+c or ax^2+bx+c. I've ...
1
vote
1answer
50 views
Turing machine with a finite tape after the input word ends
How can I prove that for a natural number K, a language that accepted by a Turing machine with K cells after the input word ends, belongs to R (which R is the set of languages that there is Turing ...
1
vote
1answer
24 views
Is $P$ defined for TM which decide or accept a language?
Sipser defines $TIME(t(n))$ as the set of all languages that are decidable by an $O(t(n))$ time TM and then $P = \bigcup_k TIME(n^k).$
However I see also many definitions like
$$
P = \{ L \mid \text{...
1
vote
1answer
203 views
Decidability of Turing machines that never move their heads past any input string
$L_1 = \{ \langle M, w\rangle : M \text{ is a TM that never moves its head past the input string } w \}$
$L_2 = \{ \langle M\rangle : M\text{ is a TM that never moves its head past any input string} ...
0
votes
2answers
49 views
Is it possible to design a Turing Machine without extra symbols for this language?
Is it possible to design a Turing Machine for the language defined as L = {0n1n | n >= 0} with only the symbols in the set of {blank, 0, 1}?
0
votes
2answers
32 views
proving $E_{TM}$ is undecidable using the halting language
How to prove that:
$E_{TM} = \{\langle M\rangle\mid M \ is\ a\ TM\ and\ L(M)=\emptyset\}\notin R$
(is undecidable)
using the language:
$H_{halt}=\{(⟨M⟩,w):M\ halts\ on\ w\}$.
I tried to prove by ...
0
votes
1answer
39 views
If $L1⊆L2$, and $L1\not∈RE$, is it possible that $L2∈RE$
If $L1⊆L2$, and $L1\not∈RE$, is it possible that $L2∈RE$ ?
Also I find it hard to find languages that are not in RE at all, I've heard about Arithmetical hierarchy but we didn't really learnt it in ...
0
votes
2answers
28 views
Turing Machine state going to itself
Hey guys in a turing machine can a state go to itself by reading a letter. For example,
q2 reading a 'c' to go to itself. Is that possible?
Or does it need to read a tape alphabet, such as $ to ...
-1
votes
2answers
39 views
Is determining if a Turing Machine stops for at least one entry decidable?
I can't find how to prove the decibility with a reduction.
EDIT:
I've tried the reduction from the halting problem and the aceptance problem. Stopping for at least one entry has infinite inputs (you ...
0
votes
0answers
30 views
Is the undecidability of a given problem undecidable?
Given an input problem P, can you construct an algorithm A to compute whether or not P is decidable or undecidable? In other words, is the undecidabiliy of a problem undecidable? My initial guess is ...
0
votes
1answer
26 views
How to build a TM which decides $L_k := \{(\langle M \rangle ,x)\in HP : |(\langle M \rangle ,x)| \le k \}$
For a specific natural $k$ we define the language of couples $(\langle M \rangle, x)$ such that $M$ stops on $x$ and the couple's encoding is bounded by $k$ i.e $L_k := \{(\langle M \rangle ,x)\in HP :...
0
votes
1answer
21 views
ODEs and Zeno Machines
Disclaimer: I know nothing about differential equations, and I don't know if this belongs here...
Wikipedia states that a Zeno machine is a hypothetical machine able to compute infinite
steps in ...
-1
votes
2answers
65 views
Halting problem - What if the halting algorithm gave more than one output?
Sorry I don't know how silly a question this might be, but i've been reading up on the halting problem lately, and understand the halting problem cannot possibly output a value that is "correct" when ...
1
vote
1answer
26 views
Reduction from $HALT$ to $A_{TM}$
I know the reduction to from $A_{TM}$ to $HALT$. But is
the following reduction from $HALT$ to $A_{TM}$ correct?
We are looking for total computable function $f$ mapping from $HALT$ to $A_{TM}$.
The ...
1
vote
0answers
21 views
Design of a single-tape NTM solving the TSP in $O({n}^4)$ time at most
I was going through the classic text "Introduction to Automata Theory, Languages, and Computation" by Hofcroft, Ullman, Motwani where I came across a claim that a "single-tape NTM can solving the TSP ...
1
vote
0answers
8 views
Logic of the squared running time in “A Variant of Nondeterministic Acceptance”
I was going through the classic text "Introduction to Automata Theory, Languages, and Computation" by Hofcroft, Ullman, Motwani where I came across the following claim:
A Variant of ...
1
vote
0answers
14 views
Mathematics of the upper bound for the encoded input of an instance Kruskal's MWST problem
I was going through the classic text "Introduction to Automata Theory, Languages, and Computation" by Hofcroft, Ullman and Motwani where I came across the encoding of an instance of Kruskal's Mininum ...
-4
votes
0answers
22 views
Suppose you want to define a new model of computation called a “Turing-Stack Machine” (TSM)
Suppose you want to define a new model of computation called a “Turing-Stack Machine” (TSM). The idea is that a TSM would have all the components of a deterministic Turing machine, but also a stack (...
0
votes
1answer
35 views
About computable sets
Let TOT be the set of all Turing Machines that halt
on all inputs.
Find a computable set B of ordered triples such that:
TOT = {e : ($\forall$x)($\exists$y)[(e, x, y) $\in$ B]
This definition means ...
2
votes
1answer
42 views
All problems about Turing machines that involve only the language that the TM accepts are undecidable
I came across the below statement in the classic text "Introduction to Automata Theory, Languages, and Computation" by Hopcroft, Ullman, Motwani.
...
2
votes
0answers
30 views
Rice theorem, the proof of the part when the empty language belongs to the property
I was going through the classic text "Introduction to Automata Theory, Languages, and Computation" by Hofcroft, Ullman and Motwani where I came across the proof the Rice theorem as shown.
$L_u$ => ...
0
votes
1answer
20 views
Probabilistic Turing machine - Probability that the head has moved k steps to the right on the work tape
I have a PTM with following transition:
$\delta(Z_0, \square , 0) = \delta(Z_0, \square , L, R)$,
$\delta(Z_0, \square , 1) = \delta(Z_0, \square , R, R)$
Suppose that this PTM executes n steps. ...
0
votes
0answers
31 views
What is the semantics of a Turing machine?
Can we formalize the operational/denotational semantics of a Turing Machine? Is there any formalization in literature?
1
vote
1answer
21 views
Is there a way to hash a turing machine?
If we have a Turing machine with various $\delta(q_i, a_i) = (q_j, a_j, Direction)$ where Direction can be L or R(denoting the movement of head), can we encode it uniquely to some natural number(which ...
1
vote
1answer
56 views
Is it possible to make a Turing Machine that accepts the language $\{\alpha\alpha\alpha | \alpha \in \{a, b\}^∗\}$?
I'm having a lot of problems trying to make a Turing Machine that accept that language, is it even possible to make it? and if so, how can I proceed to make the Turing Machine?
1
vote
1answer
24 views
One-way function is not injective when it is in NP
Let us $\Sigma = \{0,1\}$ and $f: \Sigma^* \rightarrow \Sigma^* \in FP$ for which is valid that $\exists k: \forall x \in \Sigma^* : \lvert x \rvert ^ {1/k} \leq \lvert f(x) \rvert \leq \lvert x \...
1
vote
0answers
40 views
Do we alter the input string when converting a multi-tape Turing Machine to a single-tape Turing Machine?
I'm having difficulty understanding the conversion from a multi-tape Turing Machine $M$ to a single-tape Turing Machine $S$. Suppose that $M$ has 3 tapes with input strings $w_1 = 0110$, $w_2 = aaba$, ...
0
votes
0answers
25 views
Can a halting configurations of a Turing Machine has the same state of another configuration has?
At first, I believed since the state a halting configuration is at will be a halting state, whenever a configuration goes into that state, the TM halts.
Hence, there should not exist two ...
0
votes
0answers
25 views
If T is a Turing Machine, what are the languages Accept(T), Reject(T) and Loop(T)?
I have the following Turing machine:
I am asked what are the langauges accept(T), reject(T) and loop(T).
This seems to me a trivial question as from the looks of it, accept(T) is the language of all ...
0
votes
2answers
41 views
How could you “solve” the halting problem if, hypothetically, the busy beaver numbers were “small”?
I read that if BB(n) did not grow faster than all computable sequences of integers, you could solve the halting problem and contradict Turing's theorem.
I'm trying to figure out how you could ...
0
votes
0answers
16 views
Using multiple deciders in a Turing machine
I want to construct a Turing machine that compares two different decidable Languages in some way (e.g. $L_a$ and $L_b$). Suppose we have the deciders $M_a$ and $M_b$ for these languages.
Am I allowed ...
1
vote
3answers
41 views
What does “Every CFL is decidable” exactly mean?
I am trying to prove the fact that every CFL is decidable, however I can't come to terms with what the statement exactly means.
I know that generation of a particular string by a given CFG is a ...
0
votes
0answers
13 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}$. ...
