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

The tape size needed for a Turing machine is incalculable. Here's a reference to a proof: https://scottaaronson.blog/?p=2725.

The machine with 7918-states, Z, stops (well, Z cannot be proven to run infinitly long) iff. ZFC is consistent. For this it needs a finite amount of space but we cannot calculate how much. If we could calculate an upper bound we've proven ZFC is consistent.



Yes which is why the size if strictly finite but arbitrarily large.




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

Search: