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 09:32:22 -0500 Organization: A noiseless patient Spider Lines: 186 Message-ID: References: <871qi9oky8.fsf@bsb.me.uk> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Sun, 18 Jun 2023 14:32:24 -0000 (UTC) Injection-Info: dont-email.me; posting-host="b050d2502bb641b27f2af347a7fa563d"; logging-data="1776445"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/8KqHLbqk1zN/IwvyzlrrV" User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:102.0) Gecko/20100101 Thunderbird/102.12.0 Cancel-Lock: sha1:q/Z/sgyYwZIXgwCREHoNi0x9vis= In-Reply-To: Content-Language: en-US Xref: csiph.com comp.theory:64943 sci.logic:254548 comp.ai.philosophy:29735 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. -- Copyright 2023 Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer