This tag is suited for questions involving Turing machines. Not to be confused with finite state machines and finite automata.
2
votes
1answer
151 views
How can a turing machine solve the element distinctness problem?
I am reading an example in Sipser's famous book on the theory of computation. In this example, Sipser creates a turing machine M to solve the element distinctness problem. M is given a list of strings ...
12
votes
2answers
257 views
How can Busy beaver($10 \uparrow \uparrow 10$) have no provable upper bound?
This wikipedia article claims that the number of steps for a $10 \uparrow \uparrow 10$ state (halting) Turing Machine to halt has no provable upper bound:
"... in the context of ordinary ...
1
vote
0answers
32 views
Would adding a stack to a 2-stack Turing machine allow it to recognize more languages?
I don't think it should because a third stack would be superfluous. The machine could just reuse the first stack after it uses the second right?
I'm just beginning to learn about Turing machines, so ...
