Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #156164 > unrolled thread
| Started by | olcott <NoOne@NoWhere.com> |
|---|---|
| First post | 2020-10-27 14:30 -0500 |
| Last post | 2020-11-06 20:35 -0800 |
| Articles | 20 on this page of 45 — 11 participants |
Back to article view | Back to comp.lang.c
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 →
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-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]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2020-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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-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]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2020-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]
| From | Mostowski Collapse <janburse@fastmail.fm> |
|---|---|
| Date | 2020-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]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2020-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]
| From | Mostowski Collapse <janburse@fastmail.fm> |
|---|---|
| Date | 2020-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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-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]
| From | Mostowski Collapse <janburse@fastmail.fm> |
|---|---|
| Date | 2020-10-29 14:00 +0100 |
| Subject | Stop 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]
| From | Joe Pfeiffer <pfeiffer@cs.nmsu.edu> |
|---|---|
| Date | 2020-10-29 08:48 -0600 |
| Subject | Re: 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]
| From | Mike Terry <news.dead.person.stones@darjeeling.plus.com> |
|---|---|
| Date | 2020-10-29 15:17 +0000 |
| Subject | Re: 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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-10-29 11:13 -0500 |
| Subject | Re: 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]
| From | Manfred <noname@add.invalid> |
|---|---|
| Date | 2020-10-29 19:20 +0100 |
| Subject | Re: 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]
| From | Mike Terry <news.dead.person.stones@darjeeling.plus.com> |
|---|---|
| Date | 2020-10-29 18:55 +0000 |
| Subject | Re: 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