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


Groups > comp.lang.c > #156234

Re: Architectural design of a halting problem solution

Subject Re: Architectural design of a halting problem solution
Newsgroups comp.theory, comp.lang.prolog, comp.lang.c, comp.lang.c++
References (6 earlier) <U24mH.334265$5_4.214940@fx40.iad> <QK6dndjVoqzPSgXCnZ2dnUU7-dHNnZ2d@giganews.com> <QZ4mH.358144$Av7.95213@fx34.iad> <UPydnVwfnMciQAXCnZ2dnUU7-dnNnZ2d@giganews.com> <R%dmH.185728$6w2.163875@fx44.iad>
From olcott <NoOne@NoWhere.com>
Date 2020-10-28 18:18 -0500
Message-ID <Iv-dnWW1cqbbYQTCnZ2dnUU7-R_NnZ2d@giganews.com> (permalink)

Cross-posted to 4 groups.

Show all headers | View raw


On 10/28/2020 8:04 AM, Richard Damon wrote:
> On 10/27/20 10:55 PM, olcott wrote:
>>
>> No that is not true. I thought that might be true too the first time
>> that I analyzed this months ago. It turns out that unless H_Hat is
>> aborted it really never does stop running. If we simply wait and see
>> what H_Hat does it never ever stops running.
> 
> And that is the problem with your H, not with H_Hat.
> 
> H, by definition, must have finite execution. If we can supply H with
> some input which it can't determine the right answer with finite
> execution, then H is NOT a proper halting determinater. Your 'abort'
> result is really, at least sometimes, an 'I don't know' answer, you
> haven't proven that the supplied program will never halt (because you
> haven't seen repeated state) or seen that it halted (which makes the
> answer easy) so it punts and just aborts and makes a bold statement,
> that can be wrong.

I did not answer these posts this morning so that I could work on 
providing the example program.

bool Aborted_Because_Non_Halting_Behavior_Detected(u32 M, u32 M).
There is no input that can be proved to be undecidable for the above 
function.


> It is theroretically possible, within the definition of H, that all H is
> is a finite regex on the input machine, or some magic hash. None of
> these can possibly have this infinite recursion issue, so H can't
> 'blame' the recursion on H_Hat, so can't claim that H_Hat 'was aborted'.

I have defined a Non_Halting decider that has no input that can be shown 
to be undecidable. It is possible to define this differently so that it
is no longer a decider for all of its input. This of course would form 
no rebuttal of my definition at all.

> Again part of the issue is you want to change the question, but if you
> do, you can't apply your results to the original question. The ONLY
> question of a Halt Decider is that H(M,N) will indicate in finite time,
> what will happen if we run M(N). It doesn't matter if H(M,N) releases
> the 7 plagues, if running M(N) doesn't, then that is not part of the answer.

I think that the only way that I changed the question is that the halt 
decider became a non-halting decider. It Accepts non-halting programs 
and Rejects halting programs.

> It is clear, that from the answer you say H(H_Hat, H_Hat) will produce,
> that is 'Will Not Halt' (that you call 'Aborted') that when you apply
> that to the run of H_Hat(H_Hat), and that machine terminates in finite
> time, the H(H_Hat, H_Hat) got the answer wrong.

You may not be able to understand that my analysis is correct until I 
have fully operational code. I worked on this all day.

> The question is NOT about what happened to the emulated M(N), because
> the problem doesn't assume emulation (in fact it can be shown that
> emulation can't be a universal solution), but what would happen to a
> REAL M(N) run.

You may not be able to understand that my analysis is correct until I 
have fully operational code. I worked on this all day.

This function can not be shown to have any undecidable inputs:
bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I)

int main()
{
   H_Hat(H_Hat);
}

Would never terminate unless this function aborts it input:
Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat)


> It is like disproving that you can't trisect an arbitrary angle with
> compass and straight edge, by saying you can if the angle happens to be
> a right angle. Different Question, different results.
> 
> The original, classical, halting problem statement has useful
> implication in the theory of Mathematics and Logic. Your modified
> question, I don't know of a use.

I defined a NON_HALT decider that always Accepts its input if its input 
would not halt and Rejects its input if its input would halt.

> Yes, you can disproof Linz, if you change to domain that you are
> applying Linz to. It has LONG been know that if you don't need to be a
> UNIVERSAL halt determinater, that there are a number of classes a Turing
> machines that you can determine if they will halt or not. The key here
> is that they can't handle any arbitrary Turing Machine. In particular,
> the easiest case is for machines that stay bounded over there full
> execution of the problem. It is the unboundedness that causes the
> problems, and is where you seem to have the issues, and where other
> aspects you have problems with, like incompleteness, come in.
> 

I defined a NON_HALTING decider that always Accepts NON_HALTING input
and Rejects HALTING input.


-- 
Copyright 2020 Pete Olcott

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread


Thread

Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-27 14:30 -0500
  Re: Architectural design of a halting problem solution André G. Isaak <agisaak@gm.invalid> - 2020-10-27 13:46 -0600
    Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-27 15:02 -0500
  Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-27 15:13 -0500
    Re: Architectural design of a halting problem solution André G. Isaak <agisaak@gm.invalid> - 2020-10-27 14:34 -0600
      Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-27 16:23 -0500
        Re: Architectural design of a halting problem solution André G. Isaak <agisaak@gm.invalid> - 2020-10-27 22:49 -0600
          Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-28 00:05 -0500
            Re: Architectural design of a halting problem solution André G. Isaak <agisaak@gm.invalid> - 2020-10-27 23:25 -0600
              Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-28 00:31 -0500
                Re: Architectural design of a halting problem solution André G. Isaak <agisaak@gm.invalid> - 2020-10-27 23:55 -0600
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-28 17:50 -0500
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-28 21:09 -0500
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-29 07:18 -0500
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-29 10:29 -0500
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-29 11:05 -0500
                Re: Architectural design of a halting problem solution André G. Isaak <agisaak@gm.invalid> - 2020-10-29 10:55 -0600
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-29 12:52 -0500
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-29 13:25 -0500
      Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-27 16:27 -0500
        Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-27 16:54 -0500
          Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-27 18:43 -0500
        Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-27 16:57 -0500
        Re: Architectural design of a halting problem solution Richard Damon <Richard@Damon-Family.org> - 2020-10-27 21:45 -0400
          Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-27 21:28 -0500
            Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-27 21:55 -0500
              Re: Architectural design of a halting problem solution Richard Damon <Richard@Damon-Family.org> - 2020-10-28 09:04 -0400
                Re: Architectural design of a halting problem solution Mostowski Collapse <janburse@fastmail.fm> - 2020-10-28 14:13 +0100
                Re: Architectural design of a halting problem solution David Brown <david.brown@hesbynett.no> - 2020-10-28 15:12 +0100
                Re: Architectural design of a halting problem solution Mostowski Collapse <janburse@fastmail.fm> - 2020-10-28 14:13 +0100
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-28 18:18 -0500
        Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-28 17:54 -0500
          Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-29 07:28 -0500
            Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-29 07:35 -0500
  Stop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution) Mostowski Collapse <janburse@fastmail.fm> - 2020-10-29 14:00 +0100
    Re: Stop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution) Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2020-10-29 08:48 -0600
      Re: Stop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-10-29 15:17 +0000
        Re: Stop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution) olcott <NoOne@NoWhere.com> - 2020-10-29 11:13 -0500
        Re: Stop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution) Manfred <noname@add.invalid> - 2020-10-29 19:20 +0100
          Re: Stop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-10-29 18:55 +0000
            Re: Stop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution) David Brown <david.brown@hesbynett.no> - 2020-10-30 11:02 +0100
              Re: Stop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-10-30 10:52 +0000
                Re: Stop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution) Jorgen Grahn <grahn+nntp@snipabacken.se> - 2020-10-30 19:47 +0000
  Re: Stop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution Mostowski Collapse <janburse@fastmail.fm> - 2020-10-29 19:40 +0100
  Re: Architectural design of a halting problem solution jenniferjeson35@gmail.com - 2020-11-06 20:35 -0800

csiph-web