9 ms·
It is left as an exercise to the reader to find a natural number which isn't arbitrarily large but calculable.
by thrown123098 3y ago
It is left as an exercise to the reader to find a natural number which isn't arbitrarily large but calculable.
- rrobukef 3y agoThe tape size needed for a Turing machine is incalculable. Here's a reference to a proof: https://scottaaronson.blog/?p=2725 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.
- thrown123098 3y agoYes which is why the size if strictly finite but arbitrarily large.