Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| Subject | Re: On recursion and infinite recursion (reprise #3) |
|---|---|
| Newsgroups | comp.theory |
| References | (16 earlier) <20220508133909.00007b6b@reddwarf.jmc> <9ITdK.2055$wYy9.1130@fx11.iad> <20220508200637.0000491c@reddwarf.jmc> <U%UdK.8711$t72a.8053@fx10.iad> <20220508211421.000031a0@reddwarf.jmc> |
| From | Richard Damon <Richard@Damon-Family.org> |
| Message-ID | <ENWdK.7593$VwRc.5901@fx01.iad> (permalink) |
| Organization | Forte - www.forteinc.com |
| Date | 2022-05-08 17:40 -0400 |
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.
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