Path: csiph.com!news.mixmin.net!eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: olcott Newsgroups: comp.theory,sci.logic,comp.ai.philosophy Subject: Re: ChatGPT agrees that the halting problem input can be construed as an incorrect question Date: Sun, 18 Jun 2023 13:47:44 -0500 Organization: A noiseless patient Spider Lines: 236 Message-ID: References: <871qi9oky8.fsf@bsb.me.uk> <5FGjM.3718$a0G8.2055@fx34.iad> <0WHjM.9605$8fUf.6382@fx16.iad> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Sun, 18 Jun 2023 18:47:46 -0000 (UTC) Injection-Info: dont-email.me; posting-host="b050d2502bb641b27f2af347a7fa563d"; logging-data="1826554"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18yMhC1kEdRMD7bCilEsl7y" User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:102.0) Gecko/20100101 Thunderbird/102.12.0 Cancel-Lock: sha1:mOmjurivbPGp1qNyplFrP5YNsjY= In-Reply-To: <0WHjM.9605$8fUf.6382@fx16.iad> Content-Language: en-US Xref: csiph.com comp.theory:64954 sci.logic:254579 comp.ai.philosophy:29745 On 6/18/2023 1:20 PM, Richard Damon wrote: > On 6/18/23 2:05 PM, olcott wrote: >> On 6/18/2023 12:46 PM, Richard Damon wrote: >>> On 6/18/23 1:09 PM, olcott wrote: >>>> On 6/18/2023 11:54 AM, Richard Damon wrote: >>>>> On 6/18/23 12:41 PM, olcott wrote: >>>>>> On 6/18/2023 11:31 AM, Richard Damon wrote: >>>>>>> On 6/18/23 10:32 AM, olcott wrote: >>>>>>>> On 6/18/2023 7:02 AM, Richard Damon wrote: >>>>>>>>> On 6/17/23 11:10 PM, olcott wrote: >>>>>>>>>> On 6/17/2023 9:57 PM, Richard Damon wrote: >>>>>>>>>>> On 6/17/23 10:29 PM, olcott wrote: >>>>>>>>>>>> On 6/17/2023 8:31 PM, Richard Damon wrote: >>>>>>>>>>>>> On 6/17/23 7:58 PM, olcott wrote: >>>>>>>>>>>>>> On 6/17/2023 6:13 PM, Richard Damon wrote: >>>>>>>>>>>>>>> On 6/17/23 5:46 PM, olcott wrote: >>>>>>>>>>>>>>>> On 6/17/2023 4:09 PM, Ben Bacarisse wrote: >>>>>>>>>>>>>>>>> Richard Damon writes: >>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>> Except that the Halting Problem isn't a >>>>>>>>>>>>>>>>>> "Self-Contradictory" Quesiton, so >>>>>>>>>>>>>>>>>> the answer doesn't apply. >>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>> That's an interesting point that would often catch >>>>>>>>>>>>>>>>> students out. And >>>>>>>>>>>>>>>>> the reason /why/ it catches so many out eventually led >>>>>>>>>>>>>>>>> me to stop using >>>>>>>>>>>>>>>>> the proof-by-contradiction argument in my classes. >>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>> The thing is, it looks so very much like a >>>>>>>>>>>>>>>>> self-contradicting question >>>>>>>>>>>>>>>>> is being asked.  The students think they can see it >>>>>>>>>>>>>>>>> right there in the >>>>>>>>>>>>>>>>> constructed code: "if H says I halt, I don't halt!". >>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>> Of course, they are wrong.  The code is /not/ there. >>>>>>>>>>>>>>>>> The code calls a >>>>>>>>>>>>>>>>> function that does not exist, so "it" (the constructed >>>>>>>>>>>>>>>>> code, the whole >>>>>>>>>>>>>>>>> program) does not exist either. >>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>> The fact that it's code, and the students are almost >>>>>>>>>>>>>>>>> all programmers and >>>>>>>>>>>>>>>>> not mathematicians, makes it worse.  A mathematician >>>>>>>>>>>>>>>>> seeing "let p be >>>>>>>>>>>>>>>>> the largest prime" does not assume that such a p >>>>>>>>>>>>>>>>> exists. So when a >>>>>>>>>>>>>>>>> prime number p' > p is constructed from p, this is not >>>>>>>>>>>>>>>>> seen as a >>>>>>>>>>>>>>>>> "self-contradictory number" because neither p nor p' >>>>>>>>>>>>>>>>> exist. But the >>>>>>>>>>>>>>>>> halting theorem is even more deceptive for programmers, >>>>>>>>>>>>>>>>> because the >>>>>>>>>>>>>>>>> desired function, H (or whatever), appears to be so >>>>>>>>>>>>>>>>> well defined -- much >>>>>>>>>>>>>>>>> more well-defined than "the largest prime".  We have an >>>>>>>>>>>>>>>>> exact >>>>>>>>>>>>>>>>> specification for it, mapping arguments to returned >>>>>>>>>>>>>>>>> values. It's just >>>>>>>>>>>>>>>>> software engineering to write such things (they >>>>>>>>>>>>>>>>> erroneously assume). >>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>> These sorts of proof can always be re-worded so as to >>>>>>>>>>>>>>>>> avoid the initial >>>>>>>>>>>>>>>>> assumption.  For example, we can start "let p be any >>>>>>>>>>>>>>>>> prime", and from p >>>>>>>>>>>>>>>>> we construct a prime p' > p.  And for halting, we can >>>>>>>>>>>>>>>>> start "let H be >>>>>>>>>>>>>>>>> any subroutine of two arguments always returning true >>>>>>>>>>>>>>>>> or false". Now, >>>>>>>>>>>>>>>>> all the objects /do/ exist.  In the first case, the >>>>>>>>>>>>>>>>> construction shows >>>>>>>>>>>>>>>>> that no prime is the largest, and in the second it >>>>>>>>>>>>>>>>> shows that no >>>>>>>>>>>>>>>>> subroutine computes the halting function. >>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>> This issue led to another change.  In the last couple >>>>>>>>>>>>>>>>> of years, I would >>>>>>>>>>>>>>>>> start the course by setting Post's correspondence >>>>>>>>>>>>>>>>> problem as if it were >>>>>>>>>>>>>>>>> just a fun programming challenge.  As the days passed >>>>>>>>>>>>>>>>> (and the course >>>>>>>>>>>>>>>>> got into more and more serious material) it would start >>>>>>>>>>>>>>>>> to become clear >>>>>>>>>>>>>>>>> that this was no ordinary programming challenge.  Many >>>>>>>>>>>>>>>>> students started >>>>>>>>>>>>>>>>> to suspect that, despite the trivial sounding >>>>>>>>>>>>>>>>> specification, no program >>>>>>>>>>>>>>>>> could do the job.  I always felt a bit uneasy doing >>>>>>>>>>>>>>>>> this, as if I was >>>>>>>>>>>>>>>>> not being 100% honest, but it was a very useful >>>>>>>>>>>>>>>>> learning experience for >>>>>>>>>>>>>>>>> most. >>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>> sci.logic Daryl McCullough Jun 25, 2004, 6:30:39 PM >>>>>>>>>>>>>>>>     You ask someone (we'll call him "Jack") to give a >>>>>>>>>>>>>>>> truthful >>>>>>>>>>>>>>>>     yes/no answer to the following question: >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>     Will Jack's answer to this question be no? >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>     Jack can't possibly give a correct yes/no answer to >>>>>>>>>>>>>>>> the question. >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>> It is an easily verified fact that when Jack's question >>>>>>>>>>>>>>>> is posed to Jack >>>>>>>>>>>>>>>> that this question is self-contradictory for Jack or >>>>>>>>>>>>>>>> anyone else having >>>>>>>>>>>>>>>> a pathological relationship to the question. >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> But the problem is "Jack" here is assumed to be a >>>>>>>>>>>>>>> volitional being. >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> H is not, it is a program, so before we even ask H what >>>>>>>>>>>>>>> will happen, the answer has been fixed by the definition >>>>>>>>>>>>>>> of the codr of H. >>>>>>>>>>>>>>> >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>> It is also clear that when a question has no yes or no >>>>>>>>>>>>>>>> answer because >>>>>>>>>>>>>>>> it is self-contradictory that this question is aptly >>>>>>>>>>>>>>>> classified as >>>>>>>>>>>>>>>> incorrect. >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> And the actual question DOES have a yes or no answer, in >>>>>>>>>>>>>>> this case, since H(D,D) says 0 (non-Halting) the actual >>>>>>>>>>>>>>> answer to the question does D(D) Halt is YES. >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> You just confuse yourself by trying to imagine a program >>>>>>>>>>>>>>> that can somehow change itself "at will". >>>>>>>>>>>>>>> >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>> It is incorrect to say that a question is not >>>>>>>>>>>>>>>> self-contradictory on the >>>>>>>>>>>>>>>> basis that it is not self-contradictory in some >>>>>>>>>>>>>>>> contexts. If a question >>>>>>>>>>>>>>>> is self-contradictory in some contexts then in these >>>>>>>>>>>>>>>> contexts it is an >>>>>>>>>>>>>>>> incorrect question. >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> In what context is "Does the Machine D(D) Halt When run" >>>>>>>>>>>>>>> become self-contradictory? >>>>>>>>>>>>>> When this question is posed to machine H. >>>>>>>>>>>>>> >>>>>>>>>>>>>> Jack could be asked the question: >>>>>>>>>>>>>> Will Jack answer "no" to this question? >>>>>>>>>>>>>> >>>>>>>>>>>>>> For Jack it is self-contradictory for others that are not >>>>>>>>>>>>>> Jack it is not self-contradictory. Context changes the >>>>>>>>>>>>>> semantics. >>>>>>>>>>>>>> >>>>>>>>>>>>> >>>>>>>>>>>>> But you are missing the difference. A Decider is a fixed >>>>>>>>>>>>> piece of code, so its answer has always been fixed to this >>>>>>>>>>>>> question since it has been designed. Thus what it will say >>>>>>>>>>>>> isn't a varialbe that can lead to the self-contradiction >>>>>>>>>>>>> cycle, but a fixed result that will either be correct or >>>>>>>>>>>>> incorrect. >>>>>>>>>>>>> >>>>>>>>>>>> >>>>>>>>>>>> Every input to a Turing machine decider such that both >>>>>>>>>>>> Boolean return >>>>>>>>>>>> values are incorrect is an incorrect input. >>>>>>>>>>>> >>>>>>>>>>> >>>>>>>>>>> Except it isn't. The problem is you are looking at two >>>>>>>>>>> different machines and two different inputs. >>>>>>>>>>> >>>>>>>>>> If no one can possibly correctly answer what the correct >>>>>>>>>> return value that any H having a pathological relationship >>>>>>>>>> to its input D could possibly provide then that is proof >>>>>>>>>> that D is an invalid input for H in the same way that >>>>>>>>>> any self-contradictory question is an incorrect question. >>>>>>>>>> >>>>>>>>> >>>>>>>>> But you have the wrong Question. The Question is Does D(D) >>>>>>>>> Halt, and that HAS a correct answer, since your H(D,D) returns >>>>>>>>> 0, the answer is that D(D) does Halt, and thus H was wrong. >>>>>>>>> >>>>>>>> sci.logic Daryl McCullough Jun 25, 2004, 6:30:39 PM >>>>>>>>     You ask someone (we'll call him "Jack") to give a truthful >>>>>>>>     yes/no answer to the following question: >>>>>>>> >>>>>>>>     Will Jack's answer to this question be no? >>>>>>>> >>>>>>>> For Jack the question is self-contradictory for others that >>>>>>>> are not Jack it is not self-contradictory. >>>>>>>> >>>>>>>> The context (of who is asked) changes the semantics. >>>>>>>> >>>>>>>> Every question that lacks a correct yes/no answer because >>>>>>>> the question is self-contradictory is an incorrect question. >>>>>>>> >>>>>>>> If you are not a mere Troll you will agree with this. >>>>>>>> >>>>>>> >>>>>>> But the ACTUAL QUESTION DOES have a correct answer. >>>>>> The actual question posed to Jack has no correct answer. >>>>>> The actual question posed to anyone else is a semantically >>>>>> different question even though the words are the same. >>>>>> >>>>> >>>>> But the question to Jack isn't the question you are actaully saying >>>>> doesn't have an answer. >>>>> >>>> The question posed to Jack does not have an answer because within the >>>> context that the question is posed to Jack it is self-contradictory. >>>> You can ignore that context matters yet that is not any rebuttal. >>>> >>> >>> Right, but that has ZERO bearig on the Halting Problem, >> That is great we made excellent progress on this. >> >> When ChatGPT understood that Jack's question is self-contradictory for >> Jack then it was also able to understand the following isomorphism: >> >> For every H on pathological input D both Boolean return values >> from H are incorrect for D proving that D is isomorphic to a >> self-contradictory question for every H. >> > > No, because a given H can only give one result, Some of the elements of H/D are identical except for the return value from H. In both of these cases the return value is incorrect. Since I have just defined the set of every halting problem {decider / input} pair that can possibly exist in any universe there is no rebuttal of: What about this element of this set? -- Copyright 2023 Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer