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

1
vote
0answers
348 views

Turing Machine question, this is NOT HW

I was having a hard time understanding and solving this question that wants me to show the final tape and figuring out if whether or not the turning machine accepts it or not. I have a list of 20 ...
4
votes
0answers
88 views

Designing a turing machine for primality check.

I am designing some turing machines, so far I have made Binary Addition and subtraction. Now I've been thinking that what if turing machine can check if the number is prime or not. Lets suppose we ...
2
votes
1answer
60 views

Zermelo–Fraenkel Set Theory

So I'll try keeping this real short and simple. Assume that language $L$ is defined as $\{ x\in \{0,1\}^* \}$ (finite binary strings) such that $x$ encodes a proof in ZFC that 4 is a prime number. I ...
0
votes
1answer
75 views

is differ between distributive lattice vs semi-lattice on Turing Degrees

We know a Posed Closed under suprema but not necessarily under infima is an upper semi-lattice. We now r.e set forms a distributive lattice. But my question is why following statement is hold? I ...
28
votes
4answers
914 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 ...
15
votes
3answers
539 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 ...
2
votes
1answer
405 views

Is this undecidable language recognizable?

Is this language: $L = \{\langle M\rangle : \text{$M$ is a Turing machine and $L(M)$ is decidable}\}$ which I know that is undecidable, turing-recognizable? Is its complement recognizable? ...
1
vote
1answer
85 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 ...