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


Groups > comp.lang.c > #156164 > unrolled thread

Architectural design of a halting problem solution

Started byolcott <NoOne@NoWhere.com>
First post2020-10-27 14:30 -0500
Last post2020-11-06 20:35 -0800
Articles 20 on this page of 45 — 11 participants

Back to article view | Back to comp.lang.c


Contents

  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

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →


#156181

Fromolcott <NoOne@NoWhere.com>
Date2020-10-27 16:54 -0500
Message-ID<MMednRXL_bdmCwXCnZ2dnUU7-YnNnZ2d@giganews.com>
In reply to#156179
On 10/27/2020 4:44 PM, Malcolm McLean wrote:
> On Tuesday, 27 October 2020 at 21:27:42 UTC, olcott wrote:
>> On 10/27/2020 4:11 PM, Mike Terry wrote:
>>> Exactly, and in another thread PO has confirmed that 'aborted' includes
>>> cases where the calculation in question halts.
>>
>> That is flat out not true. In every single case where this halt decider
>> decides that its input must be aborted its input would not otherwise
>> halt: bool Aborted_Because_Non_Halting_Behavior_Detected(u32 N, u32 M)
>>
>> Also in every single case where the above function returns false its
>> input has already halted.
>>
> So write a stub for bool Aborted_Because_Non_Halting_Behavior_Detected
> that just works on the input H_Hat, H_Hat.
> 

That would be no better than telling people that I must be correct 
because I really know that I am right, the same petitio principii 
logical fallacy that they are using in their utterly vacuous rebuttals.

I simply have to finish writing the actual halt deciding code for
bool Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat).
I already totally explained (2018-12-13 solution) exactly how this works.

-- 
Copyright 2020 Pete Olcott

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


#156186

Fromolcott <NoOne@NoWhere.com>
Date2020-10-27 18:43 -0500
Message-ID<NK-dndfehZEELQXCnZ2dnUU7-UHNnZ2d@giganews.com>
In reply to#156181
On 10/27/2020 5:07 PM, Malcolm McLean wrote:
> On Tuesday, 27 October 2020 at 21:54:11 UTC, olcott wrote:
>> On 10/27/2020 4:44 PM, Malcolm McLean wrote:
>>> On Tuesday, 27 October 2020 at 21:27:42 UTC, olcott wrote:
>>>> On 10/27/2020 4:11 PM, Mike Terry wrote:
>>>>> Exactly, and in another thread PO has confirmed that 'aborted' includes
>>>>> cases where the calculation in question halts.
>>>>
>>>> That is flat out not true. In every single case where this halt decider
>>>> decides that its input must be aborted its input would not otherwise
>>>> halt: bool Aborted_Because_Non_Halting_Behavior_Detected(u32 N, u32 M)
>>>>
>>>> Also in every single case where the above function returns false its
>>>> input has already halted.
>>>>
>>> So write a stub for bool Aborted_Because_Non_Halting_Behavior_Detected
>>> that just works on the input H_Hat, H_Hat.
>>>
>> That would be no better than telling people that I must be correct
>> because I really know that I am right, the same petitio principii
>> logical fallacy that they are using in their utterly vacuous rebuttals.
>>
> The "stub" cannot be
> 
> bool Aborted_Because_Non_Halting_Behaviour_Detected(U32 *M, U32 *N)
> {
>      return true;
> }
> 
> because that is no different from a halt decider, which can be inverted. It
> can't be "return false" for the same reason.
> So it must be something else. But only you can provide that. That will
> clarify everything.
>>
>> I simply have to finish writing the actual halt deciding code for
>> bool Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat).
>> I already totally explained (2018-12-13 solution) exactly how this works.
>>
> But it's a very long way round. If you were writing a real fully-fledged
> function, you would of course have to do this. But all you are doing is trying
> to refute Linz. So you only need to handle one case.

Not really. The hard part that took about 2000 hours was writing the 
x86utm operating system. I could finish the halt deciding code in 40 to 
80 hours.

I am definitely going to finish this code very soon. More importantly 
the impossibility of creating an input that
bool Aborted_Because_Non_Halting_Behaviour_Detected(u32 P, u32 I)
cannot correctly decide meaning that:

"It only reports true in those cases where its input would not halt 
unless it was aborted and its input was aborted"
and in all the others case is reports false.

I can't begin to understand why Mike Terry had such an awfully difficult 
time with something as self-evident as this meaning.

People don't seem to be able to stay focused on this single crucially 
important point:

Find an input where
bool Aborted_Because_Non_Halting_Behaviour_Detected(u32 P, u32 I)
gets the wrong answer or admit that there is no such input.


-- 
Copyright 2020 Pete Olcott

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


#156182

Fromolcott <NoOne@NoWhere.com>
Date2020-10-27 16:57 -0500
Message-ID<ouCdnTYc688mCgXCnZ2dnUU7-TfNnZ2d@giganews.com>
In reply to#156179
On 10/27/2020 4:33 PM, Mike Terry wrote:
> On 27/10/2020 21:27, olcott wrote:
>> On 10/27/2020 4:11 PM, Mike Terry wrote:
>>> On 27/10/2020 20:34, André G. Isaak wrote:
>>>> On 2020-10-27 14:13, olcott wrote:
>>>>> On 10/27/2020 3:03 PM, Mike Terry wrote:
>>>>>> On 27/10/2020 19:30, olcott wrote:
>>>>>>> Intuitively, a decider should be a Turing machine that given an
>>>>>>> input,
>>>>>>> halts and either accepts or rejects, relaying its answer in one of
>>>>>>> many
>>>>>>> equivalent ways, such as halting at an ACCEPT or REJECT state, or
>>>>>>> leaving its answer on the output tape.Yuval Filmus
>>>>>>> https://cs.stackexchange.com/questions/84433/what-is-decider
>>>>>>>
>>>>>>> Yuval Filmus top 0.04% overall Assistant Professor in the
>>>>>>> Department of
>>>>>>> Computer Science at the Technion.
>>>>>>>
>>>>>>> It is common knowledge that a halt decider with the following
>>>>>>> architectural design can be thwarted by an input program that does
>>>>>>> the
>>>>>>> opposite of whatever the halt decider decides:
>>>>>>>
>>>>>>> The halt decider divides all of its inputs into:
>>>>>>> (a) HALTS
>>>>>>> (b) DOES_NOT_HALT
>>>>>>
>>>>>> That's not an "architecural design" - it's part of the definition of
>>>>>> a halt decider.  It's good though, that you seem to be finally
>>>>>> admitting that the HP proof is correct.  The end of an era!!
>>>>>>
>>>>>> You may not get the fame and credibility you longed for, but at least
>>>>>> you can get on with the rest of your life.
>>>>>>
>>>>>>>
>>>>>>> This brand new architectural design cannot be thwarted by the
>>>>>>> conventional self-referential halting problem trick. With this 
>>>>>>> design
>>>>>>> there is no input that can be shown to be undecidable:
>>>>>>>
>>>>>>> The halt decider that divides all of its inputs into:
>>>>>>> (a) INPUT_PROGRAM_ABORTED_BECAUSE_NON_HALTING_BEHAVIOR_DETECTED
>>>>>>> (b) INPUT_PROGRAM_HAS_TERMINATED
>>>>>>>
>>>>>>
>>>>>> Aha, some kind of "aborted because non-halting behaviour detected"
>>>>>> decider!  Unfortunately there are plenty of decision problems that
>>>>>> /are/ decidable, including many whose domain is the same as that
>>>>>> halting problem's.  Possibly if you made the definition of the your
>>>>>> decision well defined, it could be one of those...
>>>>>>
>>>>> I have redefined the impossible halt decider into a
>>>>> NON_HALTING_DECIDER that divides all of its inputs into:
>>>>> (a) INPUT_PROGRAM_ABORTED_BECAUSE_NON_HALTING_BEHAVIOR_DETECTED
>>>>> (b) INPUT_PROGRAM_HAS_TERMINATED
>>>>>
>>>>> As you can see from (b) the NON_HALTING_DECIDER is still a halt
>>>>> decider.
>>>>
>>>> If your (a) and (b) are simply new names for 'doesn't halt' and 
>>>> 'halts',
>>>> then this is just as subject to Linz's proof as any other purported 
>>>> halt
>>>> decider.
>>>>
>>>> If they are not, and there are cases where 'aborted' and 'halted' don't
>>>> mean exactly the same thing, then what you have isn't a halt decider at
>>>> all.
>>>
>>> Exactly, and in another thread PO has confirmed that 'aborted'
>>> includes cases where the calculation in question halts.
>>
>> That is flat out not true. In every single case where this halt decider
>> decides that its input must be aborted its input would not otherwise
>> halt: bool Aborted_Because_Non_Halting_Behavior_Detected(u32 N, u32 M)
> 
> I explained in the other thread why that's just your confused thinking - 
> a confusion with the ".. *would* not otherwise halt ..", muddling up two 
> totally different programs.
> 
> I won't be repeating everything again in a new thread :)
> Mike.
> 

It is totally your confusion not mine.
bool Aborted_Because_Non_Halting_Behavior_Detected(u32 N, u32 M)
always decides its inputs correctly.

Your incorrect attempt at a counter-example was not an input to
bool Aborted_Because_Non_Halting_Behavior_Detected(u32 N, u32 M)

-- 
Copyright 2020 Pete Olcott

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


#156191

FromRichard Damon <Richard@Damon-Family.org>
Date2020-10-27 21:45 -0400
Message-ID<U24mH.334265$5_4.214940@fx40.iad>
In reply to#156179
On 10/27/20 5:27 PM, olcott wrote:
> 
> That is flat out not true. In every single case where this halt decider
> decides that its input must be aborted its input would not otherwise
> halt: bool Aborted_Because_Non_Halting_Behavior_Detected(u32 N, u32 M)
> 
> Also in every single case where the above function returns false its
> input has already halted.

Except that it DOES get the wrong answer for H_Hat, because H_Hat DOES
halt, at least if H give the answer that it aborted and H meets the
requirements of a decider to be always finite in execution.

The actual machine H_Hat was not aborted, just the simulation of the
model of H_Hat run inside H, and that simulation MUST by definition be
finite in execution whatever the program is that it is analyzing. You
can't 'blame' H_Hat for needing to be aborted, when the actual fault was
in you simulator.

Note, that your detrmination of 'Halting' is spurious, because it is a
function of what H did, and just shows a limitation of your chosen
method, By similar argument a poorly designed alternate H might just
decide that ALL machines had infinite behavior because H did in
analysing it so it aborts all machines. This makes 'Aborted' a
meaningless term.

Also, I suspect that you are going to have a problem handling a large
class of interesting programs which go towards or to infinite execution
but never have a repeated state. One example would be a program of the form:

define f(i)
   while true:
      if p(i) then Halt(i)
      else i := i+1

where p(i) is some finite executing test on i to determine if it meets
some property, and we want to find the first such number at least as
large as the input to the machine.

p could be a prime test, it could be an impossible test (one that will
never be true so it needs to be aborted) or it could be a test that just
won't be meet until i gets very big, like is i equal to the factorial of
a googleplex.

This machine NEVER repeats state, so your design can't determine
infinite execution by looking for repeated state. Determining between
the last two cases likely exceeds your machines capability, or your
patience. This is why 'debug stepping' is NOT really a viable method of
determining halting.

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


#156194

Fromolcott <NoOne@NoWhere.com>
Date2020-10-27 21:28 -0500
Message-ID<QK6dndjVoqzPSgXCnZ2dnUU7-dHNnZ2d@giganews.com>
In reply to#156191
On 10/27/2020 8:45 PM, Richard Damon wrote:
> On 10/27/20 5:27 PM, olcott wrote:
>>
>> That is flat out not true. In every single case where this halt decider
>> decides that its input must be aborted its input would not otherwise
>> halt: bool Aborted_Because_Non_Halting_Behavior_Detected(u32 N, u32 M)
>>
>> Also in every single case where the above function returns false its
>> input has already halted.
> 
> Except that it DOES get the wrong answer for H_Hat, because H_Hat DOES
> halt, at least if H give the answer that it aborted and H meets the
> requirements of a decider to be always finite in execution.


void H_Hat(u32 M)
{
   if (Aborted_Because_Non_Halting_Behavior_Detected(M, M))
     MOV_EAX_1  // Execution of M(M) has been aborted
   else
   {
     MOV_EAX_0  // M(M) has halted
     HERE: goto HERE;
   }
   HALT
}

01 int main()
02 {
03   u32 M = (u32)H_Hat;
04   H_Hat(M);
05   HALT
06 }

This line of H_Hat:
if (Aborted_Because_Non_Halting_Behavior_Detected(M, M))
invokes this function call
Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat).

The above function call returns true because its first H_Hat parameter 
must be aborted on its input (the second H_Hat parameter).

bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I)
can never ever be shown to decide its input incorrectly.

Line 04 of main: H_Hat(M);
IS NOT INPUT TO
bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I)





-- 
Copyright 2020 Pete Olcott

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


#156195

Fromolcott <NoOne@NoWhere.com>
Date2020-10-27 21:55 -0500
Message-ID<UPydnVwfnMciQAXCnZ2dnUU7-dnNnZ2d@giganews.com>
In reply to#156194
On 10/27/2020 9:48 PM, Richard Damon wrote:
> On 10/27/20 10:28 PM, olcott wrote:
>> On 10/27/2020 8:45 PM, Richard Damon wrote:
>>> On 10/27/20 5:27 PM, olcott wrote:
>>>>
>>>> That is flat out not true. In every single case where this halt decider
>>>> decides that its input must be aborted its input would not otherwise
>>>> halt: bool Aborted_Because_Non_Halting_Behavior_Detected(u32 N, u32 M)
>>>>
>>>> Also in every single case where the above function returns false its
>>>> input has already halted.
>>>
>>> Except that it DOES get the wrong answer for H_Hat, because H_Hat DOES
>>> halt, at least if H give the answer that it aborted and H meets the
>>> requirements of a decider to be always finite in execution.
>>
>>
>> void H_Hat(u32 M)
>> {
>>    if (Aborted_Because_Non_Halting_Behavior_Detected(M, M))
>>      MOV_EAX_1  // Execution of M(M) has been aborted
>>    else
>>    {
>>      MOV_EAX_0  // M(M) has halted
>>      HERE: goto HERE;
>>    }
>>    HALT
>> }
>>
>> 01 int main()
>> 02 {
>> 03   u32 M = (u32)H_Hat;
>> 04   H_Hat(M);
>> 05   HALT
>> 06 }
>>
>> This line of H_Hat:
>> if (Aborted_Because_Non_Halting_Behavior_Detected(M, M))
>> invokes this function call
>> Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat).
>>
>> The above function call returns true because its first H_Hat parameter
>> must be aborted on its input (the second H_Hat parameter).
>>
>> bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I)
>> can never ever be shown to decide its input incorrectly.
>>
>> Line 04 of main: H_Hat(M);
>> IS NOT INPUT TO
>> bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I)
>>
> H_Hat, the machine running, did NOT have infinite execution, therefore
> if H properly followed it through, it would have seen that it stopped.

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.

> You could say that was in infinite execution inside it, but that is
> within the implementation of H, which MUST NOT have infinite execution.
> That infinite execution only comes about due to a flawed choice of
> implementation of your halt detector, it is NOT inevitable and in fact
> your design can't handle a lot of machines that are interesting, because
> they may execute infinitely without every repeating a state.

There is not any input that can be shown to cause:
bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I)
to decide its input incorrectly.

I have already thought these things all the way through.

-- 
Copyright 2020 Pete Olcott

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


#156208

FromRichard Damon <Richard@Damon-Family.org>
Date2020-10-28 09:04 -0400
Message-ID<R%dmH.185728$6w2.163875@fx44.iad>
In reply to#156195
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.

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'.

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.

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.

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.

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.

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.

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


#156209

FromMostowski Collapse <janburse@fastmail.fm>
Date2020-10-28 14:13 +0100
Message-ID<48dde0d0-98a0-e184-1e22-8bd9c54b948f@fastmail.fm>
In reply to#156208
In what parallel universum does your nonsense
have anything to do with Prolog? You fucking
moron spammer Richard Damon?

No need to post responses on comp.lang.prolog.

Richard Damon schrieb:
> bla bla not a bit of Prolog bla bla

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


#156212

FromDavid Brown <david.brown@hesbynett.no>
Date2020-10-28 15:12 +0100
Message-ID<rnbu8s$pt5$1@dont-email.me>
In reply to#156209
On 28/10/2020 14:13, Mostowski Collapse wrote:
> 
> In what parallel universum does your nonsense
> have anything to do with Prolog? You fucking
> moron spammer Richard Damon?
> 
> No need to post responses on comp.lang.prolog.
> 
> Richard Damon schrieb:
>> bla bla not a bit of Prolog bla bla
> 


Even better - would all the sane people in these pointless "olcott"
threads /please/ remove the language groups from the replies?  They are
not remotely relevant or on-topic for C, C++ or Prolog.  I don't think
they are of much interest for theoretical computation either, but as I
don't follow comp.theory, I can't be sure.

We all know that this "Olcott" person is a manic poster and can't be
stopped.  But Richard Damon, and some of the others in these threads, is
a reasonable person.  If you folks want to discuss Olcott's ideas, make
sure you remove all non-relevant newsgroups from the posts and
follow-ups.  And if he insists on putting them back in, then please
boycott him altogether.

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


#156210

FromMostowski Collapse <janburse@fastmail.fm>
Date2020-10-28 14:13 +0100
Message-ID<rnbqpo$huh$3@solani.org>
In reply to#156208
In what parallel universum does your nonsense
have anything to do with Prolog? You fucking
moron spammer Richard Damon?

No need to post responses on comp.lang.prolog.

Richard Damon schrieb:
> bla bla not a bit of Prolog bla bla

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


#156234

Fromolcott <NoOne@NoWhere.com>
Date2020-10-28 18:18 -0500
Message-ID<Iv-dnWW1cqbbYQTCnZ2dnUU7-R_NnZ2d@giganews.com>
In reply to#156208
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

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


#156233

Fromolcott <NoOne@NoWhere.com>
Date2020-10-28 17:54 -0500
Message-ID<19ydnUE6q7UUawTCnZ2dnUU7-bvNnZ2d@giganews.com>
In reply to#156179
On 10/28/2020 4:38 AM, Alan Mackenzie wrote:
> In comp.theory olcott <NoOne@nowhere.com> wrote:
>> On 10/27/2020 4:11 PM, Mike Terry wrote:
>>> On 27/10/2020 20:34, André G. Isaak wrote:
>>>> On 2020-10-27 14:13, olcott wrote:
> 
> [ .... ]
> 
>>>>> I have redefined the impossible halt decider into a
>>>>> NON_HALTING_DECIDER that divides all of its inputs into:
>>>>> (a) INPUT_PROGRAM_ABORTED_BECAUSE_NON_HALTING_BEHAVIOR_DETECTED
>>>>> (b) INPUT_PROGRAM_HAS_TERMINATED
> 
>>>>> As you can see from (b) the NON_HALTING_DECIDER is still a halt
>>>>> decider.
> 
>>>> If your (a) and (b) are simply new names for 'doesn't halt' and
>>>> 'halts', then this is just as subject to Linz's proof as any other
>>>> purported halt decider.
> 
>>>> If they are not, and there are cases where 'aborted' and 'halted'
>>>> don't mean exactly the same thing, then what you have isn't a halt
>>>> decider at all.
> 
>>> Exactly, and in another thread PO has confirmed that 'aborted'
>>> includes cases where the calculation in question halts.
> 
>> That is flat out not true. In every single case where this halt decider
>> decides that its input must be aborted its input would not otherwise
>> halt: bool Aborted_Because_Non_Halting_Behavior_Detected(u32 N, u32 M)
> 
>> Also in every single case where the above function returns false its
>> input has already halted.
> 
> That leaves, of course, the cases where the function never returns,
> neither halting nor detecting "non-halting behaviour".

bool Aborted_Because_Non_Halting_Behavior_Detected(u32 N, u32 M)
It cannot be shown that it ever decides its input incorrectly.

Furthermore although very complex examples can be provided, none of 
these examples can be shown to be undecidable.



-- 
Copyright 2020 Pete Olcott

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


#156242

Fromolcott <NoOne@NoWhere.com>
Date2020-10-29 07:28 -0500
Message-ID<p9qdnQhFN8gYKAfCnZ2dnUU7-L3NnZ2d@giganews.com>
In reply to#156233
On 10/29/2020 1:59 AM, Alan Mackenzie wrote:
> In comp.theory olcott <NoOne@nowhere.com> wrote:
>> On 10/28/2020 4:38 AM, Alan Mackenzie wrote:
>>> In comp.theory olcott <NoOne@nowhere.com> wrote:
>>>> On 10/27/2020 4:11 PM, Mike Terry wrote:
> 
> [ .... ]
> 
>>>>> Exactly, and in another thread PO has confirmed that 'aborted'
>>>>> includes cases where the calculation in question halts.
> 
>>>> That is flat out not true. In every single case where this halt
>>>> decider decides that its input must be aborted its input would not
>>>> otherwise halt: bool
>>>> Aborted_Because_Non_Halting_Behavior_Detected(u32 N, u32 M)
> 
>>>> Also in every single case where the above function returns false its
>>>> input has already halted.
> 
>>> That leaves, of course, the cases where the function never returns,
>>> neither halting nor detecting "non-halting behaviour".
> 
>> bool Aborted_Because_Non_Halting_Behavior_Detected(u32 N, u32 M)
>> It cannot be shown that it ever decides its input incorrectly.
> 
> You're like a loop of tape.  You're all output with no input.  Why don't
> you actually consider the points people are making?

All but one of the points that people are making have been shown to be 
incorrect and people simply ignored that they have been proved wrong.
I am showing that the remaining unaddressed point is incorrect too (see 
below).

> Let me put the point to you again.  Even assuming A_B_N_H_B_D never
> returns a wrong answer, there are cases in which it will return _no_
> answer at all; it will carry on executing without ever stopping or
> displaying "non-halting behaviour" (whatever that means).

This cannot be proven. If a machine is proven to never repeat the same 
state and this machine is also proven to never terminate a very smart 
halt decider could replicate the proof of non-termination, stop 
executing its input and report non-halting.

Alternatively it cannot be proven that there is any program that meets 
those specs thus it cannot be proven that a counter-example exists.

>> Furthermore although very complex examples can be provided, none of
>> these examples can be shown to be undecidable.
> 
> Well, the burden of proof is on your side.  You must show that there are
> no such examples, complex or not.  This will necessarily involve you
> getting to know some mathematics.  Hint: this has been shown not to be
> possible.

My categorical has already been provided. I just addressed the last 
unaddressed point.

> 
> 
>> -- 
>> Copyright 2020 Pete Olcott
> 


-- 
Copyright 2020 Pete Olcott

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


#156243

Fromolcott <NoOne@NoWhere.com>
Date2020-10-29 07:35 -0500
Message-ID<sNOdnThKxoZgKwfCnZ2dnUU7-bfNnZ2d@giganews.com>
In reply to#156242
On 10/29/2020 7:28 AM, olcott wrote:
> On 10/29/2020 1:59 AM, Alan Mackenzie wrote:
>> In comp.theory olcott <NoOne@nowhere.com> wrote:
>>> On 10/28/2020 4:38 AM, Alan Mackenzie wrote:
>>>> In comp.theory olcott <NoOne@nowhere.com> wrote:
>>>>> On 10/27/2020 4:11 PM, Mike Terry wrote:
>>
>> [ .... ]
>>
>>>>>> Exactly, and in another thread PO has confirmed that 'aborted'
>>>>>> includes cases where the calculation in question halts.
>>
>>>>> That is flat out not true. In every single case where this halt
>>>>> decider decides that its input must be aborted its input would not
>>>>> otherwise halt: bool
>>>>> Aborted_Because_Non_Halting_Behavior_Detected(u32 N, u32 M)
>>
>>>>> Also in every single case where the above function returns false its
>>>>> input has already halted.
>>
>>>> That leaves, of course, the cases where the function never returns,
>>>> neither halting nor detecting "non-halting behaviour".
>>
>>> bool Aborted_Because_Non_Halting_Behavior_Detected(u32 N, u32 M)
>>> It cannot be shown that it ever decides its input incorrectly.
>>
>> You're like a loop of tape.  You're all output with no input.  Why don't
>> you actually consider the points people are making?
> 
> All but one of the points that people are making have been shown to be 
> incorrect and people simply ignored that they have been proved wrong.
> I am showing that the remaining unaddressed point is incorrect too (see 
> below).
> 
>> Let me put the point to you again.  Even assuming A_B_N_H_B_D never
>> returns a wrong answer, there are cases in which it will return _no_
>> answer at all; it will carry on executing without ever stopping or
>> displaying "non-halting behaviour" (whatever that means).
> 
> This cannot be proven. If a machine is proven to never repeat the same 
> state and this machine is also proven to never terminate a very smart 
> halt decider could replicate the proof of non-termination, stop 
> executing its input and report non-halting.
> 
> Alternatively it cannot be proven that there is any program that meets 
> those specs thus it cannot be proven that a counter-example exists.

If it can be proved that such a counter-example exists then it is not a 
counter-example, otherwise it cannot be proved that such a counter 
example exists.

Any program that can be proved does not halt can be decided on the basis 
of this proof.

Every counter-example must be provably undecidable.

> 
>>> Furthermore although very complex examples can be provided, none of
>>> these examples can be shown to be undecidable.
>>
>> Well, the burden of proof is on your side.  You must show that there are
>> no such examples, complex or not.  This will necessarily involve you
>> getting to know some mathematics.  Hint: this has been shown not to be
>> possible.
> 
> My categorical has already been provided. I just addressed the last 
> unaddressed point.

My categorical PROOF has already been provided. I just addressed the 
last  unaddressed point.

> 
>>
>>
>>> -- 
>>> Copyright 2020 Pete Olcott
>>
> 
> 


-- 
Copyright 2020 Pete Olcott

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


#156245 — Stop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution)

FromMostowski Collapse <janburse@fastmail.fm>
Date2020-10-29 14:00 +0100
SubjectStop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution)
Message-ID<rneee3$d0j$2@solani.org>
In reply to#156164
For gods sacke stop cross posting on 4 newsgroups.

Especially comp.lang.prolog doesn't make much sense.

RAM/RASP is probably best housed on comp.theory.

olcott schrieb:
 > I am a complete imbecial spammer

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


#156249 — Re: Stop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution)

FromJoe Pfeiffer <pfeiffer@cs.nmsu.edu>
Date2020-10-29 08:48 -0600
SubjectRe: Stop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution)
Message-ID<1bd011ccls.fsf@pfeifferfamily.net>
In reply to#156245
Mostowski Collapse <janburse@fastmail.fm> writes:

> For gods sacke stop cross posting on 4 newsgroups.
>
> Especially comp.lang.prolog doesn't make much sense.
>
> RAM/RASP is probably best housed on comp.theory.

Many people have asked this, and have made no impact on him.  The best
you can do is not interact with him on newsgroups where his crackpottery
is off-topic (sadly, to the best of my knoweldge there is no
alt.crackpot newsgroup, as that is the only one where he would really be
on-topic).

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


#156250 — Re: Stop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution)

FromMike Terry <news.dead.person.stones@darjeeling.plus.com>
Date2020-10-29 15:17 +0000
SubjectRe: Stop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution)
Message-ID<3c6dndQ5KJWQQAfCnZ2dnUU78InNnZ2d@brightview.co.uk>
In reply to#156249
On 29/10/2020 14:48, Joe Pfeiffer wrote:
> Mostowski Collapse <janburse@fastmail.fm> writes:
>
>> For gods sacke stop cross posting on 4 newsgroups.
>>
>> Especially comp.lang.prolog doesn't make much sense.
>>
>> RAM/RASP is probably best housed on comp.theory.
>
> Many people have asked this, and have made no impact on him.  The best
> you can do is not interact with him on newsgroups where his crackpottery
> is off-topic (sadly, to the best of my knoweldge there is no
> alt.crackpot newsgroup, as that is the only one where he would really be
> on-topic).
>

There IS an alt.crackpot newsgroup!  :)  Of course PO will not post there.

Anyway, the obvious solution to all this is that if someone doesn't want 
to be bothered by PO crackpottery in a particular newsgroup, they should 
just filter PO's posts from those groups.  I find that "ignore 
subthread" works best, as it also ignores any replies to PO.

Mike.

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


#156255 — Re: Stop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution)

Fromolcott <NoOne@NoWhere.com>
Date2020-10-29 11:13 -0500
SubjectRe: Stop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution)
Message-ID<2bednaGvMZqEdwfCnZ2dnUU7-T3NnZ2d@giganews.com>
In reply to#156250
On 10/29/2020 10:17 AM, Mike Terry wrote:
> On 29/10/2020 14:48, Joe Pfeiffer wrote:
>> Mostowski Collapse <janburse@fastmail.fm> writes:
>>
>>> For gods sacke stop cross posting on 4 newsgroups.
>>>
>>> Especially comp.lang.prolog doesn't make much sense.
>>>
>>> RAM/RASP is probably best housed on comp.theory.
>>
>> Many people have asked this, and have made no impact on him.  The best
>> you can do is not interact with him on newsgroups where his crackpottery
>> is off-topic (sadly, to the best of my knoweldge there is no
>> alt.crackpot newsgroup, as that is the only one where he would really be
>> on-topic).
>>
> 
> There IS an alt.crackpot newsgroup!  :)  Of course PO will not post there.
> 
> Anyway, the obvious solution to all this is that if someone doesn't want 
> to be bothered by PO crackpottery in a particular newsgroup, they should 
> just filter PO's posts from those groups.  I find that "ignore 
> subthread" works best, as it also ignores any replies to PO.
> 
> Mike.
> 

Sure these kind of ad homimen attacks are the first resort of clueless 
wonders and the last resort of people like yourself that diligently try 
to find a legitimate rebuttal.

Failing at that these people resort to ad hominem attacks because their 
only interest was in forming one kind of rebuttal or another and they 
never had any interest in forming mutual understanding.


-- 
Copyright 2020 Pete Olcott

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


#156263 — Re: Stop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution)

FromManfred <noname@add.invalid>
Date2020-10-29 19:20 +0100
SubjectRe: Stop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution)
Message-ID<rnf161$m68$1@gioia.aioe.org>
In reply to#156250
On 10/29/2020 4:17 PM, Mike Terry wrote:
> On 29/10/2020 14:48, Joe Pfeiffer wrote:
>> Mostowski Collapse <janburse@fastmail.fm> writes:
>>
>>> For gods sacke stop cross posting on 4 newsgroups.
>>>
>>> Especially comp.lang.prolog doesn't make much sense.
>>>
>>> RAM/RASP is probably best housed on comp.theory.
>>
>> Many people have asked this, and have made no impact on him.  The best
>> you can do is not interact with him on newsgroups where his crackpottery
>> is off-topic (sadly, to the best of my knoweldge there is no
>> alt.crackpot newsgroup, as that is the only one where he would really be
>> on-topic).
>>
> 
> There IS an alt.crackpot newsgroup!  :)  Of course PO will not post there.
> 
> Anyway, the obvious solution to all this is that if someone doesn't want 
> to be bothered by PO crackpottery in a particular newsgroup, they should 
> just filter PO's posts from those groups.  I find that "ignore 
> subthread" works best, as it also ignores any replies to PO.
> 
> Mike.
> 

The problem is that some repliers use poor newsreaders that break thread
ID consistency, and their replies manage to get through the "ignore 
subthread" killfile directive.
So, the advise still holds that those repliers should better remove the 
language groups from their replies, unless they aim at landing into the 
killfile themselves.

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


#156269 — Re: Stop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution)

FromMike Terry <news.dead.person.stones@darjeeling.plus.com>
Date2020-10-29 18:55 +0000
SubjectRe: Stop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution)
Message-ID<x_idnannRP6KjQbCnZ2dnUU78I3NnZ2d@brightview.co.uk>
In reply to#156263
On 29/10/2020 18:20, Manfred wrote:
> On 10/29/2020 4:17 PM, Mike Terry wrote:
>> On 29/10/2020 14:48, Joe Pfeiffer wrote:
>>> Mostowski Collapse <janburse@fastmail.fm> writes:
>>>
>>>> For gods sacke stop cross posting on 4 newsgroups.
>>>>
>>>> Especially comp.lang.prolog doesn't make much sense.
>>>>
>>>> RAM/RASP is probably best housed on comp.theory.
>>>
>>> Many people have asked this, and have made no impact on him.  The best
>>> you can do is not interact with him on newsgroups where his crackpottery
>>> is off-topic (sadly, to the best of my knoweldge there is no
>>> alt.crackpot newsgroup, as that is the only one where he would really be
>>> on-topic).
>>>
>>
>> There IS an alt.crackpot newsgroup!  :)  Of course PO will not post
>> there.
>>
>> Anyway, the obvious solution to all this is that if someone doesn't
>> want to be bothered by PO crackpottery in a particular newsgroup, they
>> should just filter PO's posts from those groups.  I find that "ignore
>> subthread" works best, as it also ignores any replies to PO.
>>
>> Mike.
>>
>
> The problem is that some repliers use poor newsreaders that break thread
> ID consistency, and their replies manage to get through the "ignore
> subthread" killfile directive.
> So, the advise still holds that those repliers should better remove the
> language groups from their replies, unless they aim at landing into the
> killfile themselves.

Interesting - I'm not familiar with that problem.  Perhaps you give me a 
couple of recent examples of such responses, and the newsgroup where 
you're seeing them?  (msgid values would be enough)

On the sci.math newsgroup I use ignore subthread fairly extensively and 
it pretty much eliminates posts by the well-known trolls/crackpots. 
Sometimes I think "why am I seeing this post about TrollPoster who's in 
my filter?".  But when I look closer I see it's not down to poor 
newsreaders - typically it is either that the post is merely /about/ 
TrollPoster and not actually a reply to her, or it is a reply to a 
TrollPoster post from such a long time ago that it's not recorded in my 
local newsreader.  (Neither of these is down to posters using poor 
newsreaders.)

Mike.

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


Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

Back to top | Article view | comp.lang.c


csiph-web