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
2
votes
1answer
118 views

Has this generalization of Turing machines studied before?

Introduction Hello, I'm designing a generalized model of Turing machines for a formalization in MIZAR. Mizar needs some concrete objects to work with, so I spent some time figuring out how the "tape" ...
2
votes
1answer
4k views

If a set S is infinite and recognizable, is there an infinite subset of S that is decidable?

If a set S is infinite and recognizable, how can I prove that, if any, some subsets K is infinite and decidable? how about infinite and recognizable?
1
vote
2answers
235 views

Can we convert any given turing machine to a turing machine with only 2 states? if so, how?

So i remember reading somewhere that we can convert any turing machine into a turing machine with 2 states (or 3, i don't remember) but there was no proof for it and i couldn't find it either So my ...
7
votes
2answers
2k views

Can you do an in-place reversal of a string on a vanilla turing machine in time $o(n^2)$?

By a vanilla Turing machine, I mean a Turing machine with one tape (no special input or output tapes). The problem is as follows: the tape is initially empty, other than a string of $n$ $1$s and $0$s ...
7
votes
1answer
208 views

Why do we reject turing machines that use space less than the log of the length of the input?

In Computational complexity: Modern Approach by Arora and Barak, it's mentioned that We will require however that $S(n)> \log n$ since the work tape has length $n$, and we would like the ...
6
votes
1answer
388 views

Show that the halting problem is decidable for one-pass Turing machines

$L=\{<\!M,x\!>\, \mid M's \text{ transition function can only move right and } M\text{ halts on } x \}$. I need to show that $L$ is recursive/decidable. I thought of checking the encoding of $...
5
votes
2answers
130 views

Countably many oracle Turing machines?

In Sipser's text, when proving that there exists an oracle $A$ such that $P^A \ne NP^A$, he writes: Let $M_1, M_2, \ldots$ be a list of all polynomial time oracle TMs. I understand that there are ...
5
votes
1answer
1k views

How to convert a Turing Machine program to a tiling using Wang Tiles?

This is a cross-post from a post on MathSE due to lack of answers. To illustrate my question I provide the following example. The website Online Turing Machine provides a Turing Machine simulator. ...
5
votes
2answers
563 views

Do I need to consider instance restrictions when showing a language is in P?

I have already shown that 3-colorable for an unrestricted graph is in NP, but I was thinking about the similar language defined as the set of all acyclic $G$, where $G$ such that $G$ is 3-colorable. ...
4
votes
2answers
265 views

Intuition about decidability

Given a language, how do you go about deciding if it's decidable or not? For example: Given a DFA $A_0$ and a TM $M_0$ $L_1 = \{ \langle M \rangle \, | \, M \mbox{ is a TM and }L(M) = L(A_0) \}$ $...
4
votes
3answers
733 views

Can a transcendental number like $e$ or $\pi$ be compressed as not algorithmically random?

The related and interesting fields of Information Theory, Turing Computability, Kolmogorov Complexity and Algorithmic Information Theory, give definitions of algorithmically random numbers. An ...
4
votes
1answer
795 views

Prove that the Language is Recognizable

I got stuck on this question while studying for final exam. I thought about reducing L' to L to prove that L' is recognizable since L is recognizable. I am not 100% sure if that is correct.
4
votes
1answer
4k views

A string representation of any Turing machine

The set of all Turing machines is said to be countable. The central idea of the proof of this fact is that every Turing machine can be written as a finite string of characters. I am having trouble ...
4
votes
1answer
264 views

Simulate NPDAs with DTMs using only polynomial overhead

We know by polynomial-time parsing algorithms like the classical CYK algorithm that $\mathrm{CFL} \subseteq \mathrm{P}$. Furthermore, it is easy to show by direct simulation that $\mathrm{DCFL} \...
4
votes
3answers
2k views

Proving that recursively enumerable languages are closed against taking prefixes

Define $\mathrm{Prefix} (L) = \{x\mid \exists y .xy \in L \}$. I'd love your help with proving that $\mathsf{RE}$ languages are closed under $\mathrm{Prefix}$. I know that recursively enumerable ...
4
votes
4answers
573 views

Can Turing Machines solve non-decision problems?

Since TMs are equivalent to algorithms, they must be able to perform algoriths like, say, mergesort. But the formal definition allows only for decision problems, i.e, acceptance of languages. So how ...
3
votes
1answer
1k views

Blank tape halting problem vs. Emptiness problem ($H_0$ vs. $E_{TM}$)

I have difficulties to differentiate the $H_0$ from the $E_{TM}$ problem. What exactly means $L(M)= \emptyset $? Is it dffierent from $input~ \varepsilon$ or is $L(M)= \emptyset \leftrightarrow input~...
3
votes
1answer
2k views

simulation of PDA with 2-tape Turing machine [closed]

Can someone give me suggestions how can I construct a 2-tape Turing machine which simulates PDA ?
3
votes
1answer
639 views

Is Turing machine a programmable machine or Is it like a fixed program computer?

We all know Random Access Machine (RAM) models are programmable machines. We can program a same machine for different problems with the help available instruction set. But in the case of Turing ...
3
votes
1answer
49 views

Mapping many transition functions into two transition functions

Continuing from this answer: https://cs.stackexchange.com/a/56072/43035 I don't understand how it's possible to map many transition functions $\delta_1,...,\delta_n$ of a NDTM into just two ...
3
votes
1answer
307 views

Proof by Turing Reduction

I need to proof the following by turing reduction. Given two languages: $Q= \{(\langle M_1 \rangle , \langle M_2 \rangle ) \mid L(M_1) = L(M_2)\}$ $I= \{\langle M \rangle \mid \;\vert L(M) \vert = \...
3
votes
2answers
944 views

What is a Turing Machine in class coNP

On the wikipedia article about the polynomial hierarchy http://en.wikipedia.org/wiki/Polynomial_hierarchy it says "$A^B$ is the set of decision problems solvable by a Turing machine in class A ...
2
votes
1answer
1k views

How many Turing machines are there with $c$ characters and $n$ states?

By $c$ character I mean the numbers $0,\dots,c-1$ and the blank symbol $b$, and by $n$ states I mean $n$ non-accepting states, reject and accept. We can assume every $n$-state Turing machine has $(c+...
2
votes
1answer
964 views

What is a standard way to construct a turing machine for any function to compute

I am new to turing machines, I am having problems with mapping a function to a turing maching that computes that particular function. for example: f(x) = 2x + 3 n>= 0 MIN(x,y) leaves the smallest ...
2
votes
1answer
111 views

Why would $NP^ {SAT} \subseteq P^{SAT[O(\text{log }n)]}$ imply that $PH \subseteq P^{SAT[O(\text{log }n)]} $

I was reading the following paper by Jim Kadin, "$P^{NP[O(\text{log } n)]}$ and sparse Turing complete sets for NP" The main result is that if there is a sparse set $S \in NP$ such that $coNP \...
2
votes
2answers
1k views

Turing Machine remembering copied symbols

So, I know that any multiple-tape TM can be in theory turned into a one-tape TM. However, it is too easy to copy, let's say, binary numbers from one tape to another. That's why I thought about putting ...
2
votes
2answers
147 views

Can a TM recognize whether another TM recognizes a non-empty language?

Let $$L_1 = \{\langle M\rangle\mid M \text{ is a Turing Machine and }L(M)\ne\emptyset\}.$$ Is $L_1$ recognizable? If so, can you give me a pseudo-algorithm? My attempt: I wanted to study ...
2
votes
1answer
156 views

A new definition of recursively enumerable set?

Given a Turing machine $M$, we associate a partial function $f_M : \Sigma^{\ast} \to \Sigma^{\ast}$ to it (this is called the function computed by the machine), where $\Sigma$ denotes the finite input ...
2
votes
2answers
682 views

Non-erasing Turing machines and loss of generality

A non-erasing Turing machine is one that cannot replace a symbol with a blank unless the symbol under the read head is a blank. I'm trying to understand whether there is loss of generality because of ...
2
votes
2answers
186 views

Reducing recursive languages

I need a clarification related to the following situation. Consider a Turing machine $T_1$ that halts for every input. In other words $J_1 = L(T_1) \subseteq \Sigma^*$ is recursive. Suppose we are ...
2
votes
1answer
110 views

Completeness problem of TM

$L = \{ \langle M \rangle \mid L(M) = \Sigma^∗ \}$ Is above problem R.E ? I found an explanation in one of the websites and I have doubt in few lines of paragraph. The explanation was Now, given a ...
2
votes
1answer
358 views

Space requirement of a universal Turing machine

Given a representation $g$ (e.g. the Gödel number) of a Turing machine $B$, a universal Turing machine $A$ can simulate $B$. If $B$ is restricted to using at most $n$ memory cells of its tape and the ...
2
votes
1answer
2k views

What is the complement of Halting Problem?

I understand that Halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever. ...
2
votes
1answer
96 views

Prove the languages |L<M>| = 2 and |L<M>| $\not=$ 2 to be non-Turing recognizable or non-recursively enumerable

I am trying to prove the non-recursively enumerable property of two languages. $L_2 = \{\langle M \rangle: |L\langle M \rangle| = 2\}$ and $L_{\not=2} = \{\langle M \rangle: |L\langle M \rangle| \not=...
2
votes
1answer
34 views

Can an alphabet be extended in a reduction proof? (with sample problem)

So I am working on solving a problem on whether following language is decideable: $L = \{n \in \mathbb{N} \mid M_n$ never freezes (for any input)$\}$, where $n$ is the Gödel-number of a Turing ...
2
votes
2answers
288 views

What is the relationship between oracle Turing machine $M^O$ and Turing machine $M$ (given $O$)?

An oracle Turing machine (OTM) $\bar{M}$ can be denoted $M^{O}$ if it is a Turing machine (TM) $M$ with an oracle $O$. Given the oracle $O$, there exists a relation $R$ between OTMs and TMs such that $...
2
votes
1answer
741 views

Proving Equivalence of 1-dimensional Cellular Automaton and Turing Machines

I'm considering an automaton $A$ over a alphabet $\Sigma$, with a set of states $Q$, such that $\Sigma \subset Q$, which includes special "accept" and "blank" states not in $\Sigma$. It also has an ...
2
votes
2answers
475 views

A two-tape deterministic Turing machine that recognizes an exponential string

How can I describe a Turing Machine recognizing the language $P=\{a^{2^n} | n \geq 0 \}$? This Turing Machine is deterministic and uses two tapes, both bidirectional and R / W (read & write) The ...
2
votes
1answer
3k views

Turing machine and language decidability

The document I am reading is here: Turing Machines Before getting into the question, here is the notation used on the picture: Here $\Delta$ denotes the blank and R, L and S denote move the head ...
2
votes
1answer
312 views

Language is non-empty is recursively enumerable (intuitive way) [duplicate]

$M$ is some Turing machine, $\left<M\right>$ is the code of the Turing machine. $L =\{\left<T\right> | L(T) \ne \emptyset\}$ How to see intuitively that $L$ is partially decidable? We ...
2
votes
3answers
5k views

Turing machine for $a^i b^j$ with $i \geq j$

I would have a brief question about how to construct a Turing machine that is accepting only this language: $\qquad\displaystyle L_2 = \{a^i b^j \mid i \geq j \}$. I can't come up with any mechanism ...
2
votes
1answer
409 views

How can a Turing machine run another machine for an infinite amount of strings?

The proof in my textbook, that $E_{TM}$ can be decided by oracle machine $O^{A_{TM}}$, uses a Turing machine $P$ such that for an input $w$: $P$ runs the Turing machine $M$ on all strings of $\Sigma^*...
1
vote
2answers
80 views

Why is the run time of an $f(n)$ space decider bounded by $2^{O(f(n))}$?

In the proof of Savitch's theorem from the 3rd edition of Sipser's Intro to Theory of Computation, Sipser claims that the maximum time that an $ f(n) $ space nondeterministic Turing machine that halts ...
1
vote
1answer
453 views

DTM that halts on a minimum one input

I am trying to show that this is Turing Recognizable. The language A, that is a DTM, T, that halts on a minimum of one input. My justification is that of course it is because, you just need to check ...
1
vote
0answers
172 views

A question about $O(T \log T)$ simulation of a TM on some input by universal turing machine

In the textbook by Arora and Barak in Chapter 1 and section 1.7 they have proved how a UTM can do simulation in $O(T \log T)$ time. I have read it and understood everything except that how the $k$th ...
1
vote
1answer
114 views

Construct this two-taped Turing Machine {(u#,v#):u,v E {a,b}* , |u| = 2|v|}

I am having troubles trying to create this two-taped Turing Machine, I understand how I would get it to accept 2 strings of equal length. But to move forwards, I dont know how I would check to see if |...
1
vote
2answers
310 views

Variant of Turing machine

How to prove that standard Turing machine is equivalent to a variant model where a string is accepted if the machine enters an accept state during computation? However, the machine may leave the ...
1
vote
0answers
325 views

Is there a name for a useful Turing-like machine that is more powerful (meaning accepts more languages) than a Turing machine?

Disclaimer: I'm a software engineer with only an undergrad education and have never published or anything so please forgive any minor notation or jargon blunders - but of course feel free to point ...
1
vote
1answer
120 views

NP and verifiability equivalence - does this guarantee that any certificate can be verified in polynomial time?

As a follow-up from my old question here, I'm wondering more about the equivalence proof. Intuitively, NP has been described as the class of all problems which a solution certificate can be verified ...
1
vote
1answer
2k views

How does this non-deterministic algorithm to find if a Hamiltonian path exists work?

I have read of an algorithm that a non-deterministic Turing machine $N$ can run to determine whether a given graph $G$ has a Hamiltonian path from the start node $s$ to a certain node $n$: Write a ...