Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

There are many variations of what a Turing machine is. I agree the author is using some definitions that are quite out of the ordinary and in doing so it makes it hard to follow. At any rate what they describe is certainly equivalent in terms of computability to the other Turing machine variations.

What the author is taking liberty with is instead of considering Turing machines that halt, the Turing machine reaches a point where it will never transition to a given state, or set of states. Call this quasi-halting, the Turing machine will continue running, but it will never transition to one of a predetermined set of states. As soon as the Turing Machine reaches such a point, it is said to have quasihalted, even though it has not technically halted in the usual sense.

Then the author comes up with a variation of the busy beaver game where instead of a Turing machine halting, the Turing machine enters a quasihalting state. The author argues that reasoning in terms of a quasihalting state instead of a halting state is more expressive, gives insight into a problem known as the spaghetti code conjecture and furthermore that if BB(n) represents the busy beaver function, and QQ(n) represents the variation of busy beavers but for quasihalting, then BB(n) is an element of O(QQ(b)).

QQ(n) will contain all Turing machines that halt (since anything that halts also quasi-halts), but it will also contain some Turing machines that don't halt and instead strictly quasi-halt, so we should expect that there are more of them.

Perhaps an interesting open question is whether BB(n) is in little-oh(QQ(n)). Given that BB(n) is not even computable, and hence QQ(n) is not computable, I don't even know how one would begin to tackle such a problem.



Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: