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 | (12 earlier) <20220508094913.00002e7c@reddwarf.jmc> <Q3OdK.15730$Bm21.3438@fx07.iad> <20220508130212.00007ab6@reddwarf.jmc> <iKOdK.8684$t72a.8070@fx10.iad> <20220508133909.00007b6b@reddwarf.jmc> |
| From | Richard Damon <Richard@Damon-Family.org> |
| Message-ID | <9ITdK.2055$wYy9.1130@fx11.iad> (permalink) |
| Organization | Forte - www.forteinc.com |
| Date | 2022-05-08 14:10 -0400 |
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.
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