Hacker News new | past | comments | ask | show | jobs | submit login

Take the machine for BB(n) with non-end states {1,2,3,…n} and end state E.

In its program, change every transition that goes to state E to go to a new state n+1 instead.

Add transitions “when in state n+1 and on a 1, move right” and “when in state n+1 and on a 0, write a 1 and stop”.

Doesn’t that give you a Turing machine with n+1 states that stops after writing one more 1 than BB(n) writes, thus proving that BB(n+1) is at least one more than BB(n+1)?




yeah, that shows BB(n+1) >= BB(n) + 1, but if you want to make the inequality strict you need to find a way to add another step.


Oops. Reversing your “BB(n) + 1 < BB(n + 1)” turned out to be too difficult for me today. Thanks for the reply.




Join us for AI Startup School this June 16-17 in San Francisco!

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

Search: