This tag is suited for questions involving Turing machines. Not to be confused with finite state machines and finite automata.

learn more… | top users | synonyms

19
votes
5answers
768 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 ...
0
votes
1answer
136 views

Turing Machine recognizability

I'm trying to go over some review problems regarding Turing Machine recognizability, and am still pretty confused about the following problems. This is the only information we are given in the problem ...
53
votes
3answers
3k views

Are there any Turing-undecidable problems whose undecidability is independent of the Halting problem?

To be more specific, does there exist a decision problem $P$ such that given an oracle machine solving $P$, the Halting problem remains undecidable, and given an oracle machine solving the Halting ...
32
votes
4answers
1k views

Why do we believe the Church-Turing Thesis?

The Church-Turing Thesis, which says that the Turing Machine model is at least as powerful as any computer that can be built in practice, seems to be pretty unquestioningly accepted in my exposure to ...
5
votes
2answers
447 views

Milton Green's lower bounds of the busy beaver function

Wikipedia states that Milton Green demonstrated in 1964, that the busy beaver function $\Sigma(n)$ has the lower bound $$\Sigma(2k)>3\uparrow^{k-2}3$$ I read the talk about the busy beaver ...
1
vote
1answer
1k views

Turing Machine Variation

Hi i'm trying to figure out this question: Give a formal definition of multihead-multitape Turing machine. Then show how such a machine can be simulated by a standard Turing machine Can someone ...
1
vote
1answer
336 views

Let $L_{UIUC}$ = $\{ \langle M \rangle$ : $L(M)$ contains the string $UIUC\}$. Prove that $L_{UIUC}$ is undecidable.

Been stumped as to why the following proof works. Note: I have taken this proof directly from here. Proof by reduction from $A_{TM}$. Suppose that $L_{UIUC}$ were decidable and let $R$ be a Turing ...
0
votes
1answer
68 views

Showing set is undecidable with Turing Machines

I'm given the set $T = \{\langle M, w\rangle : M $ is a Turing Machine that accepts $w$ reversed whenever it accepts $w \}$ and I want to show it's undecidable but recognizable. (I'm using the bracket ...