5 ms·
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?
by portent 10y ago
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 ?
- sbmassey 10y agoIt will eventually terminate, if only because the machine it is running on will eventually be shut down.
- portent 10y agoOK, 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.
- joshjje 10y agoIf 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 10y agoWell... 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 10y agoNo, 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
- sbmassey 10y agoWell 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 10y agomy 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?
- deleted 10y ago[deleted]
- labster 10y agoWoo, about time someone solved the halting problem ;)
- klibertp 10y agoI 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 agoWhat 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 agoNo, 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
- taneq 10y agoAnd 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!