This tag is suited for questions involving Turing machines. Not to be confused with finite state machines and finite automata.
Questions tagged [turing-machines]
954 questions
2
votes
1 answer
Turing Machine for $L$={$a^nb^m: m=n^2, n \geq 1$}
The problem only requires a description of the machine.
I was thinking for each a you need to find 1 + 2k b's where k is the a your on. (ie for the for the first a find 1 bs, the second find 3 bs, fourth find 5 bs, etc). Obviously this is not the…
Gunslinger
- 179
2
votes
1 answer
What's the difference between a non-deterministic turing machine and a deterministic turing machine?
From what I understood, it seems that the difference is that a NTM can have 2 inputs for which there is a different output or direction.
For example, state A for input 1 can result in output 0 and left, o output 1 and right.
Is that all, or am I…
john
- 21
2
votes
1 answer
Number of possible configurations in a Turing Machine
While studying for an up-and-coming exam, I stumbled upon the following question:
$$
L=\{\langle M \rangle,\langle w\rangle:M\text{ is single-tape and }M \text{ running on }w \text{ doesn't go over the first }|w|+1 \text{ cells} \}
$$
True or False:…
Ben E
- 23
2
votes
1 answer
Given a single taped deterministic turing machine what's the least amount of calculations needed in order to receive the language
Given a single taped deterministic turing machine what's the least amount of calculations needed in order to receive the language $L_k=${$0,1$}$^*0${$0,1$}$^{k-1}$.
My intuition says that i'll need at least $n+k$ calculations.
I will start at the…
StationaryTraveller
- 2,453
2
votes
1 answer
Concrete universal turing machine
I read about universal turing machines in the internet, but I did not find a concrete listing of a universal turing machine and a descreption, how a specific turing machine
has to be coded that the universal machines simulates it. Does anyone know a…
Peter
- 84,454
2
votes
1 answer
Multi-head Turing machine can be simulated by a single-tape deterministic Turing machine
A multi-head Turing machine is a Turing machine with a single tape but multiple heads. Initially, all the heads are positioned above the first cell of the input. The transition function is modified to allow reading, writing, and moving of the heads.…
guglielmo
- 31
2
votes
1 answer
Explanation of a few points in Alan Turing's, 'On the Computable Numbers'
I have recently been reading Alan Turing's On the Computable Numbers, With an Application to the Entscheidungsproblem, and found it fairly straight forward at first, but was confused on some points in §5 and §8.
Firstly, in §5 page 240, Turing…
Caleb Thoburn
- 43
- 9
2
votes
0 answers
Classifying a language into co-re using a Turing machine
I have the following language:
$$L=\{\langle M1\rangle,\langle M2\rangle: |L(M_1) ∩ L(M_2)|≤10 ~~\text{ or }~~ |L(M_1) ∩ L(M_2)|≥1000\}$$
I am told that this language is either r,re or co-re. it was obvious that it is not in r.
I used a reduction to…
yos_sir
- 43
2
votes
2 answers
Complement of halting set is not r.e.
suppose we don't know that Halting problem is not recursive.
I want to prove that complement of halting set is not r.e. then we can find halting problem is not recursive.
Can you direct prove that complement of halting set is not r.e.??
a d
- 274
2
votes
2 answers
Incomparable languages $B \nleq_T A$ and $A \nleq_T B$
I came across a problem to prove that there are sets $A$ and $B$ termed 'Turing-Incomparable' languages $B \nleq_T A$ and $A \nleq_T B$. The only languages I could think of are if $A$ and $B$ are disjoint regular expressions such as $B=1^*$ and…
Link L
- 717
2
votes
1 answer
General approach for proving decidability/undecidability
I know there are infinite number of topics on here asking about how to prove decidability, but I have been reading a lot of them, as well as reading proofs from a book, trying to understand how to approach this problem, but I'm struggling quite a…
A Val
- 23
2
votes
1 answer
Prove that exists undecidable subset of $\{1\}*$
Hello my dear friends!
I have following problem:
Prove that exists undecidable subset of $\{1\}*$
The problem is that I don't know how to start. In real I don't what does it mean undecidable set ?
user220688
- 509
2
votes
1 answer
prove that language is not deciable by reduction
I show you my approach to one problem, and try to assess it.
Show that following language is not decidable:
$L=\{\langle M\rangle|\text{M is Turing Machine and M has one or more unreachable state} \}$
And I try to reduct $E_{TM}$ (which is not…
user220688
- 509
1
vote
0 answers
(2,5) Turing Machine implemented with chess pieces
I recently came across a (limited) reference to a (2,5) Turing machine implementation that can be represented using chess pieces on a 2D board. I know it is possible to implement a UTM using cellular automata, no specifics were given to the rules…
yarbelk
- 111
1
vote
1 answer
Will this Turing machine ever halt?
Consider the following Turing Machine, $T_k(n)$, defined in terms of:
$$
T_k(n) = 1 + T_n(n)
$$
At a high level, this expression indiviates that we have a Turing machine (with instructions represented by $k$) that takes as input any arbitrary long…
Ryde91s
- 83
- 1
- 6