In the proof of the halting problem you can make a grid if Turing machines along a vertical axis and the description of a TM on the horizontal axis. The assumption is this is a list of all computable programs and whether they halt or not for a specific TM on a specific input description. Then you take the diagonal and reverse producing a TM that isn't anywhere in the list, thus proving the undecidability of the Halting problem.
Sometimes this proof is described as meta machine that says if a TM on an input halts, then the meta machine will say it loops, and if the program on an input loops, then the meta machine will say it halts.
What I don't get is why can't you construct such a metamachine that does the above and then another program that takes input this meta machine and does the opposite and thus gives the correct answer?
If metamachine says halt, you know for a fact the program loops forever. If the metamachine says loop, you know for a fact the program halts since the metamachine gives the opposite answer, this new machine gives the correct answer.
because it still doesn't get rid of the fact that there is (there could be) a machine that contradicts the whole thing
Julian Jones
The Halting problem is another one of those problems that arises from set theory regarding infinite sets. You can't fix it.
Lets assume that I did have a list of all possible computable programs X. We will assume that all programs not in X are not computable. I now want to design a computable program A() that will tell me if any of the members of X halt.
One problem, is A(X) a member of X? If it isn't, then A(X) isn't a computable program and therefore I'd be wasting my time trying to compute it, it would halt. So we should push forward with the assumption that A(X) is a member of X.
if A(X) halts, A(A(X)) halts, A(A(A(X))) halts, A(A(A(A(X)))) halts, and so on
The list of computable programs X is infinite, because it contains at least as many elements as A^n(X) where n is infinite, assuming A(X) halts.
Since X can be infinitely extended, there is no such program B in X that can generate X.
You should conclude that my first assumption, which was that I had a complete list X of all computable programs, is impossible.
Cameron Carter
>One problem, is A(X) a member of X? If it isn't, then A(X) isn't a computable program and therefore I'd be wasting my time trying to compute it, it would halt *wouldn't halt my bad
Asher Jackson
The problem is you need to first prove the Metamachine is correct, and to do that you need to prove Meta-Metamachine, Meta-Meta-Metamachine, and so on.
In other words, it's impossible because there's only a finite number of atoms in the universe.
If we can prove that the big bang happened in all directions, perhaps that means such a Metamachine is possible. If P = NP then the set of all prime numbers will collapse so that would violate the laws of Turing Machines.
Gavin Garcia
isn't it impossible also because of the fact that a turing machine could not terminate, ever and you can never have a point where you stop and say "this halts" since that moment will never arrive?
Alexander Sanders
>The Halting problem is another one of those problems that arises from set theory regarding infinite sets. You can't fix it. Even simpler: the Halting problem is an instance of the obvious truth that there's not always an easier way of finding out any part of what an algorithm's result will be than running it all the way to the end. Or more tersely: there's not always an easier way.
If you want to know whether an program halts, you're trying to find out something about its result. Running the program itself may be the most efficient possible way to get that information.
You can certainly make an algorithm that always halts extracts a lot of information about whether arbitrary programs halt, but it's always going to have to have the possibility of answering with a shrug for some inputs, or else in some cases it may continue exploring the problem forever.
Also: real computers are finite state machines, not turing machines (they have finite memory, not an infinite tape), so the halting problem doesn't apply to them. You can always analyse whether a program on a real computer will halt in a finite time on another computer with finite memory, if not necessarily within a practical amount of time on a computer which can be built in the real universe.
Samuel Campbell
bump
Ryan Wood
In my opinion it's not enough for a proof since you can just argue against it with a turing machine which analyzes the input machine for circuits and if the machine gets into one it will stop.
Liam Powell
I guess you're right. From this point that you've mentioned it is easy to understand why the previous explanations from this thread are the proper solutions.
Chase Gonzalez
So, is this the reason why my (OP) not correct My idea is,
You construct a program M that takes in a Program and input and gives the correct solution of whether it halts or not so..
M(P,i) ={ output "halt" if programs halts, otherwise output "loops" if program loops forever
Then you construct a meta machine that takes in M(P,i) called Meta
Meta(M(P,i)) ={ output "halts" if input loops, output "loops" if program halts
now take a Meta-Meta machine that does the following:
Meta-Meta(Meta(M(P,i)) ={ output "halts" if input loops, output "loops" if program halts
Now why wouldn't Meta-Meta give you the correct answer every time since it just negates the meta machine? I don't understand still.
Jack Adams
Ok, now prove that that circuit-detecting TM will always halt. :^)
Julian Carter
>Sometimes this proof is described as meta machine that says if a TM on an input halts, then the meta machine will say it loops, and if the program on an input loops, then the meta machine will say it halts. No. No such machine is involved in any of the standard proofs of the halting problem. I strongly suspect you misunderstand the proof.
Brody Campbell
Then state the correct proof instead of simply pointing out an error.Otherwise you contributed nothing to the thread
Leo Scott
The correct proof goes like this:
Assume there is a program H(M, i) that for a Turing machine M and input i will return true if M(i) halts --that is, if running M with input i halts-- and false otherwise.
Then we can construct a program P(M) that for a Turing machine M computes H(M, M). That is, it computes --using the H program-- whether M will halt when given its own description as input. If H(M, M) returns true, meaning that M(M) halts, P(M) goes into an infinite loop. If H(M, M) returns false, meaning that M(M) does not halt, P(M) halts.
Now consider what happens if we call P(P). The P program, per the above construction, will call H(P, P) to find out whether P(P) halts. If P(P) halts, the program will then enter an infinite loop. If P(P) does not halt, the program will halt.
But that means that if H(P, P) has determined that P(P) halts, P(P) does not halt; and if H(P, P) has determined that P(P) does not halt, P(P) halts. Thus, however you slice it, H has computed the wrong answer for H(P, P).
But by assumption, H computes the correct answer, which means we have arrived at a contradiction. Which means that our assumption --the existence of a program H that solves the halting problem-- must be false. Which means no such program can exist; for if you give me one, I can immediately construct a case for which it returns the wrong answer.
Ethan Myers
Thanks for giving such a well-written proof. My question is... you specifically designed P(P) to do the opposite of what H(P,P) (correctly) outputs.
So, why cannot I use the argument that your design of P(P) is flawed, since you are purposely producing a nonsensical program? In other words, why can I not say to simply negate the answer of what P(P) produces and use that as the "true" answer since all P(P) does negate H(P,P)'s correct output?
It seems like you could easily say if P(P) produced a 1 (for halt) then flip it to a 0 (doesn't halt) and that's your answer, for P(P)=0 then flip the bit to 1 and that's the correct answer since P(P) just negates the correct answer.
Can you explain why this isn't a fix?
Jackson Howard
Your negated program is still a program and can be manipulated to produce the same contradiction.
And there's nothing nonsensical about the program used in the proof. It's simply showing the halting problem cannot be decided for ALL inputs, not that the halting problem cannot be decided for SOME inputs.
Logan White
Okay, that makes sense because there isn't anything to prevent me from defining a meta-meta-meta madhine that negates my meta-meta machine and so on.
Whenever you say it proves it cannot be decided for all inputs is this true even on some empty input? I.e say you are given a machine M with input nothing. M() then ask the question if this program halts.
Also, "in real life" is it not true we can decide whether some trivially simple programs halt or not on some input? How does the halting problem apply to that?
I don't mean to play devils advocate but I have these sorts of questions before I fully understand the correct proof and it's applications in my mind. I really appreciate your high quality answers here.
Noah Turner
...
Wyatt Mitchell
>So, why cannot I use the argument that your design of P(P) is flawed, since you are purposely producing a nonsensical program? What does that change? The point of the proof is that it shows that a program exists for which H provides the wrong answer, which means that there cannot exist an H that always answers correctly. Sure, P is a weird nasty artificial thing. But that does not change the fact that no such H can exist.
>Whenever you say it proves it cannot be decided for all inputs is this true even on some empty input? I.e say you are given a machine M with input nothing. M() then ask the question if this program halts. Yes. The proof for this is a bit trickier and more technical, but the same thing still applies for empty inputs.
>Also, "in real life" is it not true we can decide whether some trivially simple programs halt or not on some input? How does the halting problem apply to that? Certainly!
The proof above says that it's impossible to create a program that will compute for *any possible program* (and input) whether it halts. It is definitely possible to make a program that *tries* to analyze a program to see whether it halts, and then either answers "this halts", "this does not halt", or "i dunno". You can make such a program quite powerful, and make it so that it can prove halting for almost all sensible programs, and only answer "i dunno" for weird edge cases.
What is not possible, per the proof, is to make a program that shows halting or non-halting for ALL POSSIBLE programs. In other words, it shows that any attempt at solving the halting problem must always be *incomplete*, and not be able to understand some particular possible programs.
Brayden Jones
Excellent reply. Thank you so so so much for your high quality answers. I absolutely learned a lot from you. Your answers really helped tremendously.
The professor writes on the board "behavior of H on input M_i,.
Can you decipher what that notation means?
It looks to me to say: H(M_i, ) which means Turing machine H takes in as input the program M_i that has input M_j. But I do not understand what is mean by the < >. The professor refers to it as the "description of M_j" (which he says is a binary string iirc). What is the difference between say turing machine M_i and the "description of Turing machine M_i"?
Pic related
Nicholas Phillips
I'm struggling to understand this. The supposed set was countably infinite before and after being 'infinitely extended' it has the same cardinality
Leo Anderson
Bump
Hunter Myers
Bump
Parker Rogers
The point is there's no computable program that could create a list of all computable programs, because the cardinality of said list is infinite. No computer can create it in a finite amount of time. Therefore the generation program doesn't halt, and it isn't a member of the list it supposedly generates.
Which begs the question "how did I get the list?" Certainly I can't have computed it. And if I claimed I had a list which was supposedly complete, it wouldn't be possible to use a computer to check if it was complete. Also the list would be quite heavy and it might break my skinny bitch arms.
Nicholas Cook
Bump on my question
Jace Anderson
I'm sorry, I must be being a huge brainlet right now. That set has the same cardinality as the naturals and I could easily construct a machine to enumerate naturals. What am I getting wrong here?
Wyatt Price
If someone could answer this question I'd stop bumping thread.
Jeremiah Moore
>Also, "in real life" is it not true we can decide whether some trivially simple programs halt or not on some input? How does the halting problem apply to that?
Of course. You could easily think about some class of programs where you can easily decide whether it will halt or not.
However, the halting problem is specifically about deciding whether a GENERAL TM will halt. It's not about whether you can decide that there exists some TM where you can decide that it halts. Instead you want to know whether you can take any arbitrary TM and decide whether it halts.
Carson Jackson
Look up Gödel numbers for turing machines. Essentially, it's a kind of "trick" that formally allows you to pass a turing machine as an input to another turing machine by generating a binary string that describes a turing machine.
Colton Gomez
>can create it in a finite amount of time
So as some example checking every number ever to see what number is prime, is considered not halting, because you will stay forever checking those numbers?
Nolan Lopez
You can't even make a complete list of "those numbers" because the list is infinite
Lincoln James
I can decide whether or not any given Turing machine will halt.
William Sanchez
doesn't mean you can't make a program that checks all of them
Joshua Davis
What does it mean for a TM to take as string input the description of another TM?
Jaxon Butler
Formally, the only input a turing machine takes is some string made up of symbols from their input alphabet (typically just 0s and 1s). So if you want to have some turing machine that takes another turing machine as an input like in , you have to have some way to encode a turing machine in the input alphabet. That's all that means. It means the turing machine M encoded in some appropriate string of 0s and 1s.
Incidentally, if you can show this is possible in a finite amount of symbols, it also tells you that the set of all turing machines is countably infinite, since you can just count through all binary strings and test if it is a valid encoding for a turing machine.
Nicholas Smith
What is this concept of a "computable program" you are talking about?
>The professor writes on the board "behavior of H on input M_i,. >Can you decipher what that notation means? Nothing relevant. It is a technical detail you can safely ignore. It is like the difference between the number 12345, and the digit sequence "12345".
Leo Thompson
>brainlet >had to Google half the terms >realize how much of a brainlet I am >cry
Justin Ross
There are many people posting in this thread confused about the most basic things. Please read Sipsers book. It's short, well written, and not challenging
Elijah Hernandez
>What is this concept of a "computable program" you are talking about? It's a program that will return a value, given an input, in a finite amount of time.
A program which returns the prime factors of some number n is a computable program. A program which returns the prime factors of all numbers n in N is not computable because N is infinite.
Colton Jenkins
Ah. That's usually called a halting program.
>The point is there's no computable program that could create a list of all computable programs, because the cardinality of said list is infinite. No computer can create it in a finite amount of time. Therefore the generation program doesn't halt, and it isn't a member of the list it supposedly generates. While it's true that there is no such halting program, that is NOT the real point. The real point is that you can't write a halting program that generates prefixes of the sequence of all halting programs either.
You can make a program that generates all prime numbers in increasing order, and this program does not halt; and you can also create a program that generates the first N prime numbers in increasing order, and that program does halt.
But you can NOT write a program that generates the first N halting programs, in whatever order. That would involve a halting decider. The thing about the program that enumerates all halting programs is a red herring.
Jonathan Cruz
>What I don't get is why can't you construct such a metamachine that does the above and then another program that takes input this meta machine and does the opposite and thus gives the correct answer? This doesn't solve the problem of the original machine's contradictory existence.
Compare it to diagonolization with reals. I suppose there is a bijection f:N->R, then I construct a real number x where the ith digit of x is different than ith digit of f(i), but x is a real so f(j)=x so what happens at the jth digit of x? Your nested "meta machine" idea is like taking the construction of x and changing it so it matches ith digit of f(i), then problem at jth digit goes away. But that's immaterial to the fact that the existence of f leads to a contradiction.
This doesn't seem correct to me, or you're muddling terminology. The infinity of the set isn't the issue, there are infinite sets that are decidable.
>Whenever you say it proves it cannot be decided for all inputs is this true even on some empty input? I.e say you are given a machine M with input nothing. M() then ask the question if this program halts. It still can't be decided. If you can decide whether a programs halts on empty input then you can solve general halting problem. To do this you just construct a modified program that ignores input and uses your hardcoded string instead.
Michael Wood
Okay thanks. When you do the diagonalizarion proof (one where you assume all computable programs are enumerably infinite and generate A new string list of computable programs (that simply changes the accept/reject state along the diagonals) and see that this string is not in your initial list, does this not only prove the halting problem but also that there are an uncountable amount of undecidable problems?
Ian Baker
Okay thanks re: question on TM descriptions
Kayden Carter
Assuming you are talking about the same proof I am thinking about, all it shows is that there exist some problems that are not even recursively enumerable. It does this by constructing one such problem using diagonalization.
Diagonalization by itself doesn't necessarily prove that something is uncountable.
Adam Taylor
What the fuck?
Daniel Ramirez
>If metamachine says halt, you know for a fact the program loops forever. If the metamachine says loop, you know for a fact the program halts since the metamachine gives the opposite answer, this new machine gives the correct answer. >Why is this not a fix for the Halting problem?
Let's say your program is function metamachine_halt. I can simply do:
func breaks_everything x = if metamachine_halt(x) then loop forever else halt => breaks_everything(breaks_everything) maintains original contradiction of halting problem
The idea of the halting problem proof is that it represents a fundamental issue with the way we define truth. It's not an engineering problem. Is "Everything I say is a lie" true or false?
