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

I think that it would be fairly easy (meaning that I think I could do it in 8 hours) to build a Turing Machine that prints 10^1000 1's on its tape and then halts. We would not be able to construct and run physical Turing machine that could do every move physically (by moving electrons) within 100 billion years, but we can still write the proof that it halts, probably with less than 3 pages. (In fact, we could probably tell you which state it is in for any i in the set {1, ...., halting step} without ever constructing and running a physical machine.)

On the other hand, if the "shortest" proof of halting is more than 10^20 pages long, then we would have major problems "writing" it.




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

Search: