# Questions tagged [turing-machines]

Questions about Turing machines, a theoretical model of mechanical computation capable of simulating any computer program.

220 questions
Filter by
Sorted by
Tagged with
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" ...
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?
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 ...
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 ...
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 ...
388 views

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 ...
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.
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 ...
264 views

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 ?
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 ...
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 ...
307 views

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 ...
111 views

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 ...
288 views

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 ...
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 ...
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 ...
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 |...
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 ...
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 ...
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 ...