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
113 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 ...
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?
2
votes
1answer
355 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
2answers
3k 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?
1
vote
2answers
94 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 ...
8
votes
1answer
230 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
1answer
398 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
564 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
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
134 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 ...
4
votes
3answers
749 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
269 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
4answers
588 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 ...
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
837 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
2answers
273 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) \}$ $...
3
votes
1answer
664 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
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
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
2answers
969 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
313 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
300 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
108 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
113 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
1answer
380 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
2answers
508 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
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
692 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
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
1k 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
2answers
191 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
2answers
155 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
427 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^*...
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
327 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
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
745 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
1answer
162 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
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
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 ...
1
vote
0answers
23 views

Obtaining a graph with no cycles after removing k edges

I am looking for an algorithm that upon an input of a directed graph G and a natural number k,outputs a set of k edges, that upon removing them, the graph will have no cycles. If there are no such k ...
1
vote
1answer
120 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
1answer
47 views

Give an implementation leveldescription of a TM

L = {x=y ⊕ z|x, y, z are binary integers, and x is the XOR of y and z} is non-regular, i.e., no FA exists that could recognize the language. How can I give an implementation level description of a TM ...
1
vote
0answers
329 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
2answers
317 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
2answers
159 views

If a non-deterministic Turing machine runs in f(n) space, then why does it run in 2^O(f(n)) time?

Assuming that f(n) >= n. If possible, I'd like a proof in terms of Turing machines. I understand the reason why with machines that run on binary, because each "tape cell" is a bit with either 0 or 1, ...
1
vote
1answer
462 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 ...