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
8
votes
2answers
698 views

How can a cyclic tag system halt with an output?

For example, we can say we have a abstract program that, given a finite binary string as input, removes all of the zeros (i.e. 0010001101011 evaluates to 111111), which is definitely a Turing-...
7
votes
1answer
175 views

$\mathsf{NL}$ versus $\mathsf{NL}[2]$

There is an equivalent definition for the class $\mathsf{NL}$ with verifier. Those verifiers are deterministic Turing machines that can read the witness tape only once in one way from left to right. ...
6
votes
2answers
469 views

Universal binary rewriting system

What is the simplest example of a rewriting system from binary strings to binary strings $$f:\Sigma^*\rightarrow\Sigma^*\qquad\Sigma=\{0,1\}$$ that can perform universal computation? Binary string ...
5
votes
2answers
239 views

Proof of Space Hierarchy Theorem incompatible with Linear Speed Up Theorem for time

In this proof of the Space Hierarchy Theorem the following language is defined $$ L = \{ (\langle M \rangle, 10^k) : M \mbox{ does not accept } (\langle M \rangle, 10^k) \mbox{ using space } \le f(|\...
5
votes
1answer
925 views

How to simulate a bidirectional TM on a regular one with time factor four?

In Computational Complexity A Modern Approach, one claim says that if $f$ is computable in time $T(n)$ by a bidirectional TM $M$, then it is computable in time $4T(n)$ by a unidirectional TM $\tilde{M}...
5
votes
1answer
405 views

For the time hierarchy theorem, how is the input translated efficiently?

I'm trying to understand the proof of the time hierarchy theorem appearing in sipser's book. The proof requires a TM M to simulate an arbitrary TM N without too much slowdown. In particular, it is ...
5
votes
0answers
2k views

Prove that turing machines and the lambda calculus are equivalent

It is known that a turing machine and the lambda calculus are equivalent in power. I now want to try to prove this myself. I think proving that the lambda calculus is at least as powerful as a turing ...
4
votes
1answer
392 views

Is a Turing Machine that only takes strings of the form $0^*$ Turing Complete?

You have a Turing machine that only processes input on the form $0^*$. If it is given an input without 0's, it will simply halt without accepting or do anything else. Is it Turing Complete? The set $...
4
votes
1answer
5k 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?
4
votes
2answers
3k views

simulation of PDA with turing machine

How to simulate a non-deterministic PDA with a turing machine?
4
votes
1answer
2k 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+...
4
votes
2answers
609 views

Can the Lambda Calculus or Turing Machines model signals, callbacks, sleep/wait, or buses?

I have a deep appreciation for formalisms like the Turing Machine and the $\lambda$-Calculus, and enjoy studying them and learning more about how they relate to physical computers. I am now learning ...
3
votes
2answers
549 views

Example of two undecidable languages that cannot be mapping reduced to each other

I want to find two undecidable languages $A$ and $B$ that $A$ cannot mapping (i.e. many-one) reduce to $B$, $B$ cannot reduce to $A$. One of my thought is to let $A$ be the halting problem, let $B$ be ...
2
votes
1answer
3k views

How exactly does a two stack pushdown automaton work?

I have to explain how a 2-PDA works and then write a program (in Delphi) which simulates a 2-PDA step by step for the language $L = \{w\$w\ |\ w ∈ \{0,1\}^n\ with\ n>0\}$. So far, so good. Now I ...
2
votes
2answers
4k views

How can I prove that the language of a read-only Turing machines is regular?

I find this, but I can't complete it, is there any other solution for it?
2
votes
1answer
531 views

If $L$ is recursive then so is $L^*$, and vice versa

Given a language $L$ over the alphabet $\{0,1\}$. Let $L^*= \{ w_1w_2...w_n | n \ge 0, w_1,...,w_n \in L\}$. Prove: If $L$ is recursive, then $L^*$ is recursive as well. If $L^*$ is recursive, then $...
2
votes
1answer
157 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
3answers
6k 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
2answers
726 views

Are nondeterministic algorithm and randomized algorithms algorithms on a deterministic Turing machine?

An algorithm on an abstract machine is a finite sequence of operations of the machine. (Correct me if I am not correct.) However, there are different kind of algorithms, such as deterministic, non-...
2
votes
1answer
209 views

Show that the set of all TMs that move only to the right and loop for some input is decidable

I am trying to prove that $\qquad L=\{\langle M\rangle \mid M \text{ is a TM }, \exists w. \text{ in } M(w) \text{ the head moves only right and } M(w)\!\uparrow \}$ is decidable. I thought about ...
2
votes
1answer
148 views

Are there any practical differences between a Turing machine with a PRNG and a probabilistic Turing machine?

Say I plugged in a hardware true-random number generator (TRNG) to my computer, then wrote programs with output that depends on the TRNG's output. Can it do anything non-trivial that a Turing machine ...
1
vote
2answers
240 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
2answers
2k 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
2answers
56 views

Are decidable set/languages EQUIVALENT to type 1 grammars (non-contracting)?

Suppose a Turing Machine (TM_G) that generates natural numbers following < or, equivalently, it generates words in lexicographical order. Then, that language/set is decidable. Because it is trivial ...
0
votes
2answers
5k views

ETM Undecidability

I'm having trouble convincing myself of the proof for the following theorem: $E_{TM} = \{\langle M\rangle\mid M$ is a TM and $L(M) = \emptyset\}$ is undecidable. I think I understand why we reduce $...
8
votes
1answer
331 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 ...
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 ...
6
votes
2answers
180 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 ...
6
votes
1answer
3k views

Is it possible to prove EQTM is undecidable by the Rice theorem?

Given the problem $EQ_{TM} = \{ \langle M_1, M_2\rangle \mid M_1 \text{ and } M_2 \text{ are } TM, L_{M_1} = L_{M_2}\}$, is it possible to prove that this is undecidable by using (a variant of) Rice ...
6
votes
1answer
438 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
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
570 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. ...
5
votes
1answer
5k 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
85 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 ...
4
votes
3answers
853 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
1k 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
308 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
2answers
339 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
4answers
750 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 ...
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 ...
3
votes
2answers
805 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 ...
3
votes
1answer
49 views

surprizing reducibility and challenge on it

Assume that Problem $A$ is polynomial-time reducible to problem $B$. Claim 1: If problem $A$ is NP-hard then problem $B$ is NP-hard. Claim 2: If problem $B$ is NP-hard then problem $A$ is NP-hard. ...
3
votes
1answer
886 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
2answers
1k 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 ...
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
4k 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. ...
3
votes
1answer
3k 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
476 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 = \...
2
votes
2answers
396 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
65 views

Can you build a solver from a verifier?

Given code to just an NP-verifier, where the certificate/witness is required to be of size polynomial in the instance, for a language L, can you, from that data alone, construct code for a solver, or ...