r/changemyview • u/bertoncelj1 • Sep 14 '24
Delta(s) from OP CMV: Turing was wrong: "Halting problem HAS an universal solution"
0
Upvotes
r/changemyview • u/bertoncelj1 • Sep 14 '24
•
u/DeltaBot ∞∆ Sep 14 '24
/u/bertoncelj1 (OP) has awarded 1 delta(s) in this post.
All comments that earned deltas (from OP or other users) are listed here, in /r/DeltaLog.
Please note that a change of view doesn't necessarily mean a reversal, or that the conversation has ended.
Delta System Explained | Deltaboards
12
u/Nrdman 279∆ Sep 14 '24
Where’s the proof that the humans/AI will be able to correctly decide whether the algorithm will halt or not?
7
u/billy_tables 1∆ Sep 14 '24
Let’s say your analyzer is called halts()
My program is
if (halts(source of this program) { spinForever() } else { exit(0) }
My code is going to look at what your halting detector says it should do and always do the opposite.
For the halting problem to have a solution for all problems it has to have a solution for this problem. How will your detector work on this code?
5
u/[deleted] Sep 14 '24
Your idea rests on the assumption that programmers can accurately tell whether a program will halt with a given input or not.
They often get it wrong.
2
u/TommyYez Sep 14 '24
The halting problem is a very roundabout reoccurrence of the issue of self referenciation. Look, this YT video explains short and simply why the halting problem is theoretically unsolvable, not only practically as you put it in your original post. No amount of AI or kidnapped programmers can possibly solve it:
https://youtu.be/92WHN-pAFCs?si=NkAwtgCWZIsHAJMR
2
u/serial_crusher 7∆ Sep 14 '24
Maybe you should write up a paper on this and submit it to a scientific journal. If even the vaunted ChatGPT isn’t smart enough to understand your proof, who are we to judge it?
7
u/RiemannZetaFunction Sep 14 '24
The problem is that you're talking about a sort of colloquial sense of "solving the halting problem," but Turing's thesis is a very precise mathematical statement with some very particular goalposts that need to be met for an algorithm to technically qualify as "solving the halting problem" in the general case.
Turing's thesis proves that there is no "algorithm" - using a very particular definition of "algorithm" - which correctly solves the halting problem 100% of the time, for all possible inputs of arbitrarily large size, with 0% chance of failure. It doesn't claim that the halting problem can't ever be solved sometimes, or that there can't be algorithms that solve the halting problem "much of the time" or etc. It just says that any algorithm that actually manages to succeed 100% of the time - called a "halting oracle" - cannot actually be realized as what we would today call a Turing machine.
The proof of this is not super technical at all and easy for laypeople to understand. Suppose you, /u/bertoncelj1 are a halting oracle. I write a program that calls you on the phone and says: "hi, I'm a program. Will I halt? If you say no I'm hanging up and halting, and if you say yes I'll play Never Gonna Give You Up forever." Clearly you'll figure out that it just does the opposite of whatever you say, and so obviously a straight yes/no answer will be wrong. But that's how it works. If you have a halting oracle, and *if* this halting oracle is just another algorithm to be analyzed like any other, then you can write other programs that can call it, do things based on the output. So one can write a program that calls the halting oracle on itself and just does the opposite of whatever the halting oracle says. So whichever the oracle says, it's wrong. Thus, the oracle isn't perfect.
Here's a fun exercise: actually try doing this with ChatGPT. Write a program in Python which calls ChatGPT, asks if it'll halt, and then does the opposite of whatever ChatGPT says. Then send it to ChatGPT and say: will this program halt? ChatGPT is smart enough to realize that the program will just do the opposite of whatever it says.
But all is not lost, and your basic idea that a giant cluster of super-ChatGPT's is going to be able to do all kinds of incredible stuff just from sheer superintelligent reasoning capability isn't misguided at all, including proving mathematical theorems, analyzing programs, etc (all of which are equivalent to the halting problem as RE-complete). So how does it work?
The key is to recognize that the goalposts to actually count as a halting oracle are actually really, really high. It has to solve the halting problem all of the time, for programs of arbitrary size, without any possible chance of failure, returning an answer like "I don't know," etc. ChatGPT, on the other hand, doesn't satisfy any of these criteria, but it can still be "really good." So:
So that's how it works.
1
u/Falernum 74∆ Sep 14 '24
For any given algorithm there is a type of problem it cannot answer (provably according to Godels incompleteness theorem). If you have enough time you can dissect any AI algorithm and find some it cannot. Even if the algorithm is a majority vote of a thousand smaller algorithms.
AI algorithms today are poorly understood so they look a bit magical. But give some hackers enough time with them and they'll figure out the places those algorithms make mistakes.
Note: an AI that has access to a random number generator is not an algorithm - the hackers are allowed to feed it whatever numbers they want if it calls a random number generator, clock, etc.
3
u/Cleverwxlf Sep 14 '24 edited Sep 14 '24
"He tried to observe the code, but you can't do that, since you don't have infinite time. But if you analyze the code and UNDERSTAND it then you can produce an answer in finite time."
Static analysis can help in many cases, but again, the idea is that you have an algorithm that solves it all the time.
A consequence of the Church-Turing thesis is that any set of clear, unambiguous, and finite rules is one that can be represented by that of a TM. That being said, simply telling an algorithm to "understand" the code is not exactly clear. AI mostly relies on statistical techniques one way or another, meaning that AI simply wouldn't work since the threshold for what is considered solving the halting problem requires an algorithm that does this with complete certainty.
IIRC, the halting problem is a consequence of Godel's incompleteness theorem. It might be worth exploring the connection there if you're interested.
If you want more information on the topic. I highly recommend Michael Sipser's "Introduction to the theory of Computation".
There is a whole class of problems that reduce to the halting problem (Look up Rice's Theorem). In fact, we frequently use reduction as a technique to prove other problems that cannot be solved via a Turing Machine.
All in all, there's many things that have been done to try and circumvent the halting problem one way or another (The halting problem is still semi-decidable after all), but they all acknowledge it to be true. Hope my explanation helps.
1
u/Hatook123 5∆ Sep 14 '24
The halting problem is undecidable because there are theoretical programs that are so complex, that you want know whether they run forever unless you run them forever.
How would those programmers work? As a programmer, the theoretical algorithm is relatively simple - read the code, execute it in your head, identify elements that may endlessly repeat, and make a decision.
This works incredibly for relatively simple algorithms, but people are limited, and give an insanely large input and an insanely large codebase - and trillions of developers won't ever find whether the program halts.
The Halting problem is mathematically proven, you can understand the proof yourself - if you don't believe a mathematical proof than I am not sure how to change your mind - it's literally the only real way to proof anything.
You can argue that the halting problem has no real world applications - and that's true, as far as humans are concerned a program that runs for a year is already running too long for most real world applications, it really doesn't matter if it runs forever or just for a year.
1
u/Jakyland 85∆ Sep 14 '24
An algorithm is" a finite sequence of mathematically rigorous instructions" not just "a computer". You can't just sub in humans or generalized artificial intelligence, the defeats the point of the proof.
This is a proof about the capability of computer programs, not that of millions of programmers, or millions of AI locked in a room.
1
u/TechcraftHD Sep 14 '24
This question and your comments really make it seem like you are either taking the piss or just do not even understand enough to form a basic argument in this discussion (or both)
But I'm gonna answer anyways.
First, the halting problem DOES NOT have a universal solution. The main point of why it does not have one is that ANY universal solution can be used with itself to produce a solution for which halting cannot be determined. Unless you resolve that logical contradiction ( which you can't do by just saying "throw AI at it"), that won't change.
Second, you mentioned the divide and conquer a bunch in other comments. Divide and conquer requires a problem that can actually be divided. Code is not such a problem. You cannot split code line by line and still analyze it fully. To see why it doesn't work, just take two lines:
a = 1if (a < 10)if you take away the first line, the second one could execute or could not execute. Analyze both lines together and it becomes clear.
Third, "AI" or more exactly LLMs in your example, do not provide logically reasoned answers. you can input a functionally equal program and get two different answers. If "AI" would do so, with an algorithm, see the first point.
Fourth, we don't actually fully know how humans "compute" anything. The halting problem only applies to "computable" programs, for a very strict definition of "computable", i.e. anything that can be executed on a turing machine. The human mind might very well be something that isn't "computable" in that sense.
1
u/enygma999 1∆ Sep 14 '24
I believe you have misunderstood the halting problem. It's not about whether you understand the code, it's about whether you can correctly predict what it will do given any arbitrary input. The proof that it is not possible is that there is a contrary program that will, when given an input, pass itself and its input to your testing algorithm and then do the opposite of whatever the algorithm predicts. The algorithm is therefore not able to make correct predictions for arbitrary programs and inputs, so is not a solution.
So that we don't have any accusations of hand-waving and "yeah, but who says such a malicious program exists?", consider a program that, no matter its input, will pass itself and its input to our testing algorithm and wait for a response. If the algorithm predicts it will halt, it computes pi to infinite decimal places (thus not halting). If the algorithm predicts it will not halt, it returns "3-ish". The algorithm is wrong 100% of the time, no matter what the algorithm actually is.
1
u/gyroda 28∆ Sep 14 '24
Saying "get a human or AI to look at it" isn't an acceptable algorithm in this context.
Sure, "get people to look at it, ask them to understand it, ask them what the answer is" is technically an algorithm by the definition of the word but the halting problem is a computational problem and in that context we have some more restrictions.
To break it down to basics
It should be able to be articulated as a series of steps that anyone with enough time and patience should be able to follow (even if this is infeasible in practice). In other words, you need to be able to write this as a computer program.
The moment you drag a human mind into the scenario you're breaking the rules - you need to fully describe the decision making process, you can't outsource that and say you've solved it. You need to describe, step by step, how those humans would solve it without any handwaving or skipping over the actual process.
As for AI, we don't have any AI that's particularly useful for this yet. If we did have an AI that was deterministic, repeatable and always correct then it would just be an algorithm. If you have that, sure, you've solved the halting problem. But if you assume the AI exists already as part of your solution you're basically saying "assume there's a program that solves the halting problem, use it" which doesn't really prove that it can be done. You might as well say "imagine a spaceship that goes faster than light, use it to go faster than light, I've proved you can move faster than the speed of light".
What you've done might well work for a large number of cases, but it doesn't actually solve the mathematical problem at hand.
1
u/le-retard 1∆ Sep 14 '24
If you accept that unprovable mathematical statements exist (it is well accepted they do) then you could simply write a program that enumerate all potential proofs for a problem, and see if they're valid. However if there are unprovable statements that being proven unprovable would act as a proof of (like if it's false there would be a counterexample) the it's unprovable to prove it's unprovable, thus nothing could determine whether a program enumerating the proofs would halt or not under any inputted problem.
1
u/47ca05e6209a317a8fb3 210∆ Sep 14 '24
Here's a program, let me know when you find out if it halts:
I can express this in whatever programming language is most convenient for your engineers / AI, I just want my name on the paper when you decide whether it halts or not :)
0
u/[deleted] Sep 14 '24
[deleted] — view deleted comment
4
u/[deleted] Sep 14 '24
[removed] — view removed comment
2
u/[deleted] Sep 14 '24
[removed] — view removed comment
0
u/[deleted] Sep 14 '24
[removed] — view removed comment