[portent]

What you are saying sounds intuitively true, but the mathematics of Chaos Theory showed that it is not actually the case.

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.

https://en.wikipedia.org/wiki/Logistic_map

[Retric]

No, virtually is the important bit. In code we can know all the details. So, you can predict the code just fine. For example running it twice and getting the same output the second time. Chaos theory is based on real world systems that can't be measured accurately. However, internal computer simulations don't have that limitation.

One example is if you try saving a simulation to disk you need to copy all internal state or you get a different output.

[TeMPOraL]

You're right (and I think commenters saying that parent was talking about halting problem are wrong - it was clearly about chaotic systems, which are deterministic). And yet, this doesn't make the original statement - "we have no idea what happens in our own code" - any less true. Without even touching the halting problem, all code we write quickly explodes in complexity beyond our ability to mentally simulate it, and those of us who don't work on life critical systems are not paid for anything more than some unit tests and a cursory "uh, it looks ok to me" assessment.

[BraveNewCurency]

No, the parent is actually talking about the Halting Problem. It has been proven impossible to predict when a program will exit without actually executing the program. (except in a few trivial edge cases)

https://en.wikipedia.org/wiki/Halting_problem

[harveywi]

Minor detail, but the undecidability Halting Problem strictly requires an infinite tape (infinite storage space).

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.

[beaconstudios]

actually, the proof for the halting problem is rather esoteric in its demonstration. The claim isn't that you can't predict when most programs will end, but that it's possible to construct a scenario where the program goes out of its way to be unpredictable by running the prediction algorithm on itself and inverting the answer using an infinite loop.

[andrepd]

No, I don't think you quite get it. What OP meant, in more rigorous terms, is: write me a function that takes "b" as an argument and returns whether the function will terminate or not when I replace 3.59 with "b". As it turns out, this is not at all simple. But you don't even need to go there. For some values of "b", the program doesn't terminate, and it's not trivial to show it. What are you going to do? Run the program forever? You can never prove it won't terminate in the next iteration.

[Retric]

Machine has finite precision, as soon as it repeats a previous state it's in an infinite loop. And no you don't need to run this on an arbitrarily large computer, two computers running at different speeds where you compare state after each step also works.

PS: The halting problem is only undecidable when running with unlimited memory.

[darkmighty]

I don't think you quite grasp how hard a problem can be for a fixed size Turing machine. The state size is 2^(Memory), naively solving the halting problem for all cases that can be solved in a reasonably-sized Turing machine still makes the age of the universe look like nothing. 2^10000000000 is nothing to scoff at.

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.

[darkmighty]

What about the following?

  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

[Retric]

In theory this will eventually overflow even with pythons Arbitrary precision due to the machines finite memory. Though for practical cases it's going to run until the machine encounters an error.

If your asking the underlying math problem, yes that is true for all positive integers. It's much more obvious in base 3.

[darkmighty]

Sorry, I probably failed at writing a simple Collatz conjecture search (it should halt if Collatz is false).

https://en.wikipedia.org/wiki/Collatz_conjecture

[jcoffland]

It will run in a loop until someone turns it off. How do you want to pay up? I accept cash and Bitcoin.