# Questions tagged [turing-machines]

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

1,877 questions
Filter by
Sorted by
Tagged with
73 views

69 views

### Is decidability closed under the mapping f where f(a)=f(b)=0 and f(c)=1?

Consider the function $f$ that maps strings over $\{a, b, c\}$ to strings over $\{0, 1\}$ by replacing each $a$ by 0, each $b$ by 0, and each $c$ by 1. For example $f(cabbc) = 10001$. The function $f$ ...
37 views

### Is {<M>: L(M) ∈ NP} ∈ NP?

Intuitively I think the answer is no since I don't think every certificate can be checked in polynomial time but I don't know how to give a formal proof. Is the statement true? Why or why not?
32 views

### Is the discrepancy in Turing's representation of complete configurations intentional?

On page 235 of Turing's 1936 paper, in the figure marked (C), the illustration appears not to match the description. The description states that space has been made on the left of the scanned symbol, ...
34 views

### What undecidable language $B$ is reducible to its complement?

I encountered a problem which asks to give an example of an undecidable language $B$ such that $B \leq_m \overline{B}$... However, I could find it hard to construct an example ... my difficulty is ...
22 views

### How to define a TM which writes all the tape alphabet, when the number of states is independent of the tape alphabet size?

Given tape alphabet $\Gamma = \{\gamma_1 ,...,\gamma_n\}$ I wish to define a single-taped TM which given the input $\varepsilon$ writes the string $\gamma_1 \gamma_2...\gamma_n$ on the tape, and the ...
28 views

### Is the languague L={<M>, M accepts a finite amount of words} decdidable?

Is $L=\{<M> | L(M) \ is \ finite\}$ decidable ? M is a TM. I think its relative simple to proof with the theorem of rice. But I am interested in a solution which does not use the Rice theorem. ...
35 views

### What is a make sense (meaningful) example of language that an unrestricted grammar could generate?

I have learned that: Unrestricted grammar is used to define (or describe) a formal language. Unrestricted grammar is used to define recursively enumerable set [https://en.wikipedia.org/wiki/...
33 views

### simple question about epsilon and estimation turing machines

i am getting really confused by it. i got to a point i had to calculate the lim when $n \rightarrow \infty$ for an optimization problem, and i got to the point that i had to calculate a fairly simple ...
43 views

### Why is this language Turing recognizable and not not-Turing recognizable

I read that the following language is r.e. but not not-Turing recognizable $L$: On input $M$ (where $M$ is a Turing Machine), $M$ accepts at least 20 inputs I am not sure why it is not not-Turing ...
47 views

### decider for a question not clear

This question was asked and answered but I cannot understand the solution. Why is it sufficient to test all strings of |Q| + 1 length? Why should special state q be found? the original question: ...
196 views

### Proving decidability of language

Prove or disprove: The following language $L$ is decidable: $\{ \langle M, t\rangle: M \text{ is a Turing machine and } \forall w \in \{0,1\}^* [M(w) \text{ halts in at most } t \text{ steps} ]\}$ ...
153 views

### Is the leapfrog automata problem in P?

My question is whether a specific decision problem—finding a computation path through a "leapfrog automaton"—is in P or not. It's straightforwardly in NP, and it resembles the hamiltonian ...
21 views

### Mapping reduction from $A_{TM}$ to $INFINITE_{TM}$ same as to $ALL_{TM}$?

I was trying to solve a problem with a mapping reduction from $A_{TM}$ to $INFINITE_{TM}$, and came across a solution that was 100% identical to another solution I saw for $A_{TM} \leq_M ALL_{TM}$. ...
25 views

### Out-Degree of a Configuration Graph

In Chapter 4 in Computational Complexity by Arora and Barak it states, regarding the configuration graph of a Turing Machine, that If M is deterministic, then the graph has out-degree one, and if M ...
### Do all languages in $P$ have polynomial proofs that they are in $P$?
A proof for a language $L$ belonging to a complexity class $C$ can be framed as there existing a verifier $V$ that accepts this proof as the first part of their input and the language as the second. ...
I need to prove $: L=\left\{<M>| M \text { is a } T M \text { and } L(M)=L\left((01)^{*}\right)\right\} \notin R e$ at first observation it looks like it's immediate from Rice's extended Thm, ...