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

Given that Turing machines cannot be guaranteed to halt (and it's trivial to write an infinitely-running Turing machine), therefore humans are not, technically, Turing-complete.


Turing completeness is a theoretical construct that ignores that errors in execution inevitably occur during a sufficiently long program, due to the second law of thermodynamics (entropy must increase in a closed system). Any realization of a Turing complete engine eventually fails. That's different than halting, though, because it doesn't answer the question as to whether the program of the machine eventually reaches a halt instruction, when properly executed.


Well, I would say that any physical implementation of a Turing machine will eventually halt because you cannot guarantee an infinite energy supply. So if we're willing to ignore physical limitations then humans can be Turing complete - if not, then no machine be either.




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

Search: