# Questions tagged [turing-machines]

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

228 questions
Filter by
Sorted by
Tagged with
4k views

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 ...
3k 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. ...
72 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 ...
652 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 ...
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 ...
197 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 ...
755 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 ...
171 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 ...
797 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 ...
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 ...
112 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 ...
36 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 ...
403 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 ...
118 views

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