[portent]

code can be very simple, and we don't always know what it will do.

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

... and what if the 3.59 was replaced by a different number - maybe 3.60 ? or 3.84 ?

[klibertp]

I think that the argument is that I could know, pretty exactly, not only when (or if) this piece of code terminates, but also how much iterations it's going to take. Sure, it's much easier (in this case) to simply run the thing, experiment with some tweaks a bit and come to some conclusion (like biologists supposedly do?). But I could also go read CPython (assuming CPython) implementation of floating point arithmetic, eventually dropping down to assembly and the workings of an FPU unit, while at the same time I could also take an analytic approach, treating this as a well-defined mathematical problem of summing a series (I think? sorry, I'm personally not that good on that front... but the option is there!). I think biologists are constrained only to the first, experimental approach - or that's how I understand the argument, at least.

[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.

[taneq]

And this is a great illustration of why arguments that "humans are special because computers can never solve the halting problem" are specious. We can't solve the halting problem (in the general case) either.

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!

[sbmassey]

It will eventually terminate, if only because the machine it is running on will eventually be shut down.

[portent]

OK, well we can always say that the heat-death of the universe renders all problems irrelevent, but it's a bit of a cheat in my opinion.

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.

[sbmassey]

Well indeed, as per Turing on the Entscheidungsproblem one cannot know what some abstract bit of code does without running it, but one can sometimes put limits on its behaviour - your snippet will never do anything but print out numbers, for example, or something running under seccomp might be prevented from making certain syscalls.

[portent]

my point is that even running the code doesn't help you answer the question. It runs for a year and doesn't halt... so will it ever halt?

[joshjje]

If you have the compiled assembly obviously you can say exactly what will happen. I agree with your meaning somewhat though that more often than not many people have no clue, especially with large systems. Its not as bad as your statement though..

[portent]

Well... the compiled assembly doesn't give you any more information than the code snippet.

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!

[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

[labster]

Woo, about time someone solved the halting problem ;)