Articles of turing machines

The Entscheidungsproblem and the notion of decidability in first order logic

The Entscheidungsproblem asks if we can find an effective procedure to decide for every formula of first-order logic if its true or false, or what is the same with regard to its completeness, if it is provable or not. This could be read on wikipedia. This problem was answered in the negative by Church and […]

Lower bounds for bb(7) and bb(8) wanted

The busy beaver function $bb(n)$ is not known for $n \geq 5$. Does Anyone know suitable lower bounds for $bb(7)$ and $bb(8)$? Remark: $bb(6)$ as a trivial lower bound does not count as a suitable bound.

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 article and someone had doubts about these bounds. I am not quite sure, if the bounds turned out to be true at last. So my quesion : Are […]

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 explain or provide proof that a standard TM can work with this other turing machine variation?

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 computer science. Why? Do we have any more evidence for its truth than “nobody has been able to think of a […]

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 statement. L1 = {hMi : |L(M)| ≤ 10}. Is L1 recognizable? Prove your answer. L2 = {hMi : |L(M)| ≥ 2}. Is L2 […]

Undecidable language problems.

Let $L_1$ and $L_2$ be two undecidable languages. 1) Is it possible that $L_1 – L_2$ is regular and $L_1 – L_2 \neq \emptyset$ ? Well I know that if I let $L_1 = L_2$ then $L_1 – L_2 = \emptyset$ which is obviously regular. In the case of this question however, I cannot set […]

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 mathematics, neither the value nor any upper-bound of $\Sigma(10\uparrow\uparrow10)$ can be proven…” How is this possible? In principle, wouldn’t listing the computations of […]