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


Groups > comp.software-eng > #2653 > unrolled thread

Re: A UTM halt decider <is> a pure function of its inputs (HP undecidability)

Started byolcott <NoOne@NoWhere.com>
First post2021-03-30 09:20 -0500
Last post2021-03-30 15:03 +0000
Articles 2 — 2 participants

Back to article view | Back to comp.software-eng

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.


Contents

  Re: A UTM halt decider <is> a pure function of its inputs (HP undecidability) olcott <NoOne@NoWhere.com> - 2021-03-30 09:20 -0500
    Re: A UTM halt decider <is> a pure function of its inputs (HP undecidability) Kaz Kylheku <563-365-8930@kylheku.com> - 2021-03-30 15:03 +0000

#2653 — Re: A UTM halt decider <is> a pure function of its inputs (HP undecidability)

Fromolcott <NoOne@NoWhere.com>
Date2021-03-30 09:20 -0500
SubjectRe: A UTM halt decider <is> a pure function of its inputs (HP undecidability)
Message-ID<oLydnQPuAMc8rv79nZ2dnUU7-VPNnZ2d@giganews.com>
On 3/30/2021 12:28 AM, Kaz Kylheku wrote:
> On 2021-03-30, olcott <NoOne@NoWhere.com> wrote:
>> Without changing the definition of H^ in the tiniest little bit I have
>> shown that it specifies infinite recursion:
> 
> That is untrue.
> 
> What H^ specifies depends on the nature of H, because the bulk of H^ is
> the sub-function H.

http://www.liarparadox.org/Peter_Linz_HP(Pages_318-319).pdf

Whenever H is a simulator then H^ <is> infinitely recursive never 
reaching the appended loop states whether or not the simulator always 
returns a value of true or false.

This by itself proves that the famous:
"do the opposite of whatever the halt decider decides"

     Now we construct a new Turing machine D with H as a
     subroutine. This new TM calls H to determine what M
     does when the input to M is its own description <M>.

     Once D has determined this information, it does the
     opposite.

     That is, it rejects if M accepts and accepts
     if M does not accept. (Sipser 1997:165)

Never has had any effect on halting problem undecidability
because no halt decider would ever return any value to H^.

Sipser, Michael 1997. Introduction to the Theory of Computation. Boston: 
PWS Publishing Company (165-167)


> 
> Infinite recursion obviously occurs for if we choose H which is just a
> trivial dispatcher that invokes P(I).
> 
> It's obvious by simple substitution of terms that since:
> 
>    H^(H^) calls H(H^, H^)
> 
> and
> 
>    H(P, I) = P(I)
> 
> it must be that:
> 
>    H^(H^) calls H^(^H)
> 
> If H is chosen in some other ways, then that doesn't hold.
> 
> The author of H^ doesn't constrain how H is to be defined, other
> than that it's a two-argument pure function returning a Boolean,
> whose P argument is a function similar to H^, and so forth.
> 


-- 
Copyright 2021 Pete Olcott

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

[toc] | [next] | [standalone]


#2654

FromKaz Kylheku <563-365-8930@kylheku.com>
Date2021-03-30 15:03 +0000
Message-ID<20210330075406.357@kylheku.com>
In reply to#2653
On 2021-03-30, olcott <NoOne@NoWhere.com> wrote:
> On 3/30/2021 12:28 AM, Kaz Kylheku wrote:
>> On 2021-03-30, olcott <NoOne@NoWhere.com> wrote:
>>> Without changing the definition of H^ in the tiniest little bit I have
>>> shown that it specifies infinite recursion:
>> 
>> That is untrue.
>> 
>> What H^ specifies depends on the nature of H, because the bulk of H^ is
>> the sub-function H.
>
> http://www.liarparadox.org/Peter_Linz_HP(Pages_318-319).pdf
>
> Whenever H is a simulator then H^ <is> infinitely recursive never 
> reaching the appended loop states whether or not the simulator always 
> returns a value of true or false.

H is not required to be a simulator.

If H simply executes its input, we know that it fails to decide due to
runaway recursion: the input calls the decider, which executes its
input, which calls the decider.

This is freshman-level obvious.

The first materials I ever read about the halting problem spelled this
out, for the dummies.

> Never has had any effect on halting problem undecidability

Not returning is completely, utterly relevant to undecidability.

The undecidability of halting means that a decision function can
only decide at most a subset of the possible cases, not all of them.

Outside of the subset which it decides, it misbehaves in one of several
ways: it either returns the wrong answer, or fails to halt, or else
something else, like failing due to a division by zero or similar
problem.

Runaway recursion falls under "fails to halt"; it's a failed case.

> because no halt decider would ever return any value to H^.

Except in your program, where a "pure function" sometimes returns a
value and sometimes doesn't, for the same pair of visible arguments!

-- 
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal

[toc] | [prev] | [standalone]


Back to top | Article view | comp.software-eng


csiph-web