11–18 of 18 posts
Consider: are all programs that don’t halt infinite loops? Perhaps one which experiences exponential growth in some variable.
x = 0.035876; while true { x = 3.5699456 * x * (1 - x); if x == rand() break; } does it halt?
Halting Problem isn't "does this one instance of a program return". Halting problem is with a Turing Machine, implement an algorithm that will determine whether any arbitrary turing machine from the space of all possible Turing machines return. You cannot generally decide the problem, because at best your algorithm can only practically determine "the Turing Machine under test has not returned...yet. The Turing Machin…
Consider: are all programs that don’t halt infinite loops? Perhaps one which experiences exponential growth in some variable.
So what about a chaotic function like: (assume x is 64bit float) x = 0.035876; while true { x = 3.5699456 * x * (1 - x); if x == rand() break; } does it halt?
Take for example a program that attempts to calculate the https://en.m.wikipedia.org/wiki/Collatz_conjecture
Some inputs would rapidly get answered. Most won’t. If you can prove it’s halt-able for all inputs, you’ve won a Nobel and will be well off for life.
Good luck.
As people said, a turning machine has infinite memory and program space. Just checking for context and program position doesn’t solve all cases of never halting. Take for example a program that attempts to calculate the https://en.m.wikipedia.org/wiki/Collatz_conjecture Some inputs would rapidly get answered. Most won’t. If you can prove it’s halt-able for all inputs, you’ve won a Nobel and will be well off for life.…
As people said, a turning machine has infinite memory and program space. Just checking for context and program position doesn’t solve all cases of never halting. Take for example a program that attempts to calculate the https://en.m.wikipedia.org/wiki/Collatz_conjecture Some inputs would rapidly get answered. Most won’t. If you can prove it’s halt-able for all inputs, you’ve won a Nobel and will be well off for life.…
while true i += 1
Example: ax is a 2 bit register initialized to 0. 100: add 1 ax 101: jmp 100 ax is 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3 0 is compared to 1, 1 is compared to 3, 3 is compared to 2, 2 is is compared to 2, wait, that's an infinite loop...
Earlier quoted context omitted.
So what about a chaotic function like: (assume x is 64bit float) x = 0.035876; while true { x = 3.5699456 * x * (1 - x); if x == rand() break; } does it halt?
After a finite amount of time, it will either report "Halt" or "Infinite Loop", but my program won't take forever, just a finite amount of time.