Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Refuting the halting problem proofs with fully operational code
36 views
Skip to first unread message
olcott
Mar 9, 2021, 11:26:56 AM3/9/21
to
On 3/9/2021 10:16 AM, R Kym Horsell wrote:
> Richard Damon <Ric...@damon-family.org> wrote:
>> On 3/8/21 11:28 PM, olcott wrote:
>>> I will respond to you to the extent that you critique how this:
>>> http://www.liarparadox.org/Eliminating_pathological_self_reference_error_from_the_halting_problem.pdf
>>> is computationally equivalent to this:
>>> A halt decider UTM that simply simulates its input
>>> until its input halts on its own or the halt decider
>>> determines that its input would never halt on its own
>>> thus stops simulating it.
>>> And how that refutes the halting problem proofs.
>>> Everyting else will be construed as a dishonest dodge.
>>> I think that Ben masters the dishonest dodge in an attempt
>>> to mask his ignorance of the subject matter.
>> It claims to refute the proofs by building a strawman with a different
>> Halting Problem.
>> The decision to detect 'would never halt' is flawed in that it doesn't
>> take into account the conditional execution of the simulated halt
>> decider itself.
>> You have made the mistake of assuming the conclusion.
>
> That happened at least when O tried to "solve" the Halting Problem
> by detecting infinite recursion -- a known equivalent problem.
> (Whether a program in general reaches any specified point on all
> inputs -- e.g. on the inside of an "if" condition where a recursive call
> happens -- is the same as the HP).
>
> The joke part was the "halt detection" was carried out by a step-by-step
> simulator.
>
> Whether O has himself been in a loop on this problem the last few years
> is the same as the HP and a meta joke.
>
You can read the updated paper, I just added much more in depth analysis
of exactly why the halting problem was previuosly considered unsolvable
and why this never actually was the case.
I provide an actual execution trace of fully operational code to prove
my point.
http://www.liarparadox.org/Eliminating_pathological_self_reference_error_from_the_halting_problem.pdf
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
> Richard Damon <Ric...@damon-family.org> wrote:
>> On 3/8/21 11:28 PM, olcott wrote:
>>> I will respond to you to the extent that you critique how this:
>>> http://www.liarparadox.org/Eliminating_pathological_self_reference_error_from_the_halting_problem.pdf
>>> is computationally equivalent to this:
>>> A halt decider UTM that simply simulates its input
>>> until its input halts on its own or the halt decider
>>> determines that its input would never halt on its own
>>> thus stops simulating it.
>>> And how that refutes the halting problem proofs.
>>> Everyting else will be construed as a dishonest dodge.
>>> I think that Ben masters the dishonest dodge in an attempt
>>> to mask his ignorance of the subject matter.
>> It claims to refute the proofs by building a strawman with a different
>> Halting Problem.
>> The decision to detect 'would never halt' is flawed in that it doesn't
>> take into account the conditional execution of the simulated halt
>> decider itself.
>> You have made the mistake of assuming the conclusion.
>
> That happened at least when O tried to "solve" the Halting Problem
> by detecting infinite recursion -- a known equivalent problem.
> (Whether a program in general reaches any specified point on all
> inputs -- e.g. on the inside of an "if" condition where a recursive call
> happens -- is the same as the HP).
>
> The joke part was the "halt detection" was carried out by a step-by-step
> simulator.
>
> Whether O has himself been in a loop on this problem the last few years
> is the same as the HP and a meta joke.
>
You can read the updated paper, I just added much more in depth analysis
of exactly why the halting problem was previuosly considered unsolvable
and why this never actually was the case.
I provide an actual execution trace of fully operational code to prove
my point.
http://www.liarparadox.org/Eliminating_pathological_self_reference_error_from_the_halting_problem.pdf
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
olcott
Mar 9, 2021, 12:54:48 PM3/9/21
to
On 3/9/2021 11:35 AM, Kaz Kylheku wrote:
> On 2021-03-09, olcott <No...@NoWhere.com> wrote:
>> On 3/9/2021 11:17 AM, Kaz Kylheku wrote:
>>> refers to a local decider which you said no longer exists; there is only
>>> a global decider.
>>>
>>> Anyone reading the code can see by inspection that if H_Hat(H_Hat) is
>>> called, it must obtain a zero from Halts, and therefore it will halt.
>>>
>>
>> You know that whenever a software function invokes another software
>> function in what would otherwise be infinite recursion if the execution
>> of the first function was not aborted that the second function would
>> never return any value to its caller in every case (aborted or not).
>
> I don't understand this subjunctive "would".
>
> That is your problem.
>
> When we say that a function "would" be something else, that is
> precisely the same thing as "isn't".
>
If X does not do Y then Z
If X does do Y then not Z
proving that not Z depends on X doing Y
Think of the halt decider as a UTM that simply simulates its input until
because both inputs that halt on their own and halt because the halt
decider stops simulating them halt.
When we remove the pathological self-reference error we correct this
question so that it can discern the halting behavior of its inputs then
the question becomes:
Would the input program have infinite execution if the halt decider did
not stop simulating it?
> On 2021-03-09, olcott <No...@NoWhere.com> wrote:
>> On 3/9/2021 11:17 AM, Kaz Kylheku wrote:
>>> On 2021-03-09, olcott <No...@NoWhere.com> wrote:
>>>> You can read the updated paper, I just added much more in depth analysis
>>>> of exactly why the halting problem was previuosly considered unsolvable
>>>> and why this never actually was the case.
>>>>
>>>> I provide an actual execution trace of fully operational code to prove
>>>> my point.
>>>>
>>>> http://www.liarparadox.org/Eliminating_pathological_self_reference_error_from_the_halting_problem.pdf
>>>
>>> Updated? It looks like the same content as two days ago. It still
>>>> You can read the updated paper, I just added much more in depth analysis
>>>> of exactly why the halting problem was previuosly considered unsolvable
>>>> and why this never actually was the case.
>>>>
>>>> I provide an actual execution trace of fully operational code to prove
>>>> my point.
>>>>
>>>> http://www.liarparadox.org/Eliminating_pathological_self_reference_error_from_the_halting_problem.pdf
>>>
>>> refers to a local decider which you said no longer exists; there is only
>>> a global decider.
>>>
>>> Anyone reading the code can see by inspection that if H_Hat(H_Hat) is
>>> called, it must obtain a zero from Halts, and therefore it will halt.
>>>
>>
>> You know that whenever a software function invokes another software
>> function in what would otherwise be infinite recursion if the execution
>> of the first function was not aborted that the second function would
>> never return any value to its caller in every case (aborted or not).
>
> I don't understand this subjunctive "would".
>
> That is your problem.
>
> When we say that a function "would" be something else, that is
> precisely the same thing as "isn't".
>
If X does not do Y then Z
If X does do Y then not Z
proving that not Z depends on X doing Y
Think of the halt decider as a UTM that simply simulates its input until
its input halts on its own or the halt decider determines that its input
would never halt on its own thus stops simulating it.
It cannot be answering the question: Does the input halt on its input?
would never halt on its own thus stops simulating it.
because both inputs that halt on their own and halt because the halt
decider stops simulating them halt.
When we remove the pathological self-reference error we correct this
question so that it can discern the halting behavior of its inputs then
the question becomes:
Would the input program have infinite execution if the halt decider did
not stop simulating it?
olcott
Mar 9, 2021, 5:56:40 PM3/9/21
to
Eliminating pathological self-reference error from the halting problem
The pathological self reference error occurs whenever a question or
decision problem cannot be correctly answered because both of the yes/no
or true/false answers are contradicted.
If we ask Jack[1] this question: Will your answer to this question be no?
Neither answer of yes or no is correct because they are both contradicted.
When an input program is defined to do opposite of whatever the halt
decider decides about its halt status then we have the same pathological
self-reference error as Jack's question.
If the halt decider Halts() returns a value of true to H_Hat() then
H_Hat() would go into an infinite loop and never halt. If the halt
decider Halts() returns a value of false to H_Hat() then H_Hat would
immediately stop running.
The simplest way to define a halt decider is to make a program that
simply runs its input to see what it does. In technical terms this would
be a universal Turing machine (UTM) that has been adapted to become a
halt decider. This UTM would simply simulate the execution of its input
the UTM to see what its input does it must keep track of an execution
trace of its input.
Every (at least partial) halt decider that decides the halting status of
its input on the basis of its examination of the execution trace of its
own simulation of this input would correctly decide the conventional
halting problem counter-examples as not halting.
The x86utm operating system was created so that halt deciders written in
the C programming language would be computationally equivalent to the
execution of actual Turing machines. These (at least partial) halt
deciders base their halting decision on examining the execution trace of
the x86 machine language of their input. The input is the COFF object
file output of a C compiler and is directly executed by the x86 emulator.
The halt decider Halts() determines that H_Hat() called it in infinite
recursion, on the basis of the x86 machine language execution trace
shown below, stop simulating its input, and decide not halting on the
basis that its input would not halt.
void H_Hat(u32 P)
{
u32 Input_Would_Halt = Halts(P, P);
if (Input_Would_Halt)
HERE: goto HERE;
}
int main()
{
u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
Output("Input_Would_Halt = ", Input_Would_Halt);
}
_H_Hat()
[0000088f](01) 55 push ebp
[00000890](02) 8bec mov ebp,esp
[00000892](01) 51 push ecx
[00000893](03) 8b4508 mov eax,[ebp+08]
[00000896](01) 50 push eax
[00000897](03) 8b4d08 mov ecx,[ebp+08]
[0000089a](01) 51 push ecx
[0000089b](05) e87ffeffff call 0000071f
[000008a0](03) 83c408 add esp,+08
[000008a3](03) 8945fc mov [ebp-04],eax
[000008a6](04) 837dfc00 cmp dword [ebp-04],+00
[000008aa](02) 7402 jz 000008ae
[000008ac](02) ebfe jmp 000008ac
[000008ae](02) 8be5 mov esp,ebp
[000008b0](01) 5d pop ebp
[000008b1](01) c3 ret
_main()
[000008bf](01) 55 push ebp
[000008c0](02) 8bec mov ebp,esp
[000008c2](01) 51 push ecx
[000008c3](05) 688f080000 push 0000088f
[000008c8](05) 688f080000 push 0000088f
[000008cd](05) e84dfeffff call 0000071f
[000008d2](03) 83c408 add esp,+08
[000008d5](03) 8945fc mov [ebp-04],eax
[000008d8](03) 8b45fc mov eax,[ebp-04]
[000008db](01) 50 push eax
[000008dc](05) 680b030000 push 0000030b
[000008e1](05) e869faffff call 0000034f
[000008e6](03) 83c408 add esp,+08
[000008e9](02) 33c0 xor eax,eax
[000008eb](02) 8be5 mov esp,ebp
[000008ed](01) 5d pop ebp
[000008ee](01) c3 ret
Columns
(1) Execution trace sequence number
(2) Machine address of instruction
(3) Machine address of top of stack
(4) Value of top of stack after instruction executed
(5) Number of bytes of machine code
(6) Machine language bytes
(7) Assembly language text
(01)[000008bf][00011208][00000000](01) 55 push ebp
(02)[000008c0][00011208][00000000](02) 8bec mov ebp,esp
(03)[000008c2][00011204][00000000](01) 51 push ecx
(04)[000008c3][00011200][0000088f](05) 688f080000 push 0000088f
(05)[000008c8][000111fc][0000088f](05) 688f080000 push 0000088f
(06)[000008cd][000111f8][000008d2](05) e84dfeffff call 0000071f
(07)[0000088f][00031288][0003128c](01) 55 push ebp
(08)[00000890][00031288][0003128c](02) 8bec mov ebp,esp
(09)[00000892][00031284][00021258](01) 51 push ecx
(10)[00000893][00031284][00021258](03) 8b4508 mov eax,[ebp+08]
(11)[00000896][00031280][0000088f](01) 50 push eax
(12)[00000897][00031280][0000088f](03) 8b4d08 mov ecx,[ebp+08]
(13)[0000089a][0003127c][0000088f](01) 51 push ecx
(14)[0000089b][00031278][000008a0](05) e87ffeffff call 0000071f
Line(11) Push second parameter value: 0000088f to Halts()
Line(13) Push first parameter value: 0000088f to Halts()
Line(14) H_Halt() calls Halts(0000088f, 0000088f)
(15)[0000088f][00042430][00042434](01) 55 push ebp
(16)[00000890][00042430][00042434](02) 8bec mov ebp,esp
(17)[00000892][0004242c][00032400](01) 51 push ecx
(18)[00000893][0004242c][00032400](03) 8b4508 mov eax,[ebp+08]
(19)[00000896][00042428][0000088f](01) 50 push eax
(20)[00000897][00042428][0000088f](03) 8b4d08 mov ecx,[ebp+08]
(21)[0000089a][00042424][0000088f](01) 51 push ecx
(22)[0000089b][00042420][000008a0](05) e87ffeffff call 0000071f
Line(19) Push second parameter value: 0000088f to Halts()
Line(21) Push first parameter value: 0000088f to Halts()
Line(22) H_Halt() calls Halts(0000088f, 0000088f)
Infinite Recursion Detected Simulation Stopped on the basis that H_Hat()
calls Halts() with the same data a second time in sequence from the same
machine address.
(23)[000008d2][00011204][00000000](03) 83c408 add esp,+08
(24)[000008d5][00011204][00000000](03) 8945fc mov [ebp-04],eax
(25)[000008d8][00011204][00000000](03) 8b45fc mov eax,[ebp-04]
(26)[000008db][00011200][00000000](01) 50 push eax
(27)[000008dc][000111fc][0000030b](05) 680b030000 push 0000030b
(28)[000008e1][000111f8][000008e6](05) e869faffff call 0000034f
Input_Would_Halt = 0
(29)[000008e6][00011204][00000000](03) 83c408 add esp,+08
(30)[000008e9][00011204][00000000](02) 33c0 xor eax,eax
(31)[000008eb][00011208][00000000](02) 8be5 mov esp,ebp
(32)[000008ed][0001120c][00010000](01) 5d pop ebp
(33)[000008ee][00011210][00000080](01) c3 ret
Number_of_User_Instructions(33)
Copyright 2021 PL Olcott
[1] sci.logic --- Daryl McCullough --- Jun 25, 2004, 6:30:39 PM
[The Psychology of Self-Reference]
https://groups.google.com/g/sci.logic/c/4kIXI1kxmsI/m/hRroMoQZx2IJ
http://www.liarparadox.org/Eliminating_pathological_self_reference_error_from_the_halting_problem.pdf
The pathological self reference error occurs whenever a question or
decision problem cannot be correctly answered because both of the yes/no
or true/false answers are contradicted.
If we ask Jack[1] this question: Will your answer to this question be no?
Neither answer of yes or no is correct because they are both contradicted.
When an input program is defined to do opposite of whatever the halt
decider decides about its halt status then we have the same pathological
self-reference error as Jack's question.
If the halt decider Halts() returns a value of true to H_Hat() then
H_Hat() would go into an infinite loop and never halt. If the halt
decider Halts() returns a value of false to H_Hat() then H_Hat would
immediately stop running.
The simplest way to define a halt decider is to make a program that
simply runs its input to see what it does. In technical terms this would
be a universal Turing machine (UTM) that has been adapted to become a
halt decider. This UTM would simply simulate the execution of its input
until its input halts on its own or the halt decider determines that its
input would never halt on its own and stops simulating it. In order for
the UTM to see what its input does it must keep track of an execution
trace of its input.
Every (at least partial) halt decider that decides the halting status of
its input on the basis of its examination of the execution trace of its
own simulation of this input would correctly decide the conventional
halting problem counter-examples as not halting.
The x86utm operating system was created so that halt deciders written in
the C programming language would be computationally equivalent to the
execution of actual Turing machines. These (at least partial) halt
deciders base their halting decision on examining the execution trace of
the x86 machine language of their input. The input is the COFF object
file output of a C compiler and is directly executed by the x86 emulator.
The halt decider Halts() determines that H_Hat() called it in infinite
recursion, on the basis of the x86 machine language execution trace
shown below, stop simulating its input, and decide not halting on the
basis that its input would not halt.
void H_Hat(u32 P)
{
u32 Input_Would_Halt = Halts(P, P);
if (Input_Would_Halt)
HERE: goto HERE;
}
int main()
{
u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
Output("Input_Would_Halt = ", Input_Would_Halt);
}
_H_Hat()
[0000088f](01) 55 push ebp
[00000890](02) 8bec mov ebp,esp
[00000892](01) 51 push ecx
[00000893](03) 8b4508 mov eax,[ebp+08]
[00000896](01) 50 push eax
[00000897](03) 8b4d08 mov ecx,[ebp+08]
[0000089a](01) 51 push ecx
[0000089b](05) e87ffeffff call 0000071f
[000008a0](03) 83c408 add esp,+08
[000008a3](03) 8945fc mov [ebp-04],eax
[000008a6](04) 837dfc00 cmp dword [ebp-04],+00
[000008aa](02) 7402 jz 000008ae
[000008ac](02) ebfe jmp 000008ac
[000008ae](02) 8be5 mov esp,ebp
[000008b0](01) 5d pop ebp
[000008b1](01) c3 ret
_main()
[000008bf](01) 55 push ebp
[000008c0](02) 8bec mov ebp,esp
[000008c2](01) 51 push ecx
[000008c3](05) 688f080000 push 0000088f
[000008c8](05) 688f080000 push 0000088f
[000008cd](05) e84dfeffff call 0000071f
[000008d2](03) 83c408 add esp,+08
[000008d5](03) 8945fc mov [ebp-04],eax
[000008d8](03) 8b45fc mov eax,[ebp-04]
[000008db](01) 50 push eax
[000008dc](05) 680b030000 push 0000030b
[000008e1](05) e869faffff call 0000034f
[000008e6](03) 83c408 add esp,+08
[000008e9](02) 33c0 xor eax,eax
[000008eb](02) 8be5 mov esp,ebp
[000008ed](01) 5d pop ebp
[000008ee](01) c3 ret
Columns
(1) Execution trace sequence number
(2) Machine address of instruction
(3) Machine address of top of stack
(4) Value of top of stack after instruction executed
(5) Number of bytes of machine code
(6) Machine language bytes
(7) Assembly language text
(01)[000008bf][00011208][00000000](01) 55 push ebp
(02)[000008c0][00011208][00000000](02) 8bec mov ebp,esp
(03)[000008c2][00011204][00000000](01) 51 push ecx
(04)[000008c3][00011200][0000088f](05) 688f080000 push 0000088f
(05)[000008c8][000111fc][0000088f](05) 688f080000 push 0000088f
(06)[000008cd][000111f8][000008d2](05) e84dfeffff call 0000071f
(07)[0000088f][00031288][0003128c](01) 55 push ebp
(08)[00000890][00031288][0003128c](02) 8bec mov ebp,esp
(09)[00000892][00031284][00021258](01) 51 push ecx
(10)[00000893][00031284][00021258](03) 8b4508 mov eax,[ebp+08]
(11)[00000896][00031280][0000088f](01) 50 push eax
(12)[00000897][00031280][0000088f](03) 8b4d08 mov ecx,[ebp+08]
(13)[0000089a][0003127c][0000088f](01) 51 push ecx
(14)[0000089b][00031278][000008a0](05) e87ffeffff call 0000071f
Line(11) Push second parameter value: 0000088f to Halts()
Line(13) Push first parameter value: 0000088f to Halts()
Line(14) H_Halt() calls Halts(0000088f, 0000088f)
(15)[0000088f][00042430][00042434](01) 55 push ebp
(16)[00000890][00042430][00042434](02) 8bec mov ebp,esp
(17)[00000892][0004242c][00032400](01) 51 push ecx
(18)[00000893][0004242c][00032400](03) 8b4508 mov eax,[ebp+08]
(19)[00000896][00042428][0000088f](01) 50 push eax
(20)[00000897][00042428][0000088f](03) 8b4d08 mov ecx,[ebp+08]
(21)[0000089a][00042424][0000088f](01) 51 push ecx
(22)[0000089b][00042420][000008a0](05) e87ffeffff call 0000071f
Line(19) Push second parameter value: 0000088f to Halts()
Line(21) Push first parameter value: 0000088f to Halts()
Line(22) H_Halt() calls Halts(0000088f, 0000088f)
Infinite Recursion Detected Simulation Stopped on the basis that H_Hat()
calls Halts() with the same data a second time in sequence from the same
machine address.
(23)[000008d2][00011204][00000000](03) 83c408 add esp,+08
(24)[000008d5][00011204][00000000](03) 8945fc mov [ebp-04],eax
(25)[000008d8][00011204][00000000](03) 8b45fc mov eax,[ebp-04]
(26)[000008db][00011200][00000000](01) 50 push eax
(27)[000008dc][000111fc][0000030b](05) 680b030000 push 0000030b
(28)[000008e1][000111f8][000008e6](05) e869faffff call 0000034f
Input_Would_Halt = 0
(29)[000008e6][00011204][00000000](03) 83c408 add esp,+08
(30)[000008e9][00011204][00000000](02) 33c0 xor eax,eax
(31)[000008eb][00011208][00000000](02) 8be5 mov esp,ebp
(32)[000008ed][0001120c][00010000](01) 5d pop ebp
(33)[000008ee][00011210][00000080](01) c3 ret
Number_of_User_Instructions(33)
Copyright 2021 PL Olcott
[1] sci.logic --- Daryl McCullough --- Jun 25, 2004, 6:30:39 PM
[The Psychology of Self-Reference]
https://groups.google.com/g/sci.logic/c/4kIXI1kxmsI/m/hRroMoQZx2IJ
http://www.liarparadox.org/Eliminating_pathological_self_reference_error_from_the_halting_problem.pdf
olcott
Mar 13, 2021, 9:18:43 AM3/13/21
to
On 3/13/2021 6:18 AM, Andy Walker wrote:
> On 13/03/2021 02:10, olcott wrote:
>> When Halts is asked:
>> Does H_Hat halt on its input?
>> This is analogous to the question posed to Jack.
>> (1) There is no possible correct answer Halts can provide.
>> (2) There is a possible correct answer from other functions besides
>> Halts.
>
> Well done! But you fail to draw the obvious conclusion.
> From (1), and despite its name, "Halts" is not in fact a correct > halt decider. Since we know nothing else of relevance about
> "Halts", we can say the same about any program that purports to
> be a halt decider. In other words, there are no fully-correct
> halt deciders, QED. This /is/ the "standard" HP proof, which
> you have just reproduced [in essence] rather than refuted.
> Your (2) shows that this is a problem with "Halts", not
> with the question being posed, just as your "Jack" question is
> a problem for Jack, not for everyone. Just as most people have
> no idea what Jack will do but a few may know, most programs have
> no idea what "H_Hat" will do but some may know [but they had
> better not be claimed to be fully-correct halt deciders].
>
Jack is asked: Will your answer to this question be no?
If Jack says no and bill says Jack will say no,
Jack is wrong and Bill is right.
If Jack says yes and Bill says Jack will say Yes,
Jack is wrong and Bill is right.
When-so-ever (for whatever reason) we have a yes/no (technically polar)
question such that neither yes or no are the correct answer we have an
incorrect question.
Will H_Hat() halt on its input? is an incorrect question for Halts()
because (just like Jack) both yes and no are the wrong answer.
Would H_Hat() halt if the halt decider never stopped simulating it?
Is the same question with the contradiction removed.
Whenever any question defined such that both answers of yes and are
contradicted the question is incorrect.
Whenever decision problem input is defined such that both decisions of
true and false are contradicted we have an incorrect decision
problem/input instance.
Whenever a new idea about an old problem is presented learned-by-rote
people reject this new idea entirely on the basis that it does not
conform to what they learned-by-rote. This is an utterly foolish thing
to do.
If an idea is to be rejected then the only legitimate basis to reject
this idea is to find an error in it. Learned-by-rote people will still
believe that they found the error in that it does not conform to what
they learned by rote. Ben is a learned-by-rote person.
> On 13/03/2021 02:10, olcott wrote:
>> When Halts is asked:
>> Does H_Hat halt on its input?
>> This is analogous to the question posed to Jack.
>> (1) There is no possible correct answer Halts can provide.
>> (2) There is a possible correct answer from other functions besides
>> Halts.
>
> Well done! But you fail to draw the obvious conclusion.
> From (1), and despite its name, "Halts" is not in fact a correct > halt decider. Since we know nothing else of relevance about
> "Halts", we can say the same about any program that purports to
> be a halt decider. In other words, there are no fully-correct
> halt deciders, QED. This /is/ the "standard" HP proof, which
> you have just reproduced [in essence] rather than refuted.
> Your (2) shows that this is a problem with "Halts", not
> with the question being posed, just as your "Jack" question is
> a problem for Jack, not for everyone. Just as most people have
> no idea what Jack will do but a few may know, most programs have
> no idea what "H_Hat" will do but some may know [but they had
> better not be claimed to be fully-correct halt deciders].
>
Jack is asked: Will your answer to this question be no?
If Jack says no and bill says Jack will say no,
Jack is wrong and Bill is right.
If Jack says yes and Bill says Jack will say Yes,
Jack is wrong and Bill is right.
When-so-ever (for whatever reason) we have a yes/no (technically polar)
question such that neither yes or no are the correct answer we have an
incorrect question.
Will H_Hat() halt on its input? is an incorrect question for Halts()
because (just like Jack) both yes and no are the wrong answer.
Would H_Hat() halt if the halt decider never stopped simulating it?
Is the same question with the contradiction removed.
Whenever any question defined such that both answers of yes and are
contradicted the question is incorrect.
Whenever decision problem input is defined such that both decisions of
true and false are contradicted we have an incorrect decision
problem/input instance.
Whenever a new idea about an old problem is presented learned-by-rote
people reject this new idea entirely on the basis that it does not
conform to what they learned-by-rote. This is an utterly foolish thing
to do.
If an idea is to be rejected then the only legitimate basis to reject
this idea is to find an error in it. Learned-by-rote people will still
believe that they found the error in that it does not conform to what
they learned by rote. Ben is a learned-by-rote person.
olcott
Mar 13, 2021, 9:24:08 AM3/13/21
to
wij
Mar 13, 2021, 11:49:35 AM3/13/21
to
refer to as an error is also incorrect.
Let S be a set of all non-halting programs. The ones that fit 'self-reference'
are just a small subset of S.
How you decide x is an element of S without simulating x is the problem.
In this respect, your decider algorithm is still incomplele at most.
Your posts are becoming annoying.
olcott
Mar 13, 2021, 3:39:44 PM3/13/21
to
link you will see that it provides a 100% complete basis for Halts() to
correctly decide that H_Hat() would not halt.
olcott
Mar 13, 2021, 3:49:49 PM3/13/21
to
On 3/13/2021 10:49 AM, wij wrote:
Does the input program halt on its input?
It is possible to define an input that does the opposite of whatever the
halt decider decides.
When the halting problem criteria is:
Would the input program halt if the halt decider never stopped
simulating it?
Then any input that does the opposite of whatever the halt decider
decides becomes decidable.
The halt decider stops simulating this input on the basis that it is
calling the halt decider in what would otherwise be infinite recursion
then the halt decider reports that the input would not halt.
> Let S be a set of all non-halting programs. The ones that fit 'self-reference'
> are just a small subset of S.
> How you decide x is an element of S without simulating x is the problem.
> In this respect, your decider algorithm is still incomplele at most.
>
> Your posts are becoming annoying.
>
olcott
Mar 13, 2021, 4:52:10 PM3/13/21
to
On 3/13/2021 3:38 PM, Malcolm McLean wrote:
> OK, so we call H_Hat(H_Hat). It calls H, which detects what would be infinite
> recursion (because of the way H is written), and returns "no", this won't halt
> unless I halt it. So H_Hat doesn't go into the infinite loop, and halts.
>
> Now we call H(H_Hat, H_Hat). Same thing happens. H simulates H_Hat, causing
> an endless recursion, which H eventually terminates. So H returns "no": , this
> won't halt unless I halt it".
>
> But H has got it wrong. You've got to somehow flag that the H-directed halt in
> H_Hat doesn't count.
>
>
No not true. The global halt decider is called on main() so both
instances are correctly terminated because of what would otherwise be
infinite recursion.
When the halt decider is based on adapting a UTM then nothing can slip
past the analysis of the halt decider.
> recursion (because of the way H is written), and returns "no", this won't halt
> unless I halt it. So H_Hat doesn't go into the infinite loop, and halts.
>
> Now we call H(H_Hat, H_Hat). Same thing happens. H simulates H_Hat, causing
> an endless recursion, which H eventually terminates. So H returns "no": , this
> won't halt unless I halt it".
>
> But H has got it wrong. You've got to somehow flag that the H-directed halt in
> H_Hat doesn't count.
>
>
No not true. The global halt decider is called on main() so both
instances are correctly terminated because of what would otherwise be
infinite recursion.
When the halt decider is based on adapting a UTM then nothing can slip
past the analysis of the halt decider.
olcott
Mar 13, 2021, 5:09:32 PM3/13/21
to
On 3/13/2021 4:00 PM, Malcolm McLean wrote:
> RIght, so the supervisor is placed outside of H, and it is this which decides the
> halting / would not halt unless halted status of the program.
When the Halt decider is based on a UTM then the halt decider is the
supervisor of every computation.
>>
>> When the halt decider is based on adapting a UTM then nothing can slip
>> past the analysis of the halt decider.
>>
> You can't solve the halting problem this way, e.g. determine the halting
> status of a famous unknown problem. However you can pick up tight loops
> or simple infinite recursion.
>
The "do the opposite of whatever the halt decider decides" of the
conventional proofs becomes decidable, they are decided as would not halt.
> halting / would not halt unless halted status of the program.
When the Halt decider is based on a UTM then the halt decider is the
supervisor of every computation.
>>
>> When the halt decider is based on adapting a UTM then nothing can slip
>> past the analysis of the halt decider.
>>
> status of a famous unknown problem. However you can pick up tight loops
> or simple infinite recursion.
>
The "do the opposite of whatever the halt decider decides" of the
conventional proofs becomes decidable, they are decided as would not halt.
olcott
Mar 14, 2021, 10:55:18 AM3/14/21
to
On 3/14/2021 5:29 AM, Malcolm McLean wrote:
> On Sunday, 14 March 2021 at 02:07:06 UTC, Richard Damon wrote:
>> things as a 'supervisor'.
>>
> You can write a near-UTM, which steps through the test machine, and has
> some loop detction logic to detect if it gets stuck.Then it breaks out
> of the loop and reports "non-halting". That's a reasonable approach to
> writing a decider which might even be practically useful, as most programming
> errors which cause hangs put the program into a tight loop.
> You can scale it up to detect more complex looping behaviour. But you will
> soon get into a mess of complexity. It can't detect all non-halting machines.
>
> However PO has added another step, which is that the supervisor runs
> "main".
>>
>> THe UTM will be a self-contained computation, which apparently you plan
>> to modify to make it a Halt Decider. That Halt Decider now becomes a
>> fully self-contained computation, which gets modified when H^ is built.
>> Nothing in H gets to be 'outside' H^, H^ is based on the TOTAL
>> computation of H.
>>
> That's how Linz specified the problem. That's not how PO has laid out his
> system. In order to get round Linz's proof you have to change Linz's system
> somehow, as PO acknowledges. The solution he has chosen, based on
> what he has said recently, is to wrap main() in a supervisor.
>
We are not wrapping main() in a supervisor exactly.
More accurately the x86utm operating system is the master UTM that
applies its system level halt decider to every user computation.
The program under test:H_Hat() and the tester:Halts() are distinctly
different computations. It is the conflation of these two that creates
the pathological self-reference error.
The teacher does not share the students grade.
When the halt decider determines that the simulation of its input must
be aborted to prevent its infinite execution the input <is> a
non-halting computation. As Ben pointed out its ridiculous to construe
that a computation is a halting computation if the only reason that it
halts is that its exection was aborted.
> On Sunday, 14 March 2021 at 02:07:06 UTC, Richard Damon wrote:
>> On 3/13/21 5:05 PM, olcott wrote:
>>>>
>>>
>>> When the Halt decider is based on a UTM then the halt decider is the
>>> supervisor of every computation.
>> Nonsense. In a Turing Machine Model of computation there is no such
>>>>
>>>
>>> When the Halt decider is based on a UTM then the halt decider is the
>>> supervisor of every computation.
>> things as a 'supervisor'.
>>
> You can write a near-UTM, which steps through the test machine, and has
> some loop detction logic to detect if it gets stuck.Then it breaks out
> of the loop and reports "non-halting". That's a reasonable approach to
> writing a decider which might even be practically useful, as most programming
> errors which cause hangs put the program into a tight loop.
> You can scale it up to detect more complex looping behaviour. But you will
> soon get into a mess of complexity. It can't detect all non-halting machines.
>
> However PO has added another step, which is that the supervisor runs
> "main".
>>
>> THe UTM will be a self-contained computation, which apparently you plan
>> to modify to make it a Halt Decider. That Halt Decider now becomes a
>> fully self-contained computation, which gets modified when H^ is built.
>> Nothing in H gets to be 'outside' H^, H^ is based on the TOTAL
>> computation of H.
>>
> That's how Linz specified the problem. That's not how PO has laid out his
> system. In order to get round Linz's proof you have to change Linz's system
> somehow, as PO acknowledges. The solution he has chosen, based on
> what he has said recently, is to wrap main() in a supervisor.
>
We are not wrapping main() in a supervisor exactly.
More accurately the x86utm operating system is the master UTM that
applies its system level halt decider to every user computation.
The program under test:H_Hat() and the tester:Halts() are distinctly
different computations. It is the conflation of these two that creates
the pathological self-reference error.
The teacher does not share the students grade.
When the halt decider determines that the simulation of its input must
be aborted to prevent its infinite execution the input <is> a
non-halting computation. As Ben pointed out its ridiculous to construe
that a computation is a halting computation if the only reason that it
halts is that its exection was aborted.
olcott
Mar 14, 2021, 2:18:10 PM3/14/21
to
On 3/14/2021 11:34 AM, Kaz Kylheku wrote:
> On 2021-03-14, olcott <polc...@gmail.com> wrote:
>> There is no correct yes/no value that any decider can ever return to an
>> input that does the opposite of whatever the decider decides.
>>
>> You know this I know this so I don't understand why you lie about this.
>
> The decider is a function. H_Hat is a specific input, so Halts(H_Hat,
> H_Hat) returns exactly one value, just like Add(1, 3). It cannot
> return any other value. The opposite of that value is the correct one.
>
On Ben's excellent suggestion I have superseded all of this reasoning
and simply concluded that if the only reason an input program halts is
that its execution was aborted by the halt decider then this input
program <is> a non-halting computation.
On 3/13/2021 8:26 PM, Ben Bacarisse wrote:
> If you really could detect those computations would not
> halt if not stopped, you'd have a conventional halt decider
> and you should be boasting about that, not hiding your light
> under a "redefining the criterion" bushel.
>
The linked paper shows exactly how an at least partial halt decider
> really could detect those computations** would not halt if not stopped,
** The conventional halting problem undecidability proof counter-examples
http://www.liarparadox.org/Halting_problem_undecidability_and_infinite_recursion.pdf
> On 2021-03-14, olcott <polc...@gmail.com> wrote:
>> There is no correct yes/no value that any decider can ever return to an
>> input that does the opposite of whatever the decider decides.
>>
>> You know this I know this so I don't understand why you lie about this.
>
> The decider is a function. H_Hat is a specific input, so Halts(H_Hat,
> H_Hat) returns exactly one value, just like Add(1, 3). It cannot
> return any other value. The opposite of that value is the correct one.
>
On Ben's excellent suggestion I have superseded all of this reasoning
and simply concluded that if the only reason an input program halts is
that its execution was aborted by the halt decider then this input
program <is> a non-halting computation.
On 3/13/2021 8:26 PM, Ben Bacarisse wrote:
> If you really could detect those computations would not
> halt if not stopped, you'd have a conventional halt decider
> and you should be boasting about that, not hiding your light
> under a "redefining the criterion" bushel.
>
The linked paper shows exactly how an at least partial halt decider
> really could detect those computations** would not halt if not stopped,
** The conventional halting problem undecidability proof counter-examples
http://www.liarparadox.org/Halting_problem_undecidability_and_infinite_recursion.pdf
olcott
Mar 15, 2021, 10:09:57 AM3/15/21
to
On 3/15/2021 8:38 AM, Andy Walker wrote:
> On 15/03/2021 02:30, Chris M. Thomasson wrote:
>> On 3/14/2021 7:20 PM, olcott wrote:
>>> This proves that I am correct [...].
>>> Thanks to Ben and Kaz this is all that is needed.
>> If you smash your forehead in with a sledge hammer, will you halt?
>
> I'm slightly ashamed to admit that when PO /did/ halt, there
> was a short period of relief, but after a month or so I started to
> miss the regular banter. I assume that no-one, not even PO, really
> thinks that any progress is being made, or will ever be made, so it's
> just a matter of observing PO and his entourage winding each other up.
> What would be perfect would be if each member of the entourage could
> restrict themselves to one posting per day. That would give us about
> a dozen articles per day as light relief, rather than getting on for
> 100 [which means I have to zap lots of them unread].
>
Any bloody idiot can continue to parrot:
You are wrong, you are wrong,
I know that you are wrong because
I really really believe that you are wrong.
I dare you or anyone else to find a single significant error
(that changes the outcome) in any of this:
> On 15/03/2021 02:30, Chris M. Thomasson wrote:
>> On 3/14/2021 7:20 PM, olcott wrote:
>>> This proves that I am correct [...].
>>> Thanks to Ben and Kaz this is all that is needed.
>> If you smash your forehead in with a sledge hammer, will you halt?
>
> I'm slightly ashamed to admit that when PO /did/ halt, there
> was a short period of relief, but after a month or so I started to
> miss the regular banter. I assume that no-one, not even PO, really
> thinks that any progress is being made, or will ever be made, so it's
> just a matter of observing PO and his entourage winding each other up.
> What would be perfect would be if each member of the entourage could
> restrict themselves to one posting per day. That would give us about
> a dozen articles per day as light relief, rather than getting on for
> 100 [which means I have to zap lots of them unread].
>
Any bloody idiot can continue to parrot:
You are wrong, you are wrong,
I know that you are wrong because
I really really believe that you are wrong.
I dare you or anyone else to find a single significant error
(that changes the outcome) in any of this:
olcott
Mar 15, 2021, 10:45:11 AM3/15/21
to
On 3/15/2021 9:22 AM, Alan Mackenzie wrote:
> theorems, ones which have stood the test of time. Having grasped those
> theorems, there is no great need for me to investigate any further into
> where you are mistaken. Several people have, nevertheless, done this for
> you. You haven't been showing much gratitude.
> time on that? I know full well that 2 + 2 = 4.
>
I show that there is a gap in the reasoning of these proofs that make
their "do the opposite of whatever the halt decider decides" decidable.
They are decidable on the basis they they specify infinite recursion to
every (at least partial) halt decider that bases its decision on
examining the execution trace of its own simulation of these inputs.
void H_Hat(u32 P)
{
u32 Input_Would_Halt = Halts(P, P);
// When Halts() simulates H_Hat() then H_Hat() specifies
// infinite recursion when it is executed with itself as input.
if (Input_Would_Halt)
HERE: goto HERE;
}
int main()
{
u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
Output("Input_Would_Halt = ", Input_Would_Halt);
}
http://www.liarparadox.org/Halting_problem_undecidability_and_infinite_recursion.pdf
> olcott <No...@nowhere.com> wrote:
>
>> Any bloody idiot can continue to parrot:
>> You are wrong, you are wrong,
>
> You are wrong, Peter Olcott.
>
>> Any bloody idiot can continue to parrot:
>> You are wrong, you are wrong,
>
>
>> I know that you are wrong because
>> I really really believe that you are wrong.
>
> No. You are wrong because you refuse to accept proven mathematical
>> I know that you are wrong because
>> I really really believe that you are wrong.
>
> theorems, ones which have stood the test of time. Having grasped those
> theorems, there is no great need for me to investigate any further into
> where you are mistaken. Several people have, nevertheless, done this for
> you. You haven't been showing much gratitude.
>
>> I dare you or anyone else to find a single significant error
>> (that changes the outcome) in any of this:
>
>> http://www.liarparadox.org/Halting_problem_undecidability_and_infinite_recursion.pdf
>
> That's your paper that "proves" 2 + 2 = 5, is it? Why should I waste my
>> I dare you or anyone else to find a single significant error
>> (that changes the outcome) in any of this:
>
>> http://www.liarparadox.org/Halting_problem_undecidability_and_infinite_recursion.pdf
>
> time on that? I know full well that 2 + 2 = 4.
>
I show that there is a gap in the reasoning of these proofs that make
their "do the opposite of whatever the halt decider decides" decidable.
They are decidable on the basis they they specify infinite recursion to
every (at least partial) halt decider that bases its decision on
examining the execution trace of its own simulation of these inputs.
void H_Hat(u32 P)
{
u32 Input_Would_Halt = Halts(P, P);
// infinite recursion when it is executed with itself as input.
if (Input_Would_Halt)
HERE: goto HERE;
}
int main()
{
u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
Output("Input_Would_Halt = ", Input_Would_Halt);
}
olcott
Mar 15, 2021, 11:12:12 AM3/15/21
to
On 3/15/2021 9:55 AM, David Brown wrote:
> Note - please /stop/ posting this stuff in unrelated groups such as
> c.l.c and c.l.c++.
> out that the halting problem cannot be solved.
> <https://en.wikipedia.org/wiki/Halting_problem> and find a single
> significant error in that. If there is no error in Turing's proof that
> the halting problem cannot be solved, then there is no need to look at
> your work to know it is wrong. (Looking at it to find /what/ is wrong
> might still be instructive.)
>
> But just for fun, I did have a look at your link. Your first mistake is
> in your first sentence - "The simplest way to define a halt decider is
> to make a program that runs its input to see what it does". You can't
> make such a program. If you could, the halting problem would be
> trivially solvable. You can't start your "proof" by assuming the thing
> you want to proof - that's begging the question, or a circular argument.
> (You can suppose it is true in order to derive a contradiction, to
> prove the hypothesis is false - but that's not what you are trying to do
> here.)
>
> You then continue to assume the existence of the impossible halt decider
> program.
>
> The nearest you get to saying something correct is to talk about a "(at
> least partial) halt decider". You don't define your terms (a common
> mistake amongst people who don't know how to write a proof), but
> certainly it is trivially possible to define a function that /sometimes/
> determines if a function halts. The only impossible bit is to make such
> a function that is /not/ "partial" - that works for any function, and
> any input.
>
> Your idea seems to be that "Halts" will look at a trace and see if a
> function (possibly "Halts" itself - your document is not clear) is
> called twice from the same address without there being a conditional
> jump in between. If so, it will conclude that the function will be
> "infinitely recursive" and not halt. Otherwise the function will halt.
> Is that correct?
>
>
> There are major flaws in this argument.
>
> First, there is no requirement for a an infinite recursion in order for
> a function not to halt. An infinite loop will be a non-halting system.
> (Loops are equivalent to a limited form of recursion in computation
> theory, but for some incomprehensible reason you are using x86 machine
> code instead of simpler computation models. There are a large numbers
> of ways of causing an infinite loop in x86, without recursion or
> conditional branches.)
>
> Secondly, your algorithm does not detect all infinite recursion.
> Conditional branches are no guarantee that the recursion is not infinite.
Now we construct a new Turing machine D with H as a
subroutine. This new TM calls H to determine what M
does when the input to M is its own description <M>.
Once D has determined this information, it does the
opposite. That is, it rejects if M accepts and accepts
if M does not accept. (Sipser 1997:165)
Sipser, Michael 1997. Introduction to the Theory of Computation. Boston:
PWS Publishing Company (165-167)
All that I have done is conclusively prove that the
"do the opposite of whatever halt decider decides"
basis of the conventional halting problem proofs does
not actually prove halting problem undecidability.
> Note - please /stop/ posting this stuff in unrelated groups such as
> c.l.c and c.l.c++.
>
> On 15/03/2021 15:09, olcott wrote:
>> On 3/15/2021 8:38 AM, Andy Walker wrote:
>>> On 15/03/2021 02:30, Chris M. Thomasson wrote:
>>>> On 3/14/2021 7:20 PM, olcott wrote:
>>>>> This proves that I am correct [...].
>>>>> Thanks to Ben and Kaz this is all that is needed.
>>>> If you smash your forehead in with a sledge hammer, will you halt?
>>>
>>> I'm slightly ashamed to admit that when PO /did/ halt, there
>>> was a short period of relief, but after a month or so I started to
>>> miss the regular banter. I assume that no-one, not even PO, really
>>> thinks that any progress is being made, or will ever be made, so it's
>>> just a matter of observing PO and his entourage winding each other up.
>>> What would be perfect would be if each member of the entourage could
>>> restrict themselves to one posting per day. That would give us about
>>> a dozen articles per day as light relief, rather than getting on for
>>> 100 [which means I have to zap lots of them unread].
>>>
>>
>> Any bloody idiot can continue to parrot:
>> You are wrong, you are wrong,
>> I know that you are wrong because
>> I really really believe that you are wrong.
>
> That is basically what /you/ have been saying to the people who figured
> On 15/03/2021 15:09, olcott wrote:
>> On 3/15/2021 8:38 AM, Andy Walker wrote:
>>> On 15/03/2021 02:30, Chris M. Thomasson wrote:
>>>> On 3/14/2021 7:20 PM, olcott wrote:
>>>>> This proves that I am correct [...].
>>>>> Thanks to Ben and Kaz this is all that is needed.
>>>> If you smash your forehead in with a sledge hammer, will you halt?
>>>
>>> I'm slightly ashamed to admit that when PO /did/ halt, there
>>> was a short period of relief, but after a month or so I started to
>>> miss the regular banter. I assume that no-one, not even PO, really
>>> thinks that any progress is being made, or will ever be made, so it's
>>> just a matter of observing PO and his entourage winding each other up.
>>> What would be perfect would be if each member of the entourage could
>>> restrict themselves to one posting per day. That would give us about
>>> a dozen articles per day as light relief, rather than getting on for
>>> 100 [which means I have to zap lots of them unread].
>>>
>>
>> Any bloody idiot can continue to parrot:
>> You are wrong, you are wrong,
>> I know that you are wrong because
>> I really really believe that you are wrong.
>
> out that the halting problem cannot be solved.
>
>>
>> I dare you or anyone else to find a single significant error
>> (that changes the outcome) in any of this:
>>
>> http://www.liarparadox.org/Halting_problem_undecidability_and_infinite_recursion.pdf
>>
>
> I dare you to look at the rough proof at
>>
>> I dare you or anyone else to find a single significant error
>> (that changes the outcome) in any of this:
>>
>> http://www.liarparadox.org/Halting_problem_undecidability_and_infinite_recursion.pdf
>>
>
> <https://en.wikipedia.org/wiki/Halting_problem> and find a single
> significant error in that. If there is no error in Turing's proof that
> the halting problem cannot be solved, then there is no need to look at
> your work to know it is wrong. (Looking at it to find /what/ is wrong
> might still be instructive.)
>
> But just for fun, I did have a look at your link. Your first mistake is
> in your first sentence - "The simplest way to define a halt decider is
> to make a program that runs its input to see what it does". You can't
> make such a program. If you could, the halting problem would be
> trivially solvable. You can't start your "proof" by assuming the thing
> you want to proof - that's begging the question, or a circular argument.
> (You can suppose it is true in order to derive a contradiction, to
> prove the hypothesis is false - but that's not what you are trying to do
> here.)
>
> You then continue to assume the existence of the impossible halt decider
> program.
>
> The nearest you get to saying something correct is to talk about a "(at
> least partial) halt decider". You don't define your terms (a common
> mistake amongst people who don't know how to write a proof), but
> certainly it is trivially possible to define a function that /sometimes/
> determines if a function halts. The only impossible bit is to make such
> a function that is /not/ "partial" - that works for any function, and
> any input.
>
> Your idea seems to be that "Halts" will look at a trace and see if a
> function (possibly "Halts" itself - your document is not clear) is
> called twice from the same address without there being a conditional
> jump in between. If so, it will conclude that the function will be
> "infinitely recursive" and not halt. Otherwise the function will halt.
> Is that correct?
>
>
> There are major flaws in this argument.
>
> First, there is no requirement for a an infinite recursion in order for
> a function not to halt. An infinite loop will be a non-halting system.
> (Loops are equivalent to a limited form of recursion in computation
> theory, but for some incomprehensible reason you are using x86 machine
> code instead of simpler computation models. There are a large numbers
> of ways of causing an infinite loop in x86, without recursion or
> conditional branches.)
>
> Secondly, your algorithm does not detect all infinite recursion.
> Conditional branches are no guarantee that the recursion is not infinite.
Now we construct a new Turing machine D with H as a
subroutine. This new TM calls H to determine what M
does when the input to M is its own description <M>.
Once D has determined this information, it does the
opposite. That is, it rejects if M accepts and accepts
if M does not accept. (Sipser 1997:165)
Sipser, Michael 1997. Introduction to the Theory of Computation. Boston:
PWS Publishing Company (165-167)
All that I have done is conclusively prove that the
"do the opposite of whatever halt decider decides"
basis of the conventional halting problem proofs does
not actually prove halting problem undecidability.
Bonita Montero
Mar 15, 2021, 12:59:28 PM3/15/21
to
Can you please stop talking to yourself here ?
Post to comp.theory only ! The only NG where your stuff fits.
Post to comp.theory only ! The only NG where your stuff fits.
olcott
Mar 15, 2021, 4:21:07 PM3/15/21
to
On 3/15/2021 2:51 PM, Chris M. Thomasson wrote:
> On 3/14/2021 8:27 PM, R Kym Horsell wrote:
>> Ben Bacarisse <ben.u...@bsb.me.uk> wrote:
>>> olcott <No...@NoWhere.com> writes:
>>>> These are my own (self-evidently correct) words:
>>>> Any computation based on finite string transformation rules is Turing
>>>> computable.
>>> Not self-evidently correct. You even give a counter example:
>>>> The fact that the case where a computation examines a finite string to
>>>> determine whether or not that finite string represents a computation
>>>> that would halt on its input <is> a finite string transformation
>>>> computation. The input string is transformed into "1" or "0".
>>> Well done.
>>
>>
>> How is it some people have an apparent infinite capacity to listen to a
>> stream of nonsense without choking on vomit?
>>
>
> Humm.... Good point! Damn. Perhaps they think there is hope? ;^o
If you simply assume that I am wrong you will not see that I am correct.
I updated these two pages of the textbook proofs:
http://www.liarparadox.org/sipser_165.pdf
http://www.liarparadox.org/kozen_233.pdf
to YELLOW HIGHLIGHT the portions that show the key basis of both of
these proofs is defining an input to the halt decider that:
point out why it does not:
void H_Hat(u32 P)
{
u32 Input_Would_Halt = Halts(P, P);
if (Input_Would_Halt)
HERE: goto HERE;
}
int main()
{
u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
Output("Input_Would_Halt = ", Input_Would_Halt);
}
Then I provide the complete execution trace of the x86 machine language
of the above code:
http://www.liarparadox.org/Halting_problem_undecidability_and_infinite_recursion.pdf
Showing exactly <how> this halting status of the above code is correctly
decided as infinitely recursive. No one can point to any error.
Any bloody idiot can play the role of a mindless naysayer, even a bot
can do this. No one can point to any error in any of the above BECAUSE
THERE IS NO ERROR!
> On 3/14/2021 8:27 PM, R Kym Horsell wrote:
>> Ben Bacarisse <ben.u...@bsb.me.uk> wrote:
>>> olcott <No...@NoWhere.com> writes:
>>>> These are my own (self-evidently correct) words:
>>>> Any computation based on finite string transformation rules is Turing
>>>> computable.
>>> Not self-evidently correct. You even give a counter example:
>>>> The fact that the case where a computation examines a finite string to
>>>> determine whether or not that finite string represents a computation
>>>> that would halt on its input <is> a finite string transformation
>>>> computation. The input string is transformed into "1" or "0".
>>> Well done.
>>
>>
>> How is it some people have an apparent infinite capacity to listen to a
>> stream of nonsense without choking on vomit?
>>
>
> Humm.... Good point! Damn. Perhaps they think there is hope? ;^o
If you simply assume that I am wrong you will not see that I am correct.
I updated these two pages of the textbook proofs:
http://www.liarparadox.org/sipser_165.pdf
http://www.liarparadox.org/kozen_233.pdf
to YELLOW HIGHLIGHT the portions that show the key basis of both of
these proofs is defining an input to the halt decider that:
"does the opposite of whatever the halt decider decides"
The following does correctly encode this same key basis and no one can
point out why it does not:
void H_Hat(u32 P)
{
u32 Input_Would_Halt = Halts(P, P);
if (Input_Would_Halt)
HERE: goto HERE;
}
int main()
{
u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
Output("Input_Would_Halt = ", Input_Would_Halt);
}
of the above code:
http://www.liarparadox.org/Halting_problem_undecidability_and_infinite_recursion.pdf
Showing exactly <how> this halting status of the above code is correctly
decided as infinitely recursive. No one can point to any error.
Any bloody idiot can play the role of a mindless naysayer, even a bot
can do this. No one can point to any error in any of the above BECAUSE
THERE IS NO ERROR!
0 new messages