info
Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Could H correctly decide that P never halts?
7 views
Skip to first unread message
olcott
Jul 3, 2021, 11:19:30 AM7/3/21
to
*Halting problem undecidability and infinitely nested simulation*
When the halt decider bases its halt status decision simulating its
input then the conventional halting problem proof undecidability
counter-example templates can be correctly decided as inputs that never
halt. They will never halt because they specify infinitely nested
simulation to any simulating halt decider.
Because a simulating halt decider must always abort the simulation of
every input that never halts its halt deciding criteria must be adapted.
[ Does the input halt on its input? ] must become [ Does the input halt
without having its simulation aborted? ] This change is required because
every input to a simulating halt decider either halts on its own or
halts because its simulation has been aborted.
The standard pseudo-code halting problem template "proved" that the
halting problem could never be solved on the basis that neither value of
true (halting) nor false (not halting) could be correctly returned to
the confounding input.
// Simplified Linz Ĥ (Linz:1990:319)
void P(u32 x)
{
u32 Input_Halts = H(x, x);
if (Input_Halts)
HERE: goto HERE;
}
int main()
{
u32 Input_Halts = H((u32)P, (u32)P);
Output("Input_Halts = ", Input_Halts);
}
This problem is overcome on the basis that a simulating halt decider
would abort the simulation of its input before ever returning any value
to this input. It aborts the simulation of its input on the basis that
its input specifies what is essentially infinite recursion (infinitely
nested simulation) to any simulating halt decider.
The x86utm operating system was created so that the halting problem
could be examined concretely in the high level language of C and x86.
When examining the halting problem this way every detail can be
explicitly specified. UTM tape elements are 32-bit unsigned integers.
H analyzes the (currently updated) stored execution trace of its x86
emulation of P(P) after it simulates each instruction of input (P, P).
As soon as a non-halting behavior pattern is matched H aborts the
simulation of its input and decides that its input does not halt.
*This is the sound deductive inference (proof) that H(P,P)==0 is correct*
Premise(1) (axiom) Every computation that never halts unless its
simulation is aborted is a computation that never halts. This verified
as true on the basis of the meaning of its words.
Premise(2) (verified fact) The simulation of the input to H(P,P) never
halts without being aborted is a verified fact on the basis of its x86
execution trace. (shown below).
When the simulator determines whether or not it must abort the
simulation of its input based on the behavior of its input the simulator
only acts as an x86 emulator thus has no effect on the behavior of its
input. This allows the simulator to always ignore its own behavior.
Conclusion(3) From the above true premises it necessarily follows that
simulating halt decider H correctly reports that its input: (P,P) never
halts.
Halting problem undecidability and infinitely nested simulation
https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
When the halt decider bases its halt status decision simulating its
input then the conventional halting problem proof undecidability
counter-example templates can be correctly decided as inputs that never
halt. They will never halt because they specify infinitely nested
simulation to any simulating halt decider.
Because a simulating halt decider must always abort the simulation of
every input that never halts its halt deciding criteria must be adapted.
[ Does the input halt on its input? ] must become [ Does the input halt
without having its simulation aborted? ] This change is required because
every input to a simulating halt decider either halts on its own or
halts because its simulation has been aborted.
The standard pseudo-code halting problem template "proved" that the
halting problem could never be solved on the basis that neither value of
true (halting) nor false (not halting) could be correctly returned to
the confounding input.
// Simplified Linz Ĥ (Linz:1990:319)
void P(u32 x)
{
u32 Input_Halts = H(x, x);
if (Input_Halts)
HERE: goto HERE;
}
int main()
{
u32 Input_Halts = H((u32)P, (u32)P);
Output("Input_Halts = ", Input_Halts);
}
This problem is overcome on the basis that a simulating halt decider
would abort the simulation of its input before ever returning any value
to this input. It aborts the simulation of its input on the basis that
its input specifies what is essentially infinite recursion (infinitely
nested simulation) to any simulating halt decider.
The x86utm operating system was created so that the halting problem
could be examined concretely in the high level language of C and x86.
When examining the halting problem this way every detail can be
explicitly specified. UTM tape elements are 32-bit unsigned integers.
H analyzes the (currently updated) stored execution trace of its x86
emulation of P(P) after it simulates each instruction of input (P, P).
As soon as a non-halting behavior pattern is matched H aborts the
simulation of its input and decides that its input does not halt.
*This is the sound deductive inference (proof) that H(P,P)==0 is correct*
Premise(1) (axiom) Every computation that never halts unless its
simulation is aborted is a computation that never halts. This verified
as true on the basis of the meaning of its words.
Premise(2) (verified fact) The simulation of the input to H(P,P) never
halts without being aborted is a verified fact on the basis of its x86
execution trace. (shown below).
When the simulator determines whether or not it must abort the
simulation of its input based on the behavior of its input the simulator
only acts as an x86 emulator thus has no effect on the behavior of its
input. This allows the simulator to always ignore its own behavior.
Conclusion(3) From the above true premises it necessarily follows that
simulating halt decider H correctly reports that its input: (P,P) never
halts.
Halting problem undecidability and infinitely nested simulation
https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
olcott
Jul 3, 2021, 12:20:02 PM7/3/21
to
On 7/3/2021 10:56 AM, Richard Damon wrote:
> On 7/3/21 11:32 AM, olcott wrote:
>> On 7/3/2021 10:25 AM, wij wrote:
>>>
>>> In computability theory, the halting problem is the problem of
>>> determining, from a description of an arbitrary computer program and
>>> an input, whether the program will finish running, or continue to run
>>> forever. Alan Turing proved in 1936 that a general algorithm to solve
>>> the halting problem for all possible program-input pairs cannot exist.
>>> https://en.wikipedia.org/wiki/Halting_problem
>>>
>>
>> There is a huge gap in the reasoning of the halting problem proofs.
>> All of the conventional halting problem proofs simply assume that H
>> must return the correct halt status of P(P) to P. None of these
>> proofs considered the possibility that a simulating halt decider
>> would be required to abort its input before ever returning any value
>> to this input.
>>
>
> But what does aborting the simulation have to do with returning the
> answer to the caller. THEY ARE DIFFERENT.
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
The simulating halt decider H must abort the simulation of its input in
the computation H(P,P) before returning any value to P.
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
> You don't seem to be able to understand the fundamental Software
> Engineering concept of execution context.
>
> After H aborts the simulation, it needs to do something. By its
> requriements, it needs to return that answer to its caller.
>
H does return a value of 0 to main(). H does not return any value to the
simulated P that calls H in infinitely nested simulation.
> When it does, it tells that caller that it thinks that P(P) is
> non-Halting, but when it does that to the caller P, that P then halts,
> showing that the answer it gave was wrong.
> as a machine with the given input. It is shown that P(P) does Halt (and
> you admit this at times) thus P(P) IS a HALTING computation, by definition.
>
That definition simply ignores simulating halt deciders. The fatal
mistake of the halting problem proofs is they simply ignoring simulating
halt deciders.
> The non-Halting answer is wrong, by definition.
>
The non-halting answer is correct the definition must be adapted.
> Any 'logic' that 'proves' otherwise is by definition wrong or at least
> shows the logic is inconsistent.
>
According to your incorrect reasoning a simulating halt decider must
always report true because all of its inputs either halt own their own
or are aborted.
Because people that are not dumber than a box of rocks do understand
that computations that only halt because they were aborted are
computations that never halt there is agreement that your reasoning is
incorrect.
Ben and Kaz both agree. that computations that only halt because their
simulation was aborted are non-halting computations.
> On 7/3/21 11:32 AM, olcott wrote:
>> On 7/3/2021 10:25 AM, wij wrote:
>>>
>>> In computability theory, the halting problem is the problem of
>>> determining, from a description of an arbitrary computer program and
>>> an input, whether the program will finish running, or continue to run
>>> forever. Alan Turing proved in 1936 that a general algorithm to solve
>>> the halting problem for all possible program-input pairs cannot exist.
>>> https://en.wikipedia.org/wiki/Halting_problem
>>>
>>
>> There is a huge gap in the reasoning of the halting problem proofs.
>> All of the conventional halting problem proofs simply assume that H
>> must return the correct halt status of P(P) to P. None of these
>> proofs considered the possibility that a simulating halt decider
>> would be required to abort its input before ever returning any value
>> to this input.
>>
>
> But what does aborting the simulation have to do with returning the
> answer to the caller. THEY ARE DIFFERENT.
>
void P(u32 x)
{
u32 Input_Halts = H(x, x);
if (Input_Halts)
HERE: goto HERE;
}
int main()
{
u32 Input_Halts = H((u32)P, (u32)P);
Output("Input_Halts = ", Input_Halts);
}
When the called is calling H in infinitely nested simulation
void P(u32 x)
{
u32 Input_Halts = H(x, x);
if (Input_Halts)
HERE: goto HERE;
}
int main()
{
u32 Input_Halts = H((u32)P, (u32)P);
Output("Input_Halts = ", Input_Halts);
}
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
The simulating halt decider H must abort the simulation of its input in
the computation H(P,P) before returning any value to P.
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
IN THE ABOVE C COMPUTATION NOT ANY OTHER COMPUTATION
> You don't seem to be able to understand the fundamental Software
> Engineering concept of execution context.
>
> After H aborts the simulation, it needs to do something. By its
> requriements, it needs to return that answer to its caller.
>
H does return a value of 0 to main(). H does not return any value to the
simulated P that calls H in infinitely nested simulation.
> When it does, it tells that caller that it thinks that P(P) is
> non-Halting, but when it does that to the caller P, that P then halts,
> showing that the answer it gave was wrong.
>
Because a simulating halt decider must always abort the simulation of
every input that never halts its halt deciding criteria must be adapted.
Does the input halt on its input?
must become
Does the input halt without having its simulation aborted?
This change is required because every input to a simulating halt decider
either halts on its own or halts because its simulation has been aborted.
> The FUNDAMENTAL definition of Halting is what the machine does when run
Because a simulating halt decider must always abort the simulation of
every input that never halts its halt deciding criteria must be adapted.
Does the input halt on its input?
must become
Does the input halt without having its simulation aborted?
This change is required because every input to a simulating halt decider
either halts on its own or halts because its simulation has been aborted.
> as a machine with the given input. It is shown that P(P) does Halt (and
> you admit this at times) thus P(P) IS a HALTING computation, by definition.
>
That definition simply ignores simulating halt deciders. The fatal
mistake of the halting problem proofs is they simply ignoring simulating
halt deciders.
> The non-Halting answer is wrong, by definition.
>
The non-halting answer is correct the definition must be adapted.
> Any 'logic' that 'proves' otherwise is by definition wrong or at least
> shows the logic is inconsistent.
>
According to your incorrect reasoning a simulating halt decider must
always report true because all of its inputs either halt own their own
or are aborted.
Because people that are not dumber than a box of rocks do understand
that computations that only halt because they were aborted are
computations that never halt there is agreement that your reasoning is
incorrect.
Ben and Kaz both agree. that computations that only halt because their
simulation was aborted are non-halting computations.
Bonita Montero
Jul 3, 2021, 12:28:42 PM7/3/21
to
You are off-topic in comp.lang.c/c++.
Nothing what you say is especially related to C or C++.
Stop posting here.
Nothing what you say is especially related to C or C++.
Stop posting here.
olcott
Jul 3, 2021, 12:52:11 PM7/3/21
to
The first 8 pages of my paper are only about software engineering in C.
Halting problem undecidability and infinitely nested simulation
https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation
Bonita Montero
Jul 3, 2021, 1:18:50 PM7/3/21
to
> It is 100% totally related to software engineering in C.
It's related to programming in general.
So you shouldn't post in groups related to specific languages.
olcott
Jul 3, 2021, 1:20:10 PM7/3/21
to
language. The C source code is provided.
Bonita Montero
Jul 3, 2021, 1:33:18 PM7/3/21
to
>>> It is 100% totally related to software engineering in C.
>> It's related to programming in general.
>> So you shouldn't post in groups related to specific languages.
> It is a specific software engineering problem in the C programming
> language. The C source code is provided.
You don't don't discuss any C/C++-specific issues.
>> It's related to programming in general.
>> So you shouldn't post in groups related to specific languages.
> It is a specific software engineering problem in the C programming
> language. The C source code is provided.
comp.theory is the only NG that fits.
Stop posting in comp.lang.c/c++.
You're a off-topic-terrorist.
Siri Cruise
Jul 3, 2021, 2:01:32 PM7/3/21
to
In article <hKudnUFx1oVw4n39...@giganews.com>,
produce a counterexample that halt on a counterexample or do not
halt if the conjecture is true. Assume the halting problem is
decidable, then the conjecture can be decided. But this
contradicts Goedel that number theory has undecidable statements.
Therefore the halting problem is undecidable.
p is prime: P = \p, k. [
k*k>p -> true;
k*k<=p and p mod k = 0 -> false;
k*k<=p and p mod k /= 0 -> P(p, k+1)
]
goldbach conjecture counterexample: E = \n, i, j. [
~P(i, 2) and i<n and j<n -> E(n, i+1, j);
~P(j, 2) and i<n and j<n -> E(n, 2, j+1);
i>=n and j<n -> E(n, 2, j+1);
i>=n and j>=n -> n;
P(i, 2) and P(j, 2) and i<n and j<n and i+j=n -> E(n+2, 2, 2);
P(i, 2) and P(j, 2) and i<n and j<n and i+j/=n -> E(n, i+1, j)
]
goldbach conjecture: G = \.E(4, 2, 2)
Prove G halts.
ob-langc
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
typedef long long unsigned Integer;
static bool P (Integer p) {
Integer k = 2;
for (; k*k<=p; ++k) if (p%k==0) return false;
return true;
}
static void G (void) {
Integer n = 4, i = 2, j = 2;
for (; ;)
if (i>=n && j>=n) {
printf("%llu counterexample\n", n);
return;
}else if (i>=n) i = 2, ++j;
else if (!P(i)) ++i;
else if (!P(j)) i = 2, ++j;
else if (i+j!=n) ++i;
else {
printf("%llu = %llu+%llu\n", n, i, j);
n += 2; i = j = 2;
}
}
int main (int argc, char **argv) {
G(); return 0;
}
--
:-<> Siri Seal of Disavowal #000-001. Disavowed. Denied. Deleted. @
'I desire mercy, not sacrifice.' /|\
Discordia: not just a religion but also a parody. This post / \
I am an Andrea Doria sockpuppet. insults Islam. Mohammed
olcott <No...@NoWhere.com> wrote:
> Conclusion(3) From the above true premises it necessarily follows that
> simulating halt decider H correctly reports that its input: (P,P) never
> halts.
Number theory conjectures can be written as Turing Machines to
> Conclusion(3) From the above true premises it necessarily follows that
> simulating halt decider H correctly reports that its input: (P,P) never
> halts.
produce a counterexample that halt on a counterexample or do not
halt if the conjecture is true. Assume the halting problem is
decidable, then the conjecture can be decided. But this
contradicts Goedel that number theory has undecidable statements.
Therefore the halting problem is undecidable.
p is prime: P = \p, k. [
k*k>p -> true;
k*k<=p and p mod k = 0 -> false;
k*k<=p and p mod k /= 0 -> P(p, k+1)
]
goldbach conjecture counterexample: E = \n, i, j. [
~P(i, 2) and i<n and j<n -> E(n, i+1, j);
~P(j, 2) and i<n and j<n -> E(n, 2, j+1);
i>=n and j<n -> E(n, 2, j+1);
i>=n and j>=n -> n;
P(i, 2) and P(j, 2) and i<n and j<n and i+j=n -> E(n+2, 2, 2);
P(i, 2) and P(j, 2) and i<n and j<n and i+j/=n -> E(n, i+1, j)
]
goldbach conjecture: G = \.E(4, 2, 2)
Prove G halts.
ob-langc
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
typedef long long unsigned Integer;
static bool P (Integer p) {
Integer k = 2;
for (; k*k<=p; ++k) if (p%k==0) return false;
return true;
}
static void G (void) {
Integer n = 4, i = 2, j = 2;
for (; ;)
if (i>=n && j>=n) {
printf("%llu counterexample\n", n);
return;
}else if (i>=n) i = 2, ++j;
else if (!P(i)) ++i;
else if (!P(j)) i = 2, ++j;
else if (i+j!=n) ++i;
else {
printf("%llu = %llu+%llu\n", n, i, j);
n += 2; i = j = 2;
}
}
int main (int argc, char **argv) {
G(); return 0;
}
--
:-<> Siri Seal of Disavowal #000-001. Disavowed. Denied. Deleted. @
'I desire mercy, not sacrifice.' /|\
Discordia: not just a religion but also a parody. This post / \
I am an Andrea Doria sockpuppet. insults Islam. Mohammed
olcott
Jul 3, 2021, 2:15:23 PM7/3/21
to
that we know that both {Yes and No} are the wrong answer. The Goldbach
conjecture is undecided and not undecidable.
0 new messages