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


Groups > comp.software-eng > #1995

Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)

From Kaz Kylheku <563-365-8930@kylheku.com>
Newsgroups comp.theory, comp.ai.philosophy, comp.software-eng
Subject Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)
Followup-To comp.theory
Date 2020-11-30 22:48 +0000
Organization Aioe.org NNTP Server
Message-ID <20201130142819.218@kylheku.com> (permalink)
References (12 earlier) <87qdncDHyLEDxlnCnZ2dnUU7-e_NnZ2d@giganews.com> <3W9xH.74663$3L49.14501@fx24.ams4> <oY2dnbTxTOKDr1jCnZ2dnUU7-QPNnZ2d@giganews.com> <20201130125512.705@kylheku.com> <I5udnWySYf1e_VjCnZ2dnUU7-KmdnZ2d@giganews.com>

Cross-posted to 3 groups.

Followups directed to: comp.theory

Show all headers | View raw


["Followup-To:" header set to comp.theory.]
On 2020-11-30, olcott <NoOne@NoWhere.com> wrote:
> On 11/30/2020 3:06 PM, Kaz Kylheku wrote:
>> On 2020-11-30, olcott <NoOne@NoWhere.com> wrote:
>>>> You still haven't explained how your non-halting decider can decide if
>>>> an arbitrary program given arbitrary input halts.
>>>
>>> My goal is not to actually solve the halting problem because to do this
>>> I would have to write a computer program that is ALL-KNOWING.
>> 
>> An imaginary "all knowing" entity is called an "oracle".
>> 
>> You believe that calculating halting requires an "oracle" program;
>> yet you don't see that as an impediment against computability?
>> 
>
> I already posted the complete execution trace of the details of how 
> Halts decides halting on H_Hat()
>
> void H_Hat(u32 P)
> {
>    u32 Input_Halts = Halts(P, P);
>    if (!Input_Halts)
>      HALT
>    else
>      HERE: goto HERE;
> }
>
> When Halts() always simulates its input it is obvious that 
> Halts((u32)H_Hat, (u32)H_Hat) specifies infinite recursion thus can be 
> decided as non halting.

You're blind to the obvious issue that H_Hat isn't a single
function/program. It's a *class* of programs.

The usual proofs just give a simple, direct representative of that class
for the sake of clarity, but it's obvious that an effective such program
can be written in an unlimited number of ways.

There is no way that a halting decider can distinguish whether the input
is one of the infinitely large class of H_Hat programs, or whether it an
innocent test case. That itself is a decision problem equivalent to
halting.

If you have make a halting-equivalent decision before deciding halting,
you've lost.

No level of simulation or execution trace monitoring, or any
number of nestings thereof, can fix this.

You're also forgeting that the Halts has to be *correct* on all inputs.
The author of Halts cannot be so obsessed with defeating H_Hat programs
that he overlooks correctness.

Suppose that Halts includes some simple hacks in order to guess whether
some trivial infinite loop or recursion is happening inside P (evidence
that it's being gamed). Those simple hacks can be always be used to
create a test case which coaxes an incorrect result out of Halts.

The author of H_Hat procedure always has the last word. The proposed
halting function Halt exists first, and H_Hat is crafted afterward,
using full knowledge of Halt. Moreover, as noted, H_Hat is actually an
instance from an infinite class of programs, not one specific program.

-- 
TXR Programming Language: http://nongnu.org/txr
Music DIY Mailing List:  http://www.kylheku.com/diy
ADA MP-1 Mailing List:   http://www.kylheku.com/mp1

Back to comp.software-eng | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread


Thread

Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) olcott <NoOne@NoWhere.com> - 2020-11-27 11:10 -0600
  Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2020-11-27 17:24 +0000
    Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) olcott <NoOne@NoWhere.com> - 2020-11-27 11:54 -0600
      Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) olcott <NoOne@NoWhere.com> - 2020-11-27 13:34 -0600
        Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) olcott <NoOne@NoWhere.com> - 2020-11-27 14:04 -0600
        Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) olcott <NoOne@NoWhere.com> - 2020-11-27 15:24 -0600
        Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(keys to understanding) olcott <NoOne@NoWhere.com> - 2020-11-27 21:57 -0600
          Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(keys to understanding) olcott <NoOne@NoWhere.com> - 2020-11-30 11:55 -0600
            Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(keys to understanding) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-11-30 21:06 +0000
              Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-11-30 15:14 -0600
                Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-11-30 22:48 +0000
                Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-11-30 17:23 -0600
                Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2020-11-30 23:54 +0000
                Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-11-30 18:08 -0600
                Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-11-30 18:18 -0600
                Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-11-30 18:59 -0600
                Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-01 01:40 +0000
                Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-11-30 19:48 -0600
                Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-01 08:41 +0000
                Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-12-01 08:52 -0600
                Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-01 21:30 +0000
                Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-12-01 16:34 -0600
                Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-01 23:10 +0000
                Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-12-01 12:12 -0600
                Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-01 18:35 +0000
                Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-12-01 12:54 -0600
                Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-12-01 10:08 -0600
                Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-01 01:23 +0000
                Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-11-30 19:30 -0600
  Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) olcott <NoOne@NoWhere.com> - 2020-11-27 12:46 -0600
    Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) olcott <NoOne@NoWhere.com> - 2020-11-27 15:40 -0600
      Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) olcott <NoOne@NoWhere.com> - 2020-11-27 15:52 -0600
      Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) olcott <NoOne@NoWhere.com> - 2020-11-27 17:09 -0600

csiph-web