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
0
votes
1answer
33 views

Proving undecidability for a language which contains string with certain syntax

Lets say we have the following problem: $$\mathcal{L}_1 = \{\langle \mathcal{M} \rangle | \mathcal{M}\ \text{is a Turing machine and $\mathcal{L}(\mathcal{M})$ contains a string with exactly three ...
0
votes
0answers
31 views

Can a pushdown automaton solve the halting problem for another Pushdown automaton?

Can a pushdown automaton solve the halting problem for another Pushdown automaton? It's already shown here turing machine can solve the halting problem for a pushdown automaton. Decidability of ...
0
votes
1answer
109 views

What's the complexity class of determing the halting problem of a finite memory Turing machine?

What's the complexity class of determining the halting problem of a finite memory Turing machine? What is the computational complexity class of determining whether a machine halts on any input if it ...
-1
votes
1answer
43 views

Is it possible to construct a Turing Submachine such that a regular turing machine can decide whether the TSM halts but the TSM cannot [closed]

Is it possible to construct a not fully turing complete version of a turing machine such that a regular turing machine can solve the halting problem for the Turing Submachine but the Turing Submachine ...
-1
votes
1answer
31 views

Can enumeration take advantage of non-determinism?

If I want to build an NDTM to enumerate a list (of all Turing machines, for example) is there a way to use non-determinism to "speed this up" or take advantage of it somehow? What types of of r.e. ...
0
votes
0answers
25 views

Program to Translate Turing Machine to Tableau?

Is a program available to translate a Turing Machine program to Boolean tableau format as used for example in proofs of the Cook-Levin theorem?
0
votes
1answer
55 views

Semi-decidability of the language $\overline{L_{\epsilon}}$

Firstly consider the problem: given $L_H = \{R(M)w : M \in TM_0, w\in L(M)\}$ where $R(M)$ are encoded transitions of $M \in TM_0$. Assume for contradiction $\overline{L_{H}}$ is semi-decidable, then ...
1
vote
1answer
32 views

Prove a language is not recursive enumerable

I need to prove $: L=\left\{<M>| M \text { is a } T M \text { and } L(M)=L\left((01)^{*}\right)\right\} \notin R e$ at first observation it looks like it's immediate from Rice's extended Thm, ...
0
votes
1answer
60 views

Do all languages in $P$ have polynomial proofs that they are in $P$?

A proof for a language $L$ belonging to a complexity class $C$ can be framed as there existing a verifier $V$ that accepts this proof as the first part of their input and the language as the second. ...
0
votes
0answers
29 views

TM for Language With a Specific Cardinality

I'm curious about how to build TM that decide and recognize languages defined by cardinality. For example, with the language $L_1$ = $\{w \in \{0,1\}^* | |w| = 1\}$ this is the language with a single ...
0
votes
1answer
52 views

Is $nHALT$ undecidable even if $M$ halts on input $w$ in finite steps

If we have the language $nHALT=\{<M,w,n>;$ $M$ halts on input $w$ in less than $n$ steps$\}$ Is this language also undecidable in the same way that $HALT$ is undecidable? And if so, $nHALT\...
1
vote
1answer
84 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
1answer
84 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
36 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
27 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
107 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 doesn't halt on. Define: $P(M)=\{w\in\Sigma^*|M$ doesn't halt on $w \}$ We know that the $HALT$ problem is $RE\...
2
votes
1answer
73 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(,)$}...
1
vote
1answer
118 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
134 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
25 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
24 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
43 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 ...
0
votes
2answers
122 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
54 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
15 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
77 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
62 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
25 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
415 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
57 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
44 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
57 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
50 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
148 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
42 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
33 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
27 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
81 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
71 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 ...
0
votes
0answers
29 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 ...
0
votes
0answers
11 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
18 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 ...
0
votes
1answer
37 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
55 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. ...
1
vote
0answers
101 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. $...
-1
votes
1answer
25 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
1answer
90 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
37 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
82 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
27 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
3 4
5
6 7
40