# Tagged Questions

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

404 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 ...
37 views

### Direct Reduction, Turing machine and a DFA

I have been reading and I am trying to understand the reduction when it comes to truing machine. This is how I understand it: it means that it reduces problem A into problem C. But I am not quite sure ...
638 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 ...
228 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 ...
65 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 ...
123 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 ...
95 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 ...
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 ...
505 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? ...
### 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 ...