Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.theory > #36377 > unrolled thread

Halting Problem proofs appear to be bogus!

Back to article view | Back to comp.theory

Contents

  Halting Problem proofs appear to be bogus! Mr Flibble <flibble@reddwarf.jmc> - 2021-07-16 14:24 +0100
    Re: Halting Problem proofs appear to be bogus! Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-16 14:34 +0100
      Re: Halting Problem proofs appear to be bogus! Mr Flibble <flibble@reddwarf.jmc> - 2021-07-16 14:39 +0100
        Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 09:36 -0500
          Re: Halting Problem proofs appear to be bogus! Mr Flibble <flibble@reddwarf.jmc> - 2021-07-16 15:39 +0100
            Re: Halting Problem proofs appear to be bogus! wij <wyniijj@gmail.com> - 2021-07-16 08:38 -0700
              Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 11:04 -0500
                Re: Halting Problem proofs appear to be bogus! wij <wyniijj@gmail.com> - 2021-07-16 09:25 -0700
                  Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 12:03 -0500
                    Re: Halting Problem proofs appear to be bogus! Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-16 19:50 +0100
          Re: Halting Problem proofs appear to be bogus! Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-16 15:46 +0100
        Re: Halting Problem proofs appear to be bogus! Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-16 15:40 +0100
          Re: Halting Problem proofs appear to be bogus! Mr Flibble <flibble@reddwarf.jmc> - 2021-07-16 15:42 +0100
            Re: Halting Problem proofs appear to be bogus! Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-17 01:06 +0100
              Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-17 10:52 -0500
        Re: Halting Problem proofs appear to be bogus! Andy Walker <anw@cuboid.co.uk> - 2021-07-16 16:12 +0100
          Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 10:52 -0500
            Re: Halting Problem proofs appear to be bogus! wij <wyniijj@gmail.com> - 2021-07-16 09:11 -0700
              Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 11:15 -0500
      Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 09:13 -0500
        Re: Halting Problem proofs appear to be bogus! wij <wyniijj@gmail.com> - 2021-07-16 08:32 -0700
        Re: Halting Problem proofs appear to be bogus! Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-17 01:03 +0100
          Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-17 10:46 -0500
            Re: Halting Problem proofs appear to be bogus! Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-18 02:32 +0100
              Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-19 10:10 -0500
                Re: Halting Problem proofs appear to be bogus! Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-20 01:35 +0100
                  Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-20 09:24 -0500
                    Re: Halting Problem proofs appear to be bogus! Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-21 01:28 +0100
                Re: Halting Problem proofs appear to be bogus! Richard Damon <Richard@Damon-Family.org> - 2021-07-19 20:48 -0700
    Re: Halting Problem proofs appear to be bogus! Peter <peterxpercival@hotmail.com> - 2021-07-16 15:27 +0100
      Re: Halting Problem proofs appear to be bogus! Mr Flibble <flibble@reddwarf.jmc> - 2021-07-16 15:36 +0100
        Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 10:02 -0500
          Re: Halting Problem proofs appear to be bogus! Peter <peterxpercival@hotmail.com> - 2021-07-16 22:09 +0100
        Re: Halting Problem proofs appear to be bogus! wij <wyniijj@gmail.com> - 2021-07-16 08:46 -0700
        Re: Halting Problem proofs appear to be bogus! Peter <peterxpercival@hotmail.com> - 2021-07-16 22:07 +0100
          Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 16:20 -0500
            Re: Halting Problem proofs appear to be bogus! Peter <peterxpercival@hotmail.com> - 2021-07-16 22:25 +0100
              Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 16:32 -0500
                Re: Halting Problem proofs appear to be bogus! Peter <peterxpercival@hotmail.com> - 2021-07-17 11:48 +0100
      Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 09:44 -0500
        Re: Halting Problem proofs appear to be bogus! Peter <peterxpercival@hotmail.com> - 2021-07-16 22:10 +0100
    Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 09:32 -0500

Page 1 of 3  [1] 2 3  Next page →

#36377 — Halting Problem proofs appear to be bogus!

Hi!

All extant halting problem proofs appear to be predicated on a
misunderstanding of the following contradiction:

	Suppose T[R] is a Boolean function taking a routine
	(or program) R with no formal or free variables as its
	argument and that for all R, T[R] — True if R terminates
	if run and that T[R] = False if R does not terminate. Consider
	the routine P defined as follows 

		rec routine P
			§L :if T[P] goto L
		Return §

	If T[P] = True the routine P will loop, and it will
	only terminate if T[P] = False. In each case T[P] has
	exactly the wrong value, and this contradiction shows
	that the function T cannot exist.

	[Strachey 1965]

T is indeed unable to decide P but for the wrong reason: T[P] is
recursive which means T can never decide if P halts because T never
halts itself; this mistake appears to have been missed by Strachey as
the §L <- L loop can't ever loop due to the recursion.

HOWEVER

Even if we ignore the error of recursion it does NOT follow that for
T[Q], T cannot decide if Q halts where Q is a program that does not
reference T.

[Strachey 1965] shows us that a decider cannot be part of or called by
that which is being decided (a pathological program) and given this it
seems to be unproven that a decider for programs that don't exhibit
this pathology cannot exist.

/Flibble

[toc] | [next] | [standalone]

#36378

Mr Flibble <flibble@reddwarf.jmc> writes:

> All extant halting problem proofs appear to be predicated on a
> misunderstanding of the following contradiction:

I don't think you've read any actual proofs, let along all of them.  Why
you would even say such a thing?

> 	Suppose T[R] is a Boolean function taking a routine
> 	(or program) R with no formal or free variables as its
> 	argument and that for all R, T[R] — True if R terminates
> 	if run and that T[R] = False if R does not terminate. Consider
> 	the routine P defined as follows 
>
> 		rec routine P
> 			§L :if T[P] goto L
> 		Return §
>
> 	If T[P] = True the routine P will loop, and it will
> 	only terminate if T[P] = False. In each case T[P] has
> 	exactly the wrong value, and this contradiction shows
> 	that the function T cannot exist.
>
> 	[Strachey 1965]
>
> T is indeed unable to decide P but for the wrong reason: T[P] is
> recursive

T[P] is not recursive.  Maybe you don't understand what the CPL means?

Further, this argument must fail for any of the actual proofs that are
based on Turing machine because TMs have not functions, not calls and no
recursion.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#36379

On Fri, 16 Jul 2021 14:34:54 +0100
Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:

> Mr Flibble <flibble@reddwarf.jmc> writes:
> 
> > All extant halting problem proofs appear to be predicated on a
> > misunderstanding of the following contradiction:
> 
> I don't think you've read any actual proofs, let along all of them.
> Why you would even say such a thing?
> 
> > 	Suppose T[R] is a Boolean function taking a routine
> > 	(or program) R with no formal or free variables as its
> > 	argument and that for all R, T[R] — True if R terminates
> > 	if run and that T[R] = False if R does not terminate.
> > Consider the routine P defined as follows 
> >
> > 		rec routine P
> > 			§L :if T[P] goto L
> > 		Return §
> >
> > 	If T[P] = True the routine P will loop, and it will
> > 	only terminate if T[P] = False. In each case T[P] has
> > 	exactly the wrong value, and this contradiction shows
> > 	that the function T cannot exist.
> >
> > 	[Strachey 1965]
> >
> > T is indeed unable to decide P but for the wrong reason: T[P] is
> > recursive
> 
> T[P] is not recursive.  Maybe you don't understand what the CPL means?

Of course it is recursive, such is obvious even to the casual reader
who is unfamiliar with the CPL language (a clue: read the paragraph
before the definition of P again).

> 
> Further, this argument must fail for any of the actual proofs that are
> based on Turing machine because TMs have not functions, not calls and
> no recursion.

Depends on whether or not there is an isomorphic equivalence.

/Flibble 

[toc] | [prev] | [next] | [standalone]

#36385

On 7/16/2021 8:39 AM, Mr Flibble wrote:
> On Fri, 16 Jul 2021 14:34:54 +0100
> Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
> 
>> Mr Flibble <flibble@reddwarf.jmc> writes:
>>
>>> All extant halting problem proofs appear to be predicated on a
>>> misunderstanding of the following contradiction:
>>
>> I don't think you've read any actual proofs, let along all of them.
>> Why you would even say such a thing?
>>
>>> 	Suppose T[R] is a Boolean function taking a routine
>>> 	(or program) R with no formal or free variables as its
>>> 	argument and that for all R, T[R] — True if R terminates
>>> 	if run and that T[R] = False if R does not terminate.
>>> Consider the routine P defined as follows
>>>
>>> 		rec routine P
>>> 			§L :if T[P] goto L
>>> 		Return §
>>>
>>> 	If T[P] = True the routine P will loop, and it will
>>> 	only terminate if T[P] = False. In each case T[P] has
>>> 	exactly the wrong value, and this contradiction shows
>>> 	that the function T cannot exist.
>>>
>>> 	[Strachey 1965]
>>>
>>> T is indeed unable to decide P but for the wrong reason: T[P] is
>>> recursive
>>
>> T[P] is not recursive.  Maybe you don't understand what the CPL means?
> 
> Of course it is recursive, such is obvious even to the casual reader
> who is unfamiliar with the CPL language (a clue: read the paragraph
> before the definition of P again).
> 

"Recursive" has a very different meaning in computer science than it 
does in software engineering.

https://en.wikipedia.org/wiki/Recursive_language

>>
>> Further, this argument must fail for any of the actual proofs that are
>> based on Turing machine because TMs have not functions, not calls and
>> no recursion.
> 
> Depends on whether or not there is an isomorphic equivalence.
> 
> /Flibble
> 
> 


-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]

#36387

On Fri, 16 Jul 2021 09:36:15 -0500
olcott <NoOne@NoWhere.com> wrote:

> On 7/16/2021 8:39 AM, Mr Flibble wrote:
> > On Fri, 16 Jul 2021 14:34:54 +0100
> > Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
> >   
> >> Mr Flibble <flibble@reddwarf.jmc> writes:
> >>  
> >>> All extant halting problem proofs appear to be predicated on a
> >>> misunderstanding of the following contradiction:  
> >>
> >> I don't think you've read any actual proofs, let along all of them.
> >> Why you would even say such a thing?
> >>  
> >>> 	Suppose T[R] is a Boolean function taking a routine
> >>> 	(or program) R with no formal or free variables as its
> >>> 	argument and that for all R, T[R] — True if R terminates
> >>> 	if run and that T[R] = False if R does not terminate.
> >>> Consider the routine P defined as follows
> >>>
> >>> 		rec routine P
> >>> 			§L :if T[P] goto L
> >>> 		Return §
> >>>
> >>> 	If T[P] = True the routine P will loop, and it will
> >>> 	only terminate if T[P] = False. In each case T[P] has
> >>> 	exactly the wrong value, and this contradiction shows
> >>> 	that the function T cannot exist.
> >>>
> >>> 	[Strachey 1965]
> >>>
> >>> T is indeed unable to decide P but for the wrong reason: T[P] is
> >>> recursive  
> >>
> >> T[P] is not recursive.  Maybe you don't understand what the CPL
> >> means?  
> > 
> > Of course it is recursive, such is obvious even to the casual reader
> > who is unfamiliar with the CPL language (a clue: read the paragraph
> > before the definition of P again).
> >   
> 
> "Recursive" has a very different meaning in computer science than it 
> does in software engineering.

By "recursion" I am referring to a function that calls itself either
directly or indirectly; in the case of [Strachey 1965] the recursion is
indirect:

T[P] -> P -> T[P] -> P -> T[P] ... ...

/Flibble

[toc] | [prev] | [next] | [standalone]

#36397

On Friday, 16 July 2021 at 22:39:59 UTC+8, Mr Flibble wrote:
> On Fri, 16 Jul 2021 09:36:15 -0500 
> olcott <No...@NoWhere.com> wrote: 
> 
> > On 7/16/2021 8:39 AM, Mr Flibble wrote: 
> > > On Fri, 16 Jul 2021 14:34:54 +0100 
> > > Ben Bacarisse <ben.u...@bsb.me.uk> wrote: 
> > > 
> > >> Mr Flibble <fli...@reddwarf.jmc> writes: 
> > >> 
> > >>> All extant halting problem proofs appear to be predicated on a 
> > >>> misunderstanding of the following contradiction: 
> > >> 
> > >> I don't think you've read any actual proofs, let along all of them. 
> > >> Why you would even say such a thing? 
> > >> 
> > >>> Suppose T[R] is a Boolean function taking a routine 
> > >>> (or program) R with no formal or free variables as its 
> > >>> argument and that for all R, T[R] — True if R terminates 
> > >>> if run and that T[R] = False if R does not terminate. 
> > >>> Consider the routine P defined as follows 
> > >>> 
> > >>> rec routine P 
> > >>> §L :if T[P] goto L 
> > >>> Return § 
> > >>> 
> > >>> If T[P] = True the routine P will loop, and it will 
> > >>> only terminate if T[P] = False. In each case T[P] has 
> > >>> exactly the wrong value, and this contradiction shows 
> > >>> that the function T cannot exist. 
> > >>> 
> > >>> [Strachey 1965] 
> > >>> 
> > >>> T is indeed unable to decide P but for the wrong reason: T[P] is 
> > >>> recursive 
> > >> 
> > >> T[P] is not recursive. Maybe you don't understand what the CPL 
> > >> means? 
> > > 
> > > Of course it is recursive, such is obvious even to the casual reader 
> > > who is unfamiliar with the CPL language (a clue: read the paragraph 
> > > before the definition of P again). 
> > > 
> > 
> > "Recursive" has a very different meaning in computer science than it 
> > does in software engineering.
> By "recursion" I am referring to a function that calls itself either 
> directly or indirectly; in the case of [Strachey 1965] the recursion is 
> indirect: 
> 
> T[P] -> P -> T[P] -> P -> T[P] ... ... 
> 
> /Flibble

// program P.c
//-------------------
void P();

inline bool H(Func p) {
 // Rewrite H here.
 // The rewrite can be in very different but functionally equivalent ways (isomorphic).
}

void P() {
 if(H(P)) {
   for(;;) {};  // If H(P)==true, P is in infinite loop.
 }
};

If there is high-level "recursive call" it is made within H itself (may be your T), nothing to
do with P. And this is why "undecidable" is called, H will not halt.

[toc] | [prev] | [next] | [standalone]

#36401

On 7/16/2021 10:38 AM, wij wrote:
> On Friday, 16 July 2021 at 22:39:59 UTC+8, Mr Flibble wrote:
>> On Fri, 16 Jul 2021 09:36:15 -0500
>> olcott <No...@NoWhere.com> wrote:
>>
>>> On 7/16/2021 8:39 AM, Mr Flibble wrote:
>>>> On Fri, 16 Jul 2021 14:34:54 +0100
>>>> Ben Bacarisse <ben.u...@bsb.me.uk> wrote:
>>>>
>>>>> Mr Flibble <fli...@reddwarf.jmc> writes:
>>>>>
>>>>>> All extant halting problem proofs appear to be predicated on a
>>>>>> misunderstanding of the following contradiction:
>>>>>
>>>>> I don't think you've read any actual proofs, let along all of them.
>>>>> Why you would even say such a thing?
>>>>>
>>>>>> Suppose T[R] is a Boolean function taking a routine
>>>>>> (or program) R with no formal or free variables as its
>>>>>> argument and that for all R, T[R] — True if R terminates
>>>>>> if run and that T[R] = False if R does not terminate.
>>>>>> Consider the routine P defined as follows
>>>>>>
>>>>>> rec routine P
>>>>>> §L :if T[P] goto L
>>>>>> Return §
>>>>>>
>>>>>> If T[P] = True the routine P will loop, and it will
>>>>>> only terminate if T[P] = False. In each case T[P] has
>>>>>> exactly the wrong value, and this contradiction shows
>>>>>> that the function T cannot exist.
>>>>>>
>>>>>> [Strachey 1965]
>>>>>>
>>>>>> T is indeed unable to decide P but for the wrong reason: T[P] is
>>>>>> recursive
>>>>>
>>>>> T[P] is not recursive. Maybe you don't understand what the CPL
>>>>> means?
>>>>
>>>> Of course it is recursive, such is obvious even to the casual reader
>>>> who is unfamiliar with the CPL language (a clue: read the paragraph
>>>> before the definition of P again).
>>>>
>>>
>>> "Recursive" has a very different meaning in computer science than it
>>> does in software engineering.
>> By "recursion" I am referring to a function that calls itself either
>> directly or indirectly; in the case of [Strachey 1965] the recursion is
>> indirect:
>>
>> T[P] -> P -> T[P] -> P -> T[P] ... ...
>>
>> /Flibble
> 
> // program P.c
> //-------------------
> void P();
> 
> inline bool H(Func p) {
>   // Rewrite H here.
>   // The rewrite can be in very different but functionally equivalent ways (isomorphic).
> }
> 
> void P() {
>   if(H(P)) {
>     for(;;) {};  // If H(P)==true, P is in infinite loop.
>   }
> };
> 
> If there is high-level "recursive call" it is made within H itself (may be your T), nothing to
> do with P. And this is why "undecidable" is called, H will not halt.
> 

#include <stdint.h>
#define u32 uint32_t

void P()
{
   if (H((u32)P)))
     HERE: goto HERE;
}

Since there is no such actual thing as Func p that is currently fully 
elaborated yet there is such as thing as the machine address of the 
machine language code of the C function P mine can be fully understood 
whereas your leaves out to many details.

In my system H is written in C returns u32 and is based on a full x86 
emulator:

https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation


-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]

#36405

On Saturday, 17 July 2021 at 00:04:56 UTC+8, olcott wrote:
> On 7/16/2021 10:38 AM, wij wrote: 
> > On Friday, 16 July 2021 at 22:39:59 UTC+8, Mr Flibble wrote: 
> >> On Fri, 16 Jul 2021 09:36:15 -0500 
> >> olcott <No...@NoWhere.com> wrote: 
> >> 
> >>> On 7/16/2021 8:39 AM, Mr Flibble wrote: 
> >>>> On Fri, 16 Jul 2021 14:34:54 +0100 
> >>>> Ben Bacarisse <ben.u...@bsb.me.uk> wrote: 
> >>>> 
> >>>>> Mr Flibble <fli...@reddwarf.jmc> writes: 
> >>>>> 
> >>>>>> All extant halting problem proofs appear to be predicated on a 
> >>>>>> misunderstanding of the following contradiction: 
> >>>>> 
> >>>>> I don't think you've read any actual proofs, let along all of them. 
> >>>>> Why you would even say such a thing? 
> >>>>> 
> >>>>>> Suppose T[R] is a Boolean function taking a routine 
> >>>>>> (or program) R with no formal or free variables as its 
> >>>>>> argument and that for all R, T[R] — True if R terminates 
> >>>>>> if run and that T[R] = False if R does not terminate. 
> >>>>>> Consider the routine P defined as follows 
> >>>>>> 
> >>>>>> rec routine P 
> >>>>>> §L :if T[P] goto L 
> >>>>>> Return § 
> >>>>>> 
> >>>>>> If T[P] = True the routine P will loop, and it will 
> >>>>>> only terminate if T[P] = False. In each case T[P] has 
> >>>>>> exactly the wrong value, and this contradiction shows 
> >>>>>> that the function T cannot exist. 
> >>>>>> 
> >>>>>> [Strachey 1965] 
> >>>>>> 
> >>>>>> T is indeed unable to decide P but for the wrong reason: T[P] is 
> >>>>>> recursive 
> >>>>> 
> >>>>> T[P] is not recursive. Maybe you don't understand what the CPL 
> >>>>> means? 
> >>>> 
> >>>> Of course it is recursive, such is obvious even to the casual reader 
> >>>> who is unfamiliar with the CPL language (a clue: read the paragraph 
> >>>> before the definition of P again). 
> >>>> 
> >>> 
> >>> "Recursive" has a very different meaning in computer science than it 
> >>> does in software engineering. 
> >> By "recursion" I am referring to a function that calls itself either 
> >> directly or indirectly; in the case of [Strachey 1965] the recursion is 
> >> indirect: 
> >> 
> >> T[P] -> P -> T[P] -> P -> T[P] ... ... 
> >> 
> >> /Flibble 
> > 
> > // program P.c 
> > //------------------- 
> > void P(); 
> > 
> > inline bool H(Func p) { 
> > // Rewrite H here. 
> > // The rewrite can be in very different but functionally equivalent ways (isomorphic). 
> > } 
> > 
> > void P() { 
> > if(H(P)) { 
> > for(;;) {}; // If H(P)==true, P is in infinite loop. 
> > } 
> > }; 
> > 
> > If there is high-level "recursive call" it is made within H itself (may be your T), nothing to 
> > do with P. And this is why "undecidable" is called, H will not halt. 
> >
> #include <stdint.h> 
> #define u32 uint32_t 
> 
> void P() 
> { 
> if (H((u32)P))) 
> HERE: goto HERE; 
> } 
> 
> Since there is no such actual thing as Func p that is currently fully 
> elaborated yet there is such as thing as the machine address of the 
> machine language code of the C function P mine can be fully understood 
> whereas your leaves out to many details. 
> 
> In my system H is written in C returns u32 and is based on a full x86 
> emulator: 
 
I can not follow your sentence well. In this case, Func is a function pointer:
typedef void (*Func)();

> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation
> -- 
> Copyright 2021 Pete Olcott 
> 
> "Great spirits have always encountered violent opposition from mediocre 
> minds." Einstein

[toc] | [prev] | [next] | [standalone]

#36407

On 7/16/2021 11:25 AM, wij wrote:
> On Saturday, 17 July 2021 at 00:04:56 UTC+8, olcott wrote:
>> On 7/16/2021 10:38 AM, wij wrote:
>>> On Friday, 16 July 2021 at 22:39:59 UTC+8, Mr Flibble wrote:
>>>> On Fri, 16 Jul 2021 09:36:15 -0500
>>>> olcott <No...@NoWhere.com> wrote:
>>>>
>>>>> On 7/16/2021 8:39 AM, Mr Flibble wrote:
>>>>>> On Fri, 16 Jul 2021 14:34:54 +0100
>>>>>> Ben Bacarisse <ben.u...@bsb.me.uk> wrote:
>>>>>>
>>>>>>> Mr Flibble <fli...@reddwarf.jmc> writes:
>>>>>>>
>>>>>>>> All extant halting problem proofs appear to be predicated on a
>>>>>>>> misunderstanding of the following contradiction:
>>>>>>>
>>>>>>> I don't think you've read any actual proofs, let along all of them.
>>>>>>> Why you would even say such a thing?
>>>>>>>
>>>>>>>> Suppose T[R] is a Boolean function taking a routine
>>>>>>>> (or program) R with no formal or free variables as its
>>>>>>>> argument and that for all R, T[R] — True if R terminates
>>>>>>>> if run and that T[R] = False if R does not terminate.
>>>>>>>> Consider the routine P defined as follows
>>>>>>>>
>>>>>>>> rec routine P
>>>>>>>> §L :if T[P] goto L
>>>>>>>> Return §
>>>>>>>>
>>>>>>>> If T[P] = True the routine P will loop, and it will
>>>>>>>> only terminate if T[P] = False. In each case T[P] has
>>>>>>>> exactly the wrong value, and this contradiction shows
>>>>>>>> that the function T cannot exist.
>>>>>>>>
>>>>>>>> [Strachey 1965]
>>>>>>>>
>>>>>>>> T is indeed unable to decide P but for the wrong reason: T[P] is
>>>>>>>> recursive
>>>>>>>
>>>>>>> T[P] is not recursive. Maybe you don't understand what the CPL
>>>>>>> means?
>>>>>>
>>>>>> Of course it is recursive, such is obvious even to the casual reader
>>>>>> who is unfamiliar with the CPL language (a clue: read the paragraph
>>>>>> before the definition of P again).
>>>>>>
>>>>>
>>>>> "Recursive" has a very different meaning in computer science than it
>>>>> does in software engineering.
>>>> By "recursion" I am referring to a function that calls itself either
>>>> directly or indirectly; in the case of [Strachey 1965] the recursion is
>>>> indirect:
>>>>
>>>> T[P] -> P -> T[P] -> P -> T[P] ... ...
>>>>
>>>> /Flibble
>>>
>>> // program P.c
>>> //-------------------
>>> void P();
>>>
>>> inline bool H(Func p) {
>>> // Rewrite H here.
>>> // The rewrite can be in very different but functionally equivalent ways (isomorphic).
>>> }
>>>
>>> void P() {
>>> if(H(P)) {
>>> for(;;) {}; // If H(P)==true, P is in infinite loop.
>>> }
>>> };
>>>
>>> If there is high-level "recursive call" it is made within H itself (may be your T), nothing to
>>> do with P. And this is why "undecidable" is called, H will not halt.
>>>
>> #include <stdint.h>
>> #define u32 uint32_t
>>
>> void P()
>> {
>> if (H((u32)P)))
>> HERE: goto HERE;
>> }
>>
>> Since there is no such actual thing as Func p that is currently fully
>> elaborated yet there is such as thing as the machine address of the
>> machine language code of the C function P mine can be fully understood
>> whereas your leaves out to many details.
>>
>> In my system H is written in C returns u32 and is based on a full x86
>> emulator:
>   
> I can not follow your sentence well. In this case, Func is a function pointer:
> typedef void (*Func)();
> 

A function pointer is also the machine address of the function.

>> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation
>> -- 
>> Copyright 2021 Pete Olcott
>>
>> "Great spirits have always encountered violent opposition from mediocre
>> minds." Einstein


-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]

#36423

olcott <NoOne@NoWhere.com> writes:

>> I can not follow your sentence well. In this case, Func is a
>> function pointer: typedef void (*Func)();
>
> A function pointer is also the machine address of the function.

Not necessarily.  I worked on a C implementation for an architecture in
which functions where just numbered.  It was very handy when debugging.
You got to know, after a while, that a call to function number 13 was
printf (or whatever).

Of course the CPU had a way to get from the number to the code, but
there was no "machine address" for that code.

I suppose you could call the number the "machine address of the
function", but it was not a address in any useful sense of the word.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#36392

olcott <NoOne@NoWhere.com> writes:

> On 7/16/2021 8:39 AM, Mr Flibble wrote:
>> On Fri, 16 Jul 2021 14:34:54 +0100
>> Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
>> 
>>> Mr Flibble <flibble@reddwarf.jmc> writes:
>>>
>>>> All extant halting problem proofs appear to be predicated on a
>>>> misunderstanding of the following contradiction:
>>>
>>> I don't think you've read any actual proofs, let along all of them.
>>> Why you would even say such a thing?
>>>
>>>> 	Suppose T[R] is a Boolean function taking a routine
>>>> 	(or program) R with no formal or free variables as its
>>>> 	argument and that for all R, T[R] — True if R terminates
>>>> 	if run and that T[R] = False if R does not terminate.
>>>> Consider the routine P defined as follows
>>>>
>>>> 		rec routine P
>>>> 			§L :if T[P] goto L
>>>> 		Return §
>>>>
>>>> 	If T[P] = True the routine P will loop, and it will
>>>> 	only terminate if T[P] = False. In each case T[P] has
>>>> 	exactly the wrong value, and this contradiction shows
>>>> 	that the function T cannot exist.
>>>>
>>>> 	[Strachey 1965]
>>>>
>>>> T is indeed unable to decide P but for the wrong reason: T[P] is
>>>> recursive
>>>
>>> T[P] is not recursive.  Maybe you don't understand what the CPL means?
>>
>> Of course it is recursive, such is obvious even to the casual reader
>> who is unfamiliar with the CPL language (a clue: read the paragraph
>> before the definition of P again).
>
> "Recursive" has a very different meaning in computer science than it
> does in software engineering.
>
> https://en.wikipedia.org/wiki/Recursive_language

I wonder why you think that's helpful.  Neither Flibble nor I was using
it in that sense.  That sense is simply not applicable to either of our
posts.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#36388

Mr Flibble <flibble@reddwarf.jmc> writes:

> On Fri, 16 Jul 2021 14:34:54 +0100
> Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
>
>> Mr Flibble <flibble@reddwarf.jmc> writes:
>> 
>> > All extant halting problem proofs appear to be predicated on a
>> > misunderstanding of the following contradiction:
>> 
>> I don't think you've read any actual proofs, let along all of them.
>> Why you would even say such a thing?
>> 
>> > 	Suppose T[R] is a Boolean function taking a routine
>> > 	(or program) R with no formal or free variables as its
>> > 	argument and that for all R, T[R] — True if R terminates
>> > 	if run and that T[R] = False if R does not terminate.
>> > Consider the routine P defined as follows 
>> >
>> > 		rec routine P
>> > 			§L :if T[P] goto L
>> > 		Return §
>> >
>> > 	If T[P] = True the routine P will loop, and it will
>> > 	only terminate if T[P] = False. In each case T[P] has
>> > 	exactly the wrong value, and this contradiction shows
>> > 	that the function T cannot exist.
>> >
>> > 	[Strachey 1965]
>> >
>> > T is indeed unable to decide P but for the wrong reason: T[P] is
>> > recursive
>> 
>> T[P] is not recursive.  Maybe you don't understand what the CPL means?
>
> Of course it is recursive, such is obvious even to the casual reader
> who is unfamiliar with the CPL language (a clue: read the paragraph
> before the definition of P again).

No.  T[P] /might/ be recursive, but then again it might not be.  Any
argument based on the blank assumption that T[P] is recursive is
flawed.  T must be permitted to make it decision based on the widest
possible use of it's argument or the sketch is pointlessly restrictive.

>> Further, this argument must fail for any of the actual proofs that are
>> based on Turing machine because TMs have not functions, not calls and
>> no recursion.
>
> Depends on whether or not there is an isomorphic equivalence.

Two things being equivalent does not mean you can use the wrong terms.
You can't count the states of CPL program, and you can't pass an
argument to a TM function.  Words matter.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#36389

On Fri, 16 Jul 2021 15:40:27 +0100
Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:

> Mr Flibble <flibble@reddwarf.jmc> writes:
> 
> > On Fri, 16 Jul 2021 14:34:54 +0100
> > Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
> >  
> >> Mr Flibble <flibble@reddwarf.jmc> writes:
> >>   
> >> > All extant halting problem proofs appear to be predicated on a
> >> > misunderstanding of the following contradiction:  
> >> 
> >> I don't think you've read any actual proofs, let along all of them.
> >> Why you would even say such a thing?
> >>   
> >> > 	Suppose T[R] is a Boolean function taking a routine
> >> > 	(or program) R with no formal or free variables as its
> >> > 	argument and that for all R, T[R] — True if R terminates
> >> > 	if run and that T[R] = False if R does not terminate.
> >> > Consider the routine P defined as follows 
> >> >
> >> > 		rec routine P
> >> > 			§L :if T[P] goto L
> >> > 		Return §
> >> >
> >> > 	If T[P] = True the routine P will loop, and it will
> >> > 	only terminate if T[P] = False. In each case T[P] has
> >> > 	exactly the wrong value, and this contradiction shows
> >> > 	that the function T cannot exist.
> >> >
> >> > 	[Strachey 1965]
> >> >
> >> > T is indeed unable to decide P but for the wrong reason: T[P] is
> >> > recursive  
> >> 
> >> T[P] is not recursive.  Maybe you don't understand what the CPL
> >> means?  
> >
> > Of course it is recursive, such is obvious even to the casual reader
> > who is unfamiliar with the CPL language (a clue: read the paragraph
> > before the definition of P again).  
> 
> No.  T[P] /might/ be recursive, but then again it might not be.  Any
> argument based on the blank assumption that T[P] is recursive is
> flawed.  T must be permitted to make it decision based on the widest
> possible use of it's argument or the sketch is pointlessly
> restrictive.

No. It is recursive.

[snip]

/Flibble

[toc] | [prev] | [next] | [standalone]

#36482

Mr Flibble <flibble@reddwarf.jmc> writes:

> On Fri, 16 Jul 2021 15:40:27 +0100
> Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
>
>> Mr Flibble <flibble@reddwarf.jmc> writes:
>> 
>> > On Fri, 16 Jul 2021 14:34:54 +0100
>> > Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
>> >  
>> >> Mr Flibble <flibble@reddwarf.jmc> writes:
>> >>   
>> >> > All extant halting problem proofs appear to be predicated on a
>> >> > misunderstanding of the following contradiction:  
>> >> 
>> >> I don't think you've read any actual proofs, let along all of them.
>> >> Why you would even say such a thing?
>> >>   
>> >> > 	Suppose T[R] is a Boolean function taking a routine
>> >> > 	(or program) R with no formal or free variables as its
>> >> > 	argument and that for all R, T[R] — True if R terminates
>> >> > 	if run and that T[R] = False if R does not terminate.
>> >> > Consider the routine P defined as follows 
>> >> >
>> >> > 		rec routine P
>> >> > 			§L :if T[P] goto L
>> >> > 		Return §
>> >> >
>> >> > 	If T[P] = True the routine P will loop, and it will
>> >> > 	only terminate if T[P] = False. In each case T[P] has
>> >> > 	exactly the wrong value, and this contradiction shows
>> >> > 	that the function T cannot exist.
>> >> >
>> >> > 	[Strachey 1965]
>> >> >
>> >> > T is indeed unable to decide P but for the wrong reason: T[P] is
>> >> > recursive  
>> >> 
>> >> T[P] is not recursive.  Maybe you don't understand what the CPL
>> >> means?  
>> >
>> > Of course it is recursive, such is obvious even to the casual reader
>> > who is unfamiliar with the CPL language (a clue: read the paragraph
>> > before the definition of P again).  
>> 
>> No.  T[P] /might/ be recursive, but then again it might not be.  Any
>> argument based on the blank assumption that T[P] is recursive is
>> flawed.  T must be permitted to make it decision based on the widest
>> possible use of it's argument or the sketch is pointlessly
>> restrictive.
>
> No. It is recursive.

I suppose if anyone else is reading this, they will just have to pick a
side!

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#36544

On 7/16/2021 7:06 PM, Ben Bacarisse wrote:
> Mr Flibble <flibble@reddwarf.jmc> writes:
> 
>> On Fri, 16 Jul 2021 15:40:27 +0100
>> Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
>>
>>> Mr Flibble <flibble@reddwarf.jmc> writes:
>>>
>>>> On Fri, 16 Jul 2021 14:34:54 +0100
>>>> Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
>>>>   
>>>>> Mr Flibble <flibble@reddwarf.jmc> writes:
>>>>>    
>>>>>> All extant halting problem proofs appear to be predicated on a
>>>>>> misunderstanding of the following contradiction:
>>>>>
>>>>> I don't think you've read any actual proofs, let along all of them.
>>>>> Why you would even say such a thing?
>>>>>    
>>>>>> 	Suppose T[R] is a Boolean function taking a routine
>>>>>> 	(or program) R with no formal or free variables as its
>>>>>> 	argument and that for all R, T[R] — True if R terminates
>>>>>> 	if run and that T[R] = False if R does not terminate.
>>>>>> Consider the routine P defined as follows
>>>>>>
>>>>>> 		rec routine P
>>>>>> 			§L :if T[P] goto L
>>>>>> 		Return §
>>>>>>
>>>>>> 	If T[P] = True the routine P will loop, and it will
>>>>>> 	only terminate if T[P] = False. In each case T[P] has
>>>>>> 	exactly the wrong value, and this contradiction shows
>>>>>> 	that the function T cannot exist.
>>>>>>
>>>>>> 	[Strachey 1965]
>>>>>>
>>>>>> T is indeed unable to decide P but for the wrong reason: T[P] is
>>>>>> recursive
>>>>>
>>>>> T[P] is not recursive.  Maybe you don't understand what the CPL
>>>>> means?
>>>>
>>>> Of course it is recursive, such is obvious even to the casual reader
>>>> who is unfamiliar with the CPL language (a clue: read the paragraph
>>>> before the definition of P again).
>>>
>>> No.  T[P] /might/ be recursive, but then again it might not be.  Any
>>> argument based on the blank assumption that T[P] is recursive is
>>> flawed.  T must be permitted to make it decision based on the widest
>>> possible use of it's argument or the sketch is pointlessly
>>> restrictive.
>>
>> No. It is recursive.
> 
> I suppose if anyone else is reading this, they will just have to pick a
> side!
> 

Pathological self-reference(Olcott 2004) is an error.
When an input is defined to do that opposite of whatever its 
corresponding halt decider decides this forms the exactly same 
self-contradictory error of the liar paradox.

On Sunday, September 5, 2004 at 11:21:57 AM UTC-5, Peter Olcott wrote:
The Liar Paradox can be shown to be nothing more than
a incorrectly formed statement because of its pathological
self-reference. The Halting Problem can only exist because
of this same sort of pathological self-reference.

Halt deciders can be defined that correctly decide the halt status of 
these otherwise pathological inputs.

https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation

-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]

#36395

On 16/07/2021 14:39, Mr Flibble wrote:
> On Fri, 16 Jul 2021 14:34:54 +0100
> Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
>> Mr Flibble <flibble@reddwarf.jmc> quotes:
>>> 	Suppose T[R] is a Boolean function taking a routine
>>> 	(or program) R with no formal or free variables as its
>>> 	argument [...].
>>> Consider the routine P defined as follows
>>> 		rec routine P
>>> 			§L :if T[P] goto L
>>> 		Return §
[...]
>>> T is indeed unable to decide P but for the wrong reason: T[P] is
>>> recursive

	I suppose one should not point out that "P", as defined, has
"T" as a free variable, so is not a valid parameter to "T"?  But that's
a quibble, as "P" could be re-written to have the code for "H" included.

>> T[P] is not recursive.  Maybe you don't understand what the CPL means?
> Of course it is recursive, such is obvious even to the casual reader
> who is unfamiliar with the CPL language (a clue: read the paragraph
> before the definition of P again).

	"T[P]" is recursive only if "T" calls "P".  That is a pretty
daft thing to do.  "Does this program ever halt?" "Dunno, let's find
out by running it."  If that doesn't seem stupid, imagine replacing
"halt" by "kill the patient" or "blow up this nuclear power station".
So a well-written "T" will not call its parameter.  This makes the
whole argument as currently being debated moot;  if you don't call a
routine, then pretty much all you can do with it is assign it or pass
it as a parameter/operand, neither of which gets us any nearer to
deciding whether it halts [or kills people].

	But in this form, it also has nothing to do with the Halting
Problem, which would not be about some "T" that /calls/ "P" but about
one that /inspects/ "P".  So the only sensible interpretation of what
Strachey wrote is that the parameter to "T" is the /source/ of some
program or routine "P".  In most languages, that source would be of
"string" or perhaps "file" type or similar.  "P" would then be the
string quoted above [preferably with also the string corresponding
to the source of "T"].  Once this simple interpretation is made, the
fundamental Strachey/Minsky/Sipser/Linz argument works perfectly well
with no question of recursion [infinite, "pathological" or otherwise]
unless "T" chooses it.

	That is why I have several times suggested, though with little
success, that participants in this debate should be very clear about
whether they are talking about "source" or "executable".  Simply
calling things "H", "P", "T", "H_hat", ... does not convey this
[necessary] information, and leads to Olcottian confusions.  Perhaps
some contributors prefer to obscure the argument.

-- 
Andy Walker, Nottingham.
    Andy's music pages: www.cuboid.me.uk/andy/Music
    Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Peerson

[toc] | [prev] | [next] | [standalone]

#36400

On 7/16/2021 10:12 AM, Andy Walker wrote:
> On 16/07/2021 14:39, Mr Flibble wrote:
>> On Fri, 16 Jul 2021 14:34:54 +0100
>> Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
>>> Mr Flibble <flibble@reddwarf.jmc> quotes:
>>>>     Suppose T[R] is a Boolean function taking a routine
>>>>     (or program) R with no formal or free variables as its
>>>>     argument [...].
>>>> Consider the routine P defined as follows

>>>>         rec routine P
>>>>             §L :if T[P] goto L
>>>>         Return §
> [...]
>>>> T is indeed unable to decide P but for the wrong reason: T[P] is
>>>> recursive
> 
>      I suppose one should not point out that "P", as defined, has
> "T" as a free variable, so is not a valid parameter to "T"?  But that's
> a quibble, as "P" could be re-written to have the code for "H" included.
> 
>>> T[P] is not recursive.  Maybe you don't understand what the CPL means?

http://www.ancientgeek.org.uk/CPL/CPL_Working_Papers.pdf
10.3.1 seems to indicate that rec routine P means that P is recursive.

>> Of course it is recursive, such is obvious even to the casual reader
>> who is unfamiliar with the CPL language (a clue: read the paragraph
>> before the definition of P again).
> 
>      "T[P]" is recursive only if "T" calls "P".  That is a pretty
> daft thing to do.  "Does this program ever halt?" "Dunno, let's find


Here is my best estimate of the CPL written in C:

void P()
{
   if (T((u32)P)
     HERE: goto HERE;
}

> out by running it."  If that doesn't seem stupid, imagine replacing
> "halt" by "kill the patient" or "blow up this nuclear power station".
> So a well-written "T" will not call its parameter.  This makes the
> whole argument as currently being debated moot;  if you don't call a
> routine, then pretty much all you can do with it is assign it or pass
> it as a parameter/operand, neither of which gets us any nearer to
> deciding whether it halts [or kills people].
> 
>      But in this form, it also has nothing to do with the Halting
> Problem, which would not be about some "T" that /calls/ "P" but about
> one that /inspects/ "P".  So the only sensible interpretation of what
> Strachey wrote is that the parameter to "T" is the /source/ of some
> program or routine "P".  In most languages, that source would be of
> "string" or perhaps "file" type or similar.  "P" would then be the
> string quoted above [preferably with also the string corresponding
> to the source of "T"].  Once this simple interpretation is made, the
> fundamental Strachey/Minsky/Sipser/Linz argument works perfectly well
> with no question of recursion [infinite, "pathological" or otherwise]
> unless "T" chooses it.
> 
>      That is why I have several times suggested, though with little
> success, that participants in this debate should be very clear about
> whether they are talking about "source" or "executable".  Simply
> calling things "H", "P", "T", "H_hat", ... does not convey this
> [necessary] information, and leads to Olcottian confusions.  Perhaps
> some contributors prefer to obscure the argument.
> 

In my case when P is passed to P it is the machine address of the 
machine language of P that is directly executed by an x86 emulator. This 
eliminates all of the extraneous complexity of switching back and forth 
between the machine and its description. The x86 description of P <is> P.

-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]

#36403

On Friday, 16 July 2021 at 23:52:53 UTC+8, olcott wrote:
> On 7/16/2021 10:12 AM, Andy Walker wrote: 
> > On 16/07/2021 14:39, Mr Flibble wrote: 
> >> On Fri, 16 Jul 2021 14:34:54 +0100 
> >> Ben Bacarisse <ben.u...@bsb.me.uk> wrote: 
> >>> Mr Flibble <fli...@reddwarf.jmc> quotes: 
> >>>> Suppose T[R] is a Boolean function taking a routine 
> >>>> (or program) R with no formal or free variables as its 
> >>>> argument [...]. 
> >>>> Consider the routine P defined as follows 
> 
> >>>> rec routine P 
> >>>> §L :if T[P] goto L 
> >>>> Return § 
> > [...] 
> >>>> T is indeed unable to decide P but for the wrong reason: T[P] is 
> >>>> recursive 
> > 
> > I suppose one should not point out that "P", as defined, has 
> > "T" as a free variable, so is not a valid parameter to "T"? But that's 
> > a quibble, as "P" could be re-written to have the code for "H" included. 
> > 
> >>> T[P] is not recursive. Maybe you don't understand what the CPL means?
> http://www.ancientgeek.org.uk/CPL/CPL_Working_Papers.pdf 
> 10.3.1 seems to indicate that rec routine P means that P is recursive.
> >> Of course it is recursive, such is obvious even to the casual reader 
> >> who is unfamiliar with the CPL language (a clue: read the paragraph 
> >> before the definition of P again). 
> > 
> > "T[P]" is recursive only if "T" calls "P". That is a pretty 
> > daft thing to do. "Does this program ever halt?" "Dunno, let's find
> Here is my best estimate of the CPL written in C: 
> 
> void P() 
> { 
> if (T((u32)P) 
> HERE: goto HERE;
> } 
> 
> > out by running it." If that doesn't seem stupid, imagine replacing 
> > "halt" by "kill the patient" or "blow up this nuclear power station". 
> > So a well-written "T" will not call its parameter. This makes the 
> > whole argument as currently being debated moot; if you don't call a 
> > routine, then pretty much all you can do with it is assign it or pass 
> > it as a parameter/operand, neither of which gets us any nearer to 
> > deciding whether it halts [or kills people]. 
> > 
> > But in this form, it also has nothing to do with the Halting 
> > Problem, which would not be about some "T" that /calls/ "P" but about 
> > one that /inspects/ "P". So the only sensible interpretation of what 
> > Strachey wrote is that the parameter to "T" is the /source/ of some 
> > program or routine "P". In most languages, that source would be of 
> > "string" or perhaps "file" type or similar. "P" would then be the 
> > string quoted above [preferably with also the string corresponding 
> > to the source of "T"]. Once this simple interpretation is made, the 
> > fundamental Strachey/Minsky/Sipser/Linz argument works perfectly well 
> > with no question of recursion [infinite, "pathological" or otherwise] 
> > unless "T" chooses it. 
> > 
> > That is why I have several times suggested, though with little 
> > success, that participants in this debate should be very clear about 
> > whether they are talking about "source" or "executable". Simply 
> > calling things "H", "P", "T", "H_hat", ... does not convey this 
> > [necessary] information, and leads to Olcottian confusions. Perhaps 
> > some contributors prefer to obscure the argument. 
> >
> In my case when P is passed to P it is the machine address of the 
> machine language of P that is directly executed by an x86 emulator. This 
> eliminates all of the extraneous complexity of switching back and forth 
> between the machine and its description. The x86 description of P <is> P.
> -- 
> Copyright 2021 Pete Olcott 
> 
> "Great spirits have always encountered violent opposition from mediocre 
> minds." Einstein

IMO, DOS + x86 assembly is already a TM simulator.
x86 emulator is redundant. Besides, the input of the x86 emulator
seems have to be COFF, this would made x86 emulator not a valid
proof machine (input and execution codes are different).

[toc] | [prev] | [next] | [standalone]

#36404

On 7/16/2021 11:11 AM, wij wrote:
> On Friday, 16 July 2021 at 23:52:53 UTC+8, olcott wrote:
>> On 7/16/2021 10:12 AM, Andy Walker wrote:
>>> On 16/07/2021 14:39, Mr Flibble wrote:
>>>> On Fri, 16 Jul 2021 14:34:54 +0100
>>>> Ben Bacarisse <ben.u...@bsb.me.uk> wrote:
>>>>> Mr Flibble <fli...@reddwarf.jmc> quotes:
>>>>>> Suppose T[R] is a Boolean function taking a routine
>>>>>> (or program) R with no formal or free variables as its
>>>>>> argument [...].
>>>>>> Consider the routine P defined as follows
>>
>>>>>> rec routine P
>>>>>> §L :if T[P] goto L
>>>>>> Return §
>>> [...]
>>>>>> T is indeed unable to decide P but for the wrong reason: T[P] is
>>>>>> recursive
>>>
>>> I suppose one should not point out that "P", as defined, has
>>> "T" as a free variable, so is not a valid parameter to "T"? But that's
>>> a quibble, as "P" could be re-written to have the code for "H" included.
>>>
>>>>> T[P] is not recursive. Maybe you don't understand what the CPL means?
>> http://www.ancientgeek.org.uk/CPL/CPL_Working_Papers.pdf
>> 10.3.1 seems to indicate that rec routine P means that P is recursive.
>>>> Of course it is recursive, such is obvious even to the casual reader
>>>> who is unfamiliar with the CPL language (a clue: read the paragraph
>>>> before the definition of P again).
>>>
>>> "T[P]" is recursive only if "T" calls "P". That is a pretty
>>> daft thing to do. "Does this program ever halt?" "Dunno, let's find
>> Here is my best estimate of the CPL written in C:
>>
>> void P()
>> {
>> if (T((u32)P)
>> HERE: goto HERE;
>> }
>>
>>> out by running it." If that doesn't seem stupid, imagine replacing
>>> "halt" by "kill the patient" or "blow up this nuclear power station".
>>> So a well-written "T" will not call its parameter. This makes the
>>> whole argument as currently being debated moot; if you don't call a
>>> routine, then pretty much all you can do with it is assign it or pass
>>> it as a parameter/operand, neither of which gets us any nearer to
>>> deciding whether it halts [or kills people].
>>>
>>> But in this form, it also has nothing to do with the Halting
>>> Problem, which would not be about some "T" that /calls/ "P" but about
>>> one that /inspects/ "P". So the only sensible interpretation of what
>>> Strachey wrote is that the parameter to "T" is the /source/ of some
>>> program or routine "P". In most languages, that source would be of
>>> "string" or perhaps "file" type or similar. "P" would then be the
>>> string quoted above [preferably with also the string corresponding
>>> to the source of "T"]. Once this simple interpretation is made, the
>>> fundamental Strachey/Minsky/Sipser/Linz argument works perfectly well
>>> with no question of recursion [infinite, "pathological" or otherwise]
>>> unless "T" chooses it.
>>>
>>> That is why I have several times suggested, though with little
>>> success, that participants in this debate should be very clear about
>>> whether they are talking about "source" or "executable". Simply
>>> calling things "H", "P", "T", "H_hat", ... does not convey this
>>> [necessary] information, and leads to Olcottian confusions. Perhaps
>>> some contributors prefer to obscure the argument.
>>>
>> In my case when P is passed to P it is the machine address of the
>> machine language of P that is directly executed by an x86 emulator. This
>> eliminates all of the extraneous complexity of switching back and forth
>> between the machine and its description. The x86 description of P <is> P.
>> -- 
>> Copyright 2021 Pete Olcott
>>
>> "Great spirits have always encountered violent opposition from mediocre
>> minds." Einstein
> 
> IMO, DOS + x86 assembly is already a TM simulator.
> x86 emulator is redundant. Besides, the input of the x86 emulator
> seems have to be COFF, this would made x86 emulator not a valid
> proof machine (input and execution codes are different).
> 

A halt decider must have absolute control over its slave process.
H steps through P(P) one instruction at a time and immediately aborts 
its simulation of P(P) as soon as the next instruction of P indicates 
that P is stuck in infinitely nested simulation.

-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]

#36381

On 7/16/2021 8:34 AM, Ben Bacarisse wrote:
> Mr Flibble <flibble@reddwarf.jmc> writes:
> 
>> All extant halting problem proofs appear to be predicated on a
>> misunderstanding of the following contradiction:
> 
> I don't think you've read any actual proofs, let along all of them.  Why
> you would even say such a thing?
> 
>> 	Suppose T[R] is a Boolean function taking a routine
>> 	(or program) R with no formal or free variables as its
>> 	argument and that for all R, T[R] — True if R terminates
>> 	if run and that T[R] = False if R does not terminate. Consider
>> 	the routine P defined as follows
>>
>> 		rec routine P
>> 			§L :if T[P] goto L
>> 		Return §
>>
>> 	If T[P] = True the routine P will loop, and it will
>> 	only terminate if T[P] = False. In each case T[P] has
>> 	exactly the wrong value, and this contradiction shows
>> 	that the function T cannot exist.
>>
>> 	[Strachey 1965]
>>
>> T is indeed unable to decide P but for the wrong reason: T[P] is
>> recursive
> 
> T[P] is not recursive.  Maybe you don't understand what the CPL means?
> 
> Further, this argument must fail for any of the actual proofs that are
> based on Turing machine because TMs have not functions, not calls and no
> recursion.
> 
Peter Linz Ĥ applied to the Turing machine description of itself: ⟨Ĥ⟩

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞
if M applied to wM halts, and

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
if M applied to wM does not halt

When we hypothesize that the halt decider embedded in Ĥ is simply a UTM 
then it seems that when the Peter Linz Ĥ is applied to its own Turing 
machine description ⟨Ĥ⟩ this specifies a computation that never halts.

Ĥ0.q0 copies its input ⟨Ĥ1⟩ to ⟨Ĥx⟩ then Ĥ0.qx simulates this input with 
the copy then
Ĥ1.q0 copies its input ⟨Ĥ2⟩ to ⟨Ĥy⟩ then Ĥ1.qx simulates this input with 
the copy then
Ĥ2.q0 copies its input ⟨Ĥ3⟩ to ⟨Ĥz⟩ then Ĥ2.qx simulates this input with 
the copy then ...

This is expressed in figure 12.4 as a cycle from qx to q0 to qx.

Within the hypothesis that the internal halt decider embedded within Ĥ 
simulates its input Ĥ applied to its own Turing machine description ⟨Ĥ⟩ 
derives infinitely nested simulation, unless this simulation is aborted.

Self-Evident-Truth (premise[1])
When the pure simulation of a machine on its input never halts we know 
that the execution of this machine on its input never halts.

Self-Evident-Truth (premise[2])
The ⟨Ĥ⟩ ⟨Ĥ⟩ input to the embedded simulating halt decider at Ĥ.qx is 
pure simulation that never halts.

∴ Sound Deductive Conclusion
The embedded simulating halt decider at Ĥ.qx correctly decides its 
input: ⟨Ĥ⟩ ⟨Ĥ⟩ is a computation that never halts.

Ĥ.q0 ⟨Ĥ⟩ specifies an infinite chain of invocations that is terminated 
at its third invocation. The first invocation of Ĥ.qx ⟨Ĥ⟩, ⟨Ĥ⟩ is the 
first element of an infinite chain of invocations.

It is common knowledge that when any invocation of an infinite chain of 
invocations is terminated that the whole chain terminates. That the 
first element of this infinite chain terminates after its third element 
has been terminated does not entail that this first element is an actual 
terminating computation.

The above is more clear when you can see the cycle in the state 
transition diagram of Ĥ(⟨Ĥ⟩) provided in this paper:

https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation


-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]

Page 1 of 3  [1] 2 3  Next page →

Back to top | Article view | comp.theory

csiph-web