Simple example: can you tell me if this snippet of (python) code will ever terminate or not?
x=0.5
while x<0.6 or x>0.7:
x=3.59*x*(1-x)
print x
What my code snippet is doing is running a sample of a particular chaotic function that was originally inspired by biology (a simple predator/prey model). Ultimately, what happens is that you just cannot predict how the function will behave - it is chaotic.
Ultimately most complex systems start to show some chaotic behaviour, which basically means that the behaviour of the system cannot be predicted in detail, even if virtually everything is known about the system in advance.
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
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.
That said, we can still see what that code does, even if we don't know precisely what code path it takes. Great example though!
The original poster seems to imply that knowing the code means that you can know the behaviour of the system; I do not think that is the case, and my simple (chaotic) example tries to demonstrate this.
The issue is not so much how this code is translated from higher abstraction level to lower abstraction level... the issue is, that this code represents a simple chaotic function (the logistic map). As such, for a simple few lines of code the behaviour is very complex and virtually impossible to predict; for certain values of the controlling number it will (1) halt relatively quickly, (2) never halt, or (3) halt after a very long time... but good luck in distinguishing between cases 2 and 3!