Re: On recursion and infinite recursion (reprise #3)

From	Mikko <mikko.levanto@iki.fi>
Newsgroups	comp.theory
Subject	Re: On recursion and infinite recursion (reprise #3)
Date	2022-05-08 11:31 +0300
Organization	-
Message-ID	<t57v4c$7do$1@dont-email.me> (permalink)
References	(6 earlier) <20220507150612.00003fab@reddwarf.jmc> <t55uvv$fpf$1@dont-email.me> <20220507152017.00000990@reddwarf.jmc> <t562a4$9ao$1@dont-email.me> <20220507161901.00002e54@reddwarf.jmc>

Show all headers | View raw

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.

Mikko

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