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

There is a physical limit to the number of disks you can add to your CPU. There is a physical limit to the memory you can address in your CPU (48-bits). It is not arbitrarily large.

Also wrong for Turing Machines, it really is infinite. That's a big difference to arbitrarily large. The halting problem is undecidable for TM's but not for arbitrarily large (you'll need precise definitions though).



It is left as an exercise to the reader to find a natural number which isn't arbitrarily large but calculable.


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: