One example is if you try saving a simulation to disk you need to copy all internal state or you get a different output.
One example is if you try saving a simulation to disk you need to copy all internal state or you get a different output.
In "practice", if you could call it such, a computer with limited memory becomes a "linear bounded automaton" and the Halting Problem is decidable; cf. http://cs.stackexchange.com/q/22925
Of course, big enough memory can mean that it can be impossible to detect termination before the heat death of the universe - we are talking theory here.
PS: The halting problem is only undecidable when running with unlimited memory.
For the Collatz problem you can simply run a (fixed version) of that program with arbitrary-precision arithmetic and it would pretty much run until you run out of memory, which is on the order of 2^RAM. For me that would be about 2^8000000000.
I think an important argument that hasn't been made is the simulation speed. If we want to make sure a program running at clock C never ill-behaves, it suffices to simulate it at a clock C'>C and halt it if and when it misbehaves. Any constant factor speedup is sufficient to manage that even in the same hardware. A problem starts to occur if C is susceptible to random mutations, with a branching factor B every T seconds. Then to simulate t seconds into the future requires B^T/t more computing power. If there's one 1-bit mutation per second, it gets unpredictible less than 1 hour in the future.
x=5
y=5
while True:
if y%2 == 0:
y=y/2
else:
y=3y+1
if y == 1:
x=x+1
y=x
if y==x:
return x
Please predict the code. I'll even give you $500 in memory of some guy named Erdos if you get it right (and I haven't even gone for a provably undecidable example! :) )PS: Don't waste time checking x values less than 1000000000000000000
If your asking the underlying math problem, yes that is true for all positive integers. It's much more obvious in base 3.