# Questions tagged [turing-machines]

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

1,660 questions
Filter by
Sorted by
Tagged with
17 views

### Maximum Query String Length in Oracle Turing Machines

I am learning oracle Turing machines, which is normal Turing machines equipped with a write-only query tape and with access to a query oracle. My question is, is there a limit of the content that can ...
38 views

### Turing Machine where the number of a’s and b’s are either both even or both odd over {a,b} [closed]

Turing Machine where the number of a’s and b’s are either both even or both odd.
20 views

### decidability and reducibility

I am a bit confused on how I can show the finiteness problem is undecidable using Rice’s Theorem. So I’ve got something like B = { | M is a TM and L(M)- finite}. I thought I could reduce A TM (...
9 views

### Improving Turing Machine for Eulerian Path Problem [closed]

I'm trying to construct a determinististic one-tape Turing Machine for an Eulerian Path (https://en.wikipedia.org/wiki/Eulerian_path). I have written the one below as a starting point, but would like ...
22 views

### Question for “Only if” part for the theorem “A language is Turing-recognizable iff some enumerator enumerates it.”

I am trying to prove the theorem A language is Turing-recognizable iff some enumerator enumerates it. I proved the "if" part, but I have no idea of proving the "only if" part, so I searched a ...
42 views

### Does any algorithm loops at some point?

Given that any implementable algorithm has a finite number of internal states, and given that any state is determined by the previous one, does that implies that any algorithm loops at some point? If ...
34 views

### How to translate automaton (Turing machine) into the program of high level programming language?

Every program in high level ("industrial") programming language can be expresses as some Turing machine. I guess, that there exists universal algorithm for doing that (e.g. one can take the Cartesian ...
63 views

### Can a Non-Deterministic Pushdown Automaton recognize $\# a^nb^{2^n} \#$ which a TM can?

$\# a^nb^{2^n} \#$ such that • The alphabet of the machine is {, a, b, x}. • The symbol x will never appear on the input a. • The contents of the tape at completion may be anything. • The head ...
35 views

65 views

33 views

### Turing machine deciding $L = \{w ∈ \{a, b, c\}^*\ |\ |w|\ mod\ 3 = 0\ OR\ w ≠ w^R\}$

$$L = \{w ∈ \{a, b, c\}^*\ |\ |w|\ mod\ 3 = 0\ OR\ w ≠ w^R\}$$ I'm looking for transition function... Any hint?
97 views

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

I want to find two undecidable languages $A$ and $B$ that $A$ cannot reduce to $B$, $B$ cannot reduce to $A$(Many-one reduce). One of my thought is to let $A$ be the halting problem, let $B$ be some ...