4 ms·

Wrong: https://en.wikipedia.org/wiki/Arbitrarily_large https://en.wikipedia.org/wiki/Arbitrarily_large

• rrobukef 4y ago
  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).
  • thrown123098 4y ago
    It is left as an exercise to the reader to find a natural number which isn't arbitrarily large but calculable.
    • rrobukef 4y ago
      The 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 4y ago
        Yes which is why the size if strictly finite but arbitrarily large.