The abstract formalism of a turing machine has an infinite amount of memory. Any process that exists in the real physical world (as far as I know) has only a finite amount of memory. My computer contains around 243 bits. So it has 2243 distinct computational states. To see if a program will hault, just simulate for 2243 timesteps, and if it hasn’t halted yet, it never will. (Actually, if you really zoom in on the physical details, the hard drive will wear out before then)
If you ran a programming language on some magic computer with infinite memory, there is no procedure takes in an arbitrary piece of programming code and returns “halt” or “no halt” correctly.
You can run arbitrary code and see if it has halted yet. So “does arbitrary code halt in a googleplex timesteps?” is computable. But if someone hands you a piece of code that runs forever, you can’t always tell if it runs forever or just runs for longer than you have simulated it.
Whenever something like a card game turns out to be turing complete, there is some score or number of points that is an arbitrary natural number. In other words, an unboundedly large amount of info can be encoded in the digits of the score. In a real game, the score is small, but in principle you could get a score so big you couldn’t write it down and have to stop playing.
The abstract formalism of a turing machine has an infinite amount of memory. Any process that exists in the real physical world (as far as I know) has only a finite amount of memory. My computer contains around 243 bits. So it has 2243 distinct computational states. To see if a program will hault, just simulate for 2243 timesteps, and if it hasn’t halted yet, it never will. (Actually, if you really zoom in on the physical details, the hard drive will wear out before then)
If you ran a programming language on some magic computer with infinite memory, there is no procedure takes in an arbitrary piece of programming code and returns “halt” or “no halt” correctly.
You can run arbitrary code and see if it has halted yet. So “does arbitrary code halt in a googleplex timesteps?” is computable. But if someone hands you a piece of code that runs forever, you can’t always tell if it runs forever or just runs for longer than you have simulated it.
Whenever something like a card game turns out to be turing complete, there is some score or number of points that is an arbitrary natural number. In other words, an unboundedly large amount of info can be encoded in the digits of the score. In a real game, the score is small, but in principle you could get a score so big you couldn’t write it down and have to stop playing.