Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Mr Flibble <flibble@reddwarf.jmc> |
|---|---|
| Newsgroups | comp.theory |
| Subject | Re: On recursion and infinite recursion (reprise #3) |
| Message-ID | <20220508230420.0000053f@reddwarf.jmc> (permalink) |
| References | (17 earlier) <9ITdK.2055$wYy9.1130@fx11.iad> <20220508200637.0000491c@reddwarf.jmc> <U%UdK.8711$t72a.8053@fx10.iad> <20220508211421.000031a0@reddwarf.jmc> <ENWdK.7593$VwRc.5901@fx01.iad> |
| Organization | Jupiter Mining Corp |
| Date | 2022-05-08 23:04 +0100 |
On Sun, 8 May 2022 17:40:52 -0400 Richard Damon <Richard@Damon-Family.org> wrote: > On 5/8/22 4:14 PM, Mr Flibble wrote: > > On Sun, 8 May 2022 15:39:32 -0400 > > Richard Damon <Richard@Damon-Family.org> wrote: > > > >> On 5/8/22 3:06 PM, Mr Flibble wrote: > >>> On Sun, 8 May 2022 14:10:13 -0400 > >>> Richard Damon <Richard@Damon-Family.org> wrote: > >>> > >>>> On 5/8/22 8:39 AM, Mr Flibble wrote: > >>>>> On Sun, 8 May 2022 08:31:10 -0400 > >>>>> Richard Damon <Richard@Damon-Family.org> wrote: > >>>>> > >>>>>> On 5/8/22 8:02 AM, Mr Flibble wrote: > >>>>>>> On Sun, 8 May 2022 07:45:52 -0400 > >>>>>>> Richard Damon <Richard@Damon-Family.org> wrote: > >>>>>>> > >>>>>>>> On 5/8/22 4:49 AM, Mr Flibble wrote: > >>>>>>>>> On Sun, 8 May 2022 11:31:08 +0300 > >>>>>>>>> Mikko <mikko.levanto@iki.fi> wrote: > >>>>>>>>> > >>>>>>>>>> On 2022-05-07 15:19:01 +0000, Mr Flibble said: > >>>>>>>>>> > >>>>>>>>>>> On Sat, 7 May 2022 18:13:08 +0300 > >>>>>>>>>>> Mikko <mikko.levanto@iki.fi> wrote: > >>>>>>>>>>> > >>>>>>>>>>>> On 2022-05-07 14:20:17 +0000, Mr Flibble said: > >>>>>>>>>>>> > >>>>>>>>>>>>> On Sat, 7 May 2022 17:16:31 +0300 > >>>>>>>>>>>>> Mikko <mikko.levanto@iki.fi> wrote: > >>>>>>>>>>>>> > >>>>>>>>>>>>>> On 2022-05-07 14:06:12 +0000, Mr Flibble said: > >>>>>>>>>>>>>> > >>>>>>>>>>>>>>> On Sat, 7 May 2022 16:59:55 +0300 > >>>>>>>>>>>>>>> Mikko <mikko.levanto@iki.fi> wrote: > >>>>>>>>>>>>>>> > >>>>>>>>>>>>>>>> On 2022-05-07 12:42:50 +0000, Mr Flibble said: > >>>>>>>>>>>>>>>> > >>>>>>>>>>>>>>>>> On Sat, 7 May 2022 12:52:58 +0300 > >>>>>>>>>>>>>>>>> Mikko <mikko.levanto@iki.fi> wrote: > >>>>>>>>>>>>>>>>> > >>>>>>>>>>>>>>>>>> On 2022-05-06 14:02:53 +0000, Mr Flibble said: > >>>>>>>>>>>>>>>>>> > >>>>>>>>>>>>>>>>>>> The decider could never be compiled and run in the > >>>>>>>>>>>>>>>>>>> first place due to the category error in the > >>>>>>>>>>>>>>>>>>> definition of the proof. > >>>>>>>>>>>>>>>>>> > >>>>>>>>>>>>>>>>>> An error in the definition of the proof does not > >>>>>>>>>>>>>>>>>> prevent compilation and execution of the program. > >>>>>>>>>>>>>>>>> > >>>>>>>>>>>>>>>>> In this case the error in the definition of the > >>>>>>>>>>>>>>>>> proof > >>>>>>>>>>>>>>>> > >>>>>>>>>>>>>>>> No part of the proof is identified as errorneous, so > >>>>>>>>>>>>>>>> the rest is irrelevant. Anyway, > >>>>>>>>>>>>>>>> > >>>>>>>>>>>>>>>>> does prevent compilation unless > >>>>>>>>>>>>>>>> > >>>>>>>>>>>>>>>> There is no option here, so the "unless" is void. > >>>>>>>>>>>>>>>> > >>>>>>>>>>>>>>>>> the decider is made part of the program that is > >>>>>>>>>>>>>>>>> being decided > >>>>>>>>>>>>>>>> > >>>>>>>>>>>>>>>> The decider is made a part of the program discussed > >>>>>>>>>>>>>>>> in the proof. > >>>>>>>>>>>>>>>>> in which case we get a function call-like infinite > >>>>>>>>>>>>>>>>> recursion instead > >>>>>>>>>>>>>>>> > >>>>>>>>>>>>>>>> We get or we don't get, depending on how the halt > >>>>>>>>>>>>>>>> decider candidate attempts to decide. > >>>>>>>>>>>>>>>> > >>>>>>>>>>>>>>>>> (as described by Pete Olcott) and we are attempting > >>>>>>>>>>>>>>>>> (and failing) to decide if a procedure halts rather > >>>>>>>>>>>>>>>>> than if a program halts. > >>>>>>>>>>>>>>>> > >>>>>>>>>>>>>>>> In any case, the decider candidate fails to give the > >>>>>>>>>>>>>>>> correct answer, and therefore is not a halt decider. > >>>>>>>>>>>>>>>> Note that this is correctly inferred in the proof. > >>>>>>>>>>>>>>>> Therefore either the conclusion of the proof is > >>>>>>>>>>>>>>>> correct or you are wrong. > >>>>>>>>>>>>>>> > >>>>>>>>>>>>>>> No answer is ever given due to the infinite > >>>>>>>>>>>>>>> recursion. > >>>>>>>>>>>>>> > >>>>>>>>>>>>>> True about some candidates, false about others. For > >>>>>>>>>>>>>> example, a candidate that always says "no" is not > >>>>>>>>>>>>>> infinitely recursive but is wrong in the particular > >>>>>>>>>>>>>> case discussed in the proof. But anyway, you have > >>>>>>>>>>>>>> confirmed the conclusion of the proof. > >>>>>>>>>>>>> > >>>>>>>>>>>>> False. The proof is not cognisant of the presence of the > >>>>>>>>>>>>> infinite recursion. The decider can never return an > >>>>>>>>>>>>> answer of halts/doesn't halt due to the infinite > >>>>>>>>>>>>> recursion. > >>>>>>>>>>>> > >>>>>>>>>>>> The correct term is decider candidate. It is not a > >>>>>>>>>>>> decider because the infinite recursion prevents it from > >>>>>>>>>>>> halting in finite time. > >>>>>>>>>>>> > >>>>>>>>>>>> You cannot call the proof incorrect merely because it > >>>>>>>>>>>> agrees with you. > >>>>>>>>>>> > >>>>>>>>>>> Try actually reading what Strachey wrote: a contradiction > >>>>>>>>>>> arises based on the result of evaluating T[P] however T[P] > >>>>>>>>>>> is never evaluated due to the infinite recursion: a fact > >>>>>>>>>>> ignored by the proof. > >>>>>>>>>> > >>>>>>>>>> If you can prove that the program does give the correct > >>>>>>>>>> result in that case you have proven Strachey wrong. > >>>>>>>>>> Otherwise you haven't. > >>>>>>>>> > >>>>>>>>> Strachey is wrong because he neglected to account for the > >>>>>>>>> infinite recursion; this should be obvious to anyone who has > >>>>>>>>> actually read and understood what Strachey wrote: it seems > >>>>>>>>> that you haven't. > >>>>>>>>> > >>>>>>>>> /Flibble > >>>>>>>>> > >>>>>>>> > >>>>>>>> No, because if T gets stuck in an infinite recursion, it is > >>>>>>>> wrong, because it failed to answer in finite time. > >>>>>>>> > >>>>>>>> If T does answer in finite time, then there never was an > >>>>>>>> infinite recursion. > >>>>>>>> > >>>>>>>> All you have shown is that there exists a WRONG method to > >>>>>>>> build a T that gets stuck, Like a T that needs to run its > >>>>>>>> input to completion to answer about it. > >>>>>>> > >>>>>>> I have shown that [Strachey, 1965] contains an infinite > >>>>>>> recursion and is thus invalid. > >>>>>>> > >>>>>>> /Flibble > >>>>>>> > >>>>>> > >>>>>> No, you haven't. All you have shown is that one way to attempt > >>>>>> to make the program that Strachev says doesn't exist, fails > >>>>>> due to getting caught in infinite recursion. > >>>>>> > >>>>>> That just helps confirm Strachev, not refute it. > >>>>> > >>>>> Nope. Strachey's proof is based on a contradiction relating to > >>>>> evaluating the result of T[P] however T[P] can never be > >>>>> evaluated if there is an infinite recursion. > >>>>> > >>>>> /Flibble > >>>>> > >>>> > >>>> Nope, because if T actually meets the requirement to be able to > >>>> take ANY program and answer, then it need to be able to take a > >>>> program that uses a copy of T in it, as that is a valid program. > >>>> > >>>> If T gets into an infinite recursion on such a program, it is > >>>> that *T* fails to meet the requirements, not that the such a > >>>> program is invalid to give to T. > >>>> > >>>> This means that the program T is Strachey's proof can't just > >>>> execute its input to get the needed answer, as that makes it (T) > >>>> not meet its requirements. > >>>> > >>>> Thus, the "recursion" error isn't in the proof of impossibility, > >>>> but in the candidate T that is attempting to be the counter > >>>> example for the proof. > >>>> > >>>> Recursion is allowed in programming and in math. If you try to > >>>> just ban it, you will find you logic can't handle what it needs > >>>> to. > >>> > >>> You are simply wrong, and fractally so. Try reading what Strachey > >>> actually wrote. > >>> > >>> /Flibble > >>> > >> > >> I have. > >> > >> T[R] is defined to be a boolean function that returns True if > >> routine R (taking no parameters) Halts, and False if R never halts. > >> > >> Thus, for ANY input program, T must itself Halt, that requirement > >> INCLUDES if R calls T[R], so if T gerts into infinite recursion and > >> thus not answer, T has failed its specification. > >> > >> If you want to define that T can't take the R he defines, then why > >> is that NOT a program? What "rule of programs" has it violated, > >> note R getting stuck in an infinite loop is one of the purposes > >> that T is supposed to handle. > >> > >> T has no requirement that the input R halts or in fact, any > >> requirement other than it be a program. Thus the fact that R gets > >> "hung up" in an infinite recursion isn't an error in building R, > >> but it IS a error in the design of T, as T is REQUIRED, to meet its > >> definition to always answer. > >> > >> Thus, your claim about T not answering because it got stuck in an > >> infinite recursion is just a statement that a T built that way jus > >> fails to meet its requriement. > >> > >> Note, there is NO requirement in the problem that T[R] actually > >> runs R, and in fact, you are proving that it CAN'T (at least not > >> without some way to stop it) as that leads to T inherently failing > >> for this sort of program. > >> > >> Note, any "rule" you try to invent that prohibits this "impossible > >> program" must also take into account the "compliant" program C that > >> should be allowed that just calls T[C] and doesn't what it says, > >> and the two fixed behavior ones that call T with themselfs and then > >> unconditionally Halt or Loop. All three of these should be "legal" > >> as they do have definite answers that work, so arguements on > >> contrariness don't apply. > > > > You continue to be wrong and fractally so. The infinite recursion > > will ALWAYS happen according to the definition of the proof. Again: > > read AND UNDERSTAND what Strachey actually wrote. > > > > /Flibble > > > > Nope. Yes, R will call/invoke T to get a value, but T does not (and > in fact can not) invoke R to determine if it halts, so no infinite > recursion. > > Note, you are making the error of assuming that the only way to even > try to determine if a program will halt is to just run it. > > In fact, if T does do some partial running to get information, it > must strictly limit how much it allows the program to run to get the > data it needs, or it will fail to meet the requirement to decide. > > Once it has in place that sort of limit, no infinite recursion > becomes possible, because T won't partially run its input forever. > > This is just like Olcott's H, if it is going to answer, MUST abort > its simulation to give an answer, and it will always give the wrong > answer bucause it didn't get enough information, and did it analysis > with the false assumption that the copy of H in P/H^ won't abort its > simulation since it didn't simulate long enough to see it. Confusion lay with what Strachey said: "T[R] = True if R terminates if run" "if run" doesn't have to mean T[R] runs R. HOWEVER it would be nice to know what T[R] actually means in the obsolete CPL programming language Strachey is using (R is a ROUTINE passed as an argument to T a FUNCTION). Didn't spot anything obvious in http://www.ancientgeek.org.uk/CPL/CPL_Elementary_Programming_Manual.pdf but I only had a cursory look. So modulo the outcome of that CPL question I agree with you and Olcott is wrong if his mistake is the same as mine. Any other business? /Flibble
Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
On recursion and infinite recursion (reprise #3) Mr Flibble <flibble@reddwarf.jmc> - 2022-05-05 17:50 +0100
Re: On recursion and infinite recursion (reprise #3) olcott <polcott2@gmail.com> - 2022-05-05 13:58 -0500
Re: On recursion and infinite recursion (reprise #3) Ben <ben.usenet@bsb.me.uk> - 2022-05-05 20:56 +0100
Re: On recursion and infinite recursion (reprise #3) olcott <polcott2@gmail.com> - 2022-05-05 17:15 -0500
Re: On recursion and infinite recursion (reprise #3) Ben <ben.usenet@bsb.me.uk> - 2022-05-06 02:43 +0100
Re: On recursion and infinite recursion (reprise #3) olcott <polcott2@gmail.com> - 2022-05-05 20:59 -0500
Re: On recursion and infinite recursion (reprise #3) Ben <ben.usenet@bsb.me.uk> - 2022-05-06 04:08 +0100
Re: On recursion and infinite recursion (reprise #3) Ben <ben.usenet@bsb.me.uk> - 2022-05-05 20:51 +0100
Re: On recursion and infinite recursion (reprise #3) Mr Flibble <flibble@reddwarf.jmc> - 2022-05-05 20:52 +0100
Re: On recursion and infinite recursion (reprise #3) Ben <ben.usenet@bsb.me.uk> - 2022-05-05 21:15 +0100
Re: On recursion and infinite recursion (reprise #3) Mr Flibble <flibble@reddwarf.jmc> - 2022-05-05 21:16 +0100
Re: On recursion and infinite recursion (reprise #3) olcott <polcott2@gmail.com> - 2022-05-05 16:35 -0500
Re: On recursion and infinite recursion (reprise #3) olcott <polcott2@gmail.com> - 2022-05-05 16:37 -0500
Re: On recursion and infinite recursion (reprise #3) Ben <ben.usenet@bsb.me.uk> - 2022-05-06 02:38 +0100
Re: On recursion and infinite recursion (reprise #3) olcott <polcott2@gmail.com> - 2022-05-05 20:42 -0500
Re: On recursion and infinite recursion (reprise #3) Ben <ben.usenet@bsb.me.uk> - 2022-05-06 03:59 +0100
Re: On recursion and infinite recursion (reprise #3) Richard Damon <Richard@Damon-Family.org> - 2022-05-05 22:33 -0400
Re: On recursion and infinite recursion (reprise #3) Mr Flibble <flibble@reddwarf.jmc> - 2022-05-06 15:02 +0100
Re: On recursion and infinite recursion (reprise #3) Python <python@example.invalid> - 2022-05-06 16:18 +0200
Re: On recursion and infinite recursion (reprise #3) olcott <polcott2@gmail.com> - 2022-05-06 11:55 -0500
Re: On recursion and infinite recursion (reprise #3) Mikko <mikko.levanto@iki.fi> - 2022-05-07 12:52 +0300
Re: On recursion and infinite recursion (reprise #3) Mr Flibble <flibble@reddwarf.jmc> - 2022-05-07 13:42 +0100
Re: On recursion and infinite recursion (reprise #3) Mikko <mikko.levanto@iki.fi> - 2022-05-07 16:59 +0300
Re: On recursion and infinite recursion (reprise #3) Mr Flibble <flibble@reddwarf.jmc> - 2022-05-07 15:06 +0100
Re: On recursion and infinite recursion (reprise #3) Mikko <mikko.levanto@iki.fi> - 2022-05-07 17:16 +0300
Re: On recursion and infinite recursion (reprise #3) Mr Flibble <flibble@reddwarf.jmc> - 2022-05-07 15:20 +0100
Re: On recursion and infinite recursion (reprise #3) Mikko <mikko.levanto@iki.fi> - 2022-05-07 18:13 +0300
Re: On recursion and infinite recursion (reprise #3) Mr Flibble <flibble@reddwarf.jmc> - 2022-05-07 16:19 +0100
Re: On recursion and infinite recursion (reprise #3) olcott <polcott2@gmail.com> - 2022-05-07 11:03 -0500
Re: On recursion and infinite recursion (reprise #3) Ben <ben.usenet@bsb.me.uk> - 2022-05-07 23:41 +0100
Re: On recursion and infinite recursion (reprise #3) Mr Flibble <flibble@reddwarf.jmc> - 2022-05-07 23:43 +0100
Re: On recursion and infinite recursion (reprise #3) Richard Damon <Richard@Damon-Family.org> - 2022-05-07 19:59 -0400
Re: On recursion and infinite recursion (reprise #3) Mr Flibble <flibble@reddwarf.jmc> - 2022-05-08 01:01 +0100
Re: On recursion and infinite recursion (reprise #3) Richard Damon <Richard@Damon-Family.org> - 2022-05-07 20:18 -0400
Re: On recursion and infinite recursion (reprise #3) Mr Flibble <flibble@reddwarf.jmc> - 2022-05-08 01:55 +0100
Re: On recursion and infinite recursion (reprise #3) Mikko <mikko.levanto@iki.fi> - 2022-05-08 11:31 +0300
Re: On recursion and infinite recursion (reprise #3) Mr Flibble <flibble@reddwarf.jmc> - 2022-05-08 09:49 +0100
Re: On recursion and infinite recursion (reprise #3) Mikko <mikko.levanto@iki.fi> - 2022-05-08 13:00 +0300
Re: On recursion and infinite recursion (reprise #3) Mr Flibble <flibble@reddwarf.jmc> - 2022-05-08 12:57 +0100
Re: On recursion and infinite recursion (reprise #3) Richard Damon <Richard@Damon-Family.org> - 2022-05-08 07:45 -0400
Re: On recursion and infinite recursion (reprise #3) Mr Flibble <flibble@reddwarf.jmc> - 2022-05-08 13:02 +0100
Re: On recursion and infinite recursion (reprise #3) Richard Damon <Richard@Damon-Family.org> - 2022-05-08 08:31 -0400
Re: On recursion and infinite recursion (reprise #3) Mr Flibble <flibble@reddwarf.jmc> - 2022-05-08 13:39 +0100
Re: On recursion and infinite recursion (reprise #3) Richard Damon <Richard@Damon-Family.org> - 2022-05-08 14:10 -0400
Re: On recursion and infinite recursion (reprise #3) Mr Flibble <flibble@reddwarf.jmc> - 2022-05-08 20:06 +0100
Re: On recursion and infinite recursion (reprise #3) Richard Damon <Richard@Damon-Family.org> - 2022-05-08 15:39 -0400
Re: On recursion and infinite recursion (reprise #3) Mr Flibble <flibble@reddwarf.jmc> - 2022-05-08 21:14 +0100
Re: On recursion and infinite recursion (reprise #3) Richard Damon <Richard@Damon-Family.org> - 2022-05-08 17:40 -0400
Re: On recursion and infinite recursion (reprise #3) Mr Flibble <flibble@reddwarf.jmc> - 2022-05-08 23:04 +0100
Re: On recursion and infinite recursion (reprise #3) Ben <ben.usenet@bsb.me.uk> - 2022-05-09 00:26 +0100
Re: On recursion and infinite recursion (reprise #3) Richard Damon <Richard@Damon-Family.org> - 2022-05-08 19:40 -0400
Re: On recursion and infinite recursion (reprise #3) olcott <NoOne@NoWhere.com> - 2022-05-09 10:55 -0500
Re: On recursion and infinite recursion (reprise #3) Richard Damon <Richard@Damon-Family.org> - 2022-05-09 20:13 -0400
Re: On recursion and infinite recursion (reprise #3) olcott <NoOne@NoWhere.com> - 2022-05-09 10:51 -0500
Re: On recursion and infinite recursion (reprise #3) Mr Flibble <flibble@reddwarf.jmc> - 2022-05-09 18:31 +0100
Re: On recursion and infinite recursion (reprise #3) olcott <NoOne@NoWhere.com> - 2022-05-09 12:36 -0500
Re: On recursion and infinite recursion (reprise #3) Richard Damon <Richard@Damon-Family.org> - 2022-05-09 20:15 -0400
Re: On recursion and infinite recursion (reprise #3) Richard Damon <Richard@Damon-Family.org> - 2022-05-09 20:14 -0400
Re: On recursion and infinite recursion (reprise #3) olcott <NoOne@NoWhere.com> - 2022-05-09 10:49 -0500
Re: On recursion and infinite recursion (reprise #3) Mr Flibble <flibble@reddwarf.jmc> - 2022-05-09 18:31 +0100
Re: On recursion and infinite recursion (reprise #3) olcott <NoOne@NoWhere.com> - 2022-05-09 12:37 -0500
Re: On recursion and infinite recursion (reprise #3) olcott <NoOne@NoWhere.com> - 2022-05-09 10:47 -0500
Re: On recursion and infinite recursion (reprise #3) Mikko <mikko.levanto@iki.fi> - 2022-05-09 19:33 +0300
Re: On recursion and infinite recursion (reprise #3) olcott <NoOne@NoWhere.com> - 2022-05-09 11:36 -0500
Re: On recursion and infinite recursion (reprise #3) Richard Damon <Richard@Damon-Family.org> - 2022-05-09 20:17 -0400
Re: On recursion and infinite recursion (reprise #3) olcott <polcott2@gmail.com> - 2022-05-07 11:06 -0500
Re: On recursion and infinite recursion (reprise #3) Mikko <mikko.levanto@iki.fi> - 2022-05-06 16:39 +0300
csiph-web