Am open to constructive criticism: My Halting Problem solution
4 comments
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 Machine capable of ultimately deciding the returnability of TMuT, would necessarilly have practically infinite runtime.
And for that matter, bring yourself out of TM's and you've got all sorts of other nasty constraints that make the Halting Problem Solver unimplementable in the real. What happens when brownouts happen? Single-event-upsets? Rowhammer events? You couldn't win in the purely abstract theoretical, so even trying to get a literal win in the real doesn't stand a chance.
Halting Problem is Computer Science's realization that there is always a bigger Turing Machine, much like how mathematicians understand there to be infinitely many primes. Within the constraints of the axiomatic model of computation; you cannot put a pin in the entire space. Only increasingly large swathes of the space at the cost of completely unreasonable respurce expenditure.
Or as I like to think of it, HP is the understanding that only 2 people ever understood this code in it's totality. God, and me when I was writing it. And I long ago ditched that original context that allowed me to claim I understood it.
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 Machine capable of ultimately deciding the returnability of TMuT, would necessarilly have practically infinite runtime.
And for that matter, bring yourself out of TM's and you've got all sorts of other nasty constraints that make the Halting Problem Solver unimplementable in the real. What happens when brownouts happen? Single-event-upsets? Rowhammer events? You couldn't win in the purely abstract theoretical, so even trying to get a literal win in the real doesn't stand a chance.
Halting Problem is Computer Science's realization that there is always a bigger Turing Machine, much like how mathematicians understand there to be infinitely many primes. Within the constraints of the axiomatic model of computation; you cannot put a pin in the entire space. Only increasingly large swathes of the space at the cost of completely unreasonable respurce expenditure.
Or as I like to think of it, HP is the understanding that only 2 people ever understood this code in it's totality. God, and me when I was writing it. And I long ago ditched that original context that allowed me to claim I understood it.
Consider: are all programs that don’t halt infinite loops?
Perhaps one which experiences exponential growth in some variable.
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?
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.
then you have added nothing to the problem. of course if you run the program and it halts, even if runs until T+heatdeathofuniverse^googleplex (which is a finite time) without an infinite loop, you have not solved the conundrum implied by Turing’s work.
Turing proved no algorithm exists that always correctly decides whether, for a given arbitrary program and input, the program halts when run with that input. The essence of Turing's proof is that any such algorithm can be made to produce contradictory output and therefore cannot be correct.
He proved it - QED
I think his point is, that there are (due to the limits of longs/BigInts) only a finite number of configurations before an integer overflow. I am not qualified to present an argument against, but I think there are some programs for which the computation time would be greater than the age of the universe. For example, “Print all possible configurations of this 4k monitor”.
Yes, this infinite loop solver would take longer than the universe's age to print all possible configurations of this 4k monitor, but it would take a finite amount of time as opposed to infinite. (Provided that the integer n is big enough as a arbitrary precision fixed point unsigned integer)
I think (and I am no expert here, so correct me if I am wrong) that, when it comes to actually written programs, there is little difference between “actually infinite” and “practically infinite”. This is like saying the probability of any particular real number being given by a float is zero because floats are only countable infinite (practically) rather than uncountable infinite. I don’t know, maybe I am talking out of my ass, tho lol
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.
Good luck.
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.
[deleted]
[deleted]
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...
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...
You have two memory locations A and B... Your example already requires 5 such locations...
Step 1: Load the program and initialize my Halting Problem program's variable n to 0.
Step 2: Save the register context (meaning all the values in all the registers in a CPU) to memory location A.
Step 3: Step variable n + 1 instructions.
Step 4: Save the register context (meaning all the values in all the registers in a CPU) to memory location B.
Step 5: Compare the contents of memory location A to memory location B. If they match exactly, then exit with a return code of "This program is in an infinite loop", if they don't match exactly, then goto Step 2.
The variable n is an unsigned fixed point arbitrary precision integer.
If this solves the Halting Problem as proposed by Alan Turing, then does this also solve P versus NP?
An example of this working:
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...
Well, my program basically detects if a infinite loop is of 1 iteration or two iterations or three iterations or ... iterations, but only infinite loops and not finite loops and in a finite amount of time. This means that finite loops don't trigger my program ever, only infinite ones after a finite amount of time.
TLDR: A turing machine can run my program and determine whether any other program halts or infinite loops in a finite amount of time, never infinite only if the variable n can be infinitely large.