4 ms·

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

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 10y ago
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 https://en.wikipedia.org/wiki/Logistic_map
- Retric 10y ago
  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.
  - BraveNewCurency 10y ago
    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 https://en.wikipedia.org/wiki/Halting_problem
    - beaconstudios 10y ago
      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.
    - harveywi 10y ago
      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 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.
  - andrepd 10y ago
    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 10y ago
      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.

portent 10y ago

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 https://en.wikipedia.org/wiki/Logistic_map

Retric 10y ago
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.
- BraveNewCurency 10y ago
  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 https://en.wikipedia.org/wiki/Halting_problem
  - beaconstudios 10y ago
    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.
  - harveywi 10y ago
    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 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.
- andrepd 10y ago
  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 10y ago
    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.