You CANNOT solve the halting problem through simulation as simulation
simply isn't practical: each branch DOUBLES the number of paths which
have to be analyzed and you soon get to a very large number of paths
with any non-trivial program that cannot be solved within the lifetime
of the universe by a classical computer.

/Flibble

--
This message is a troll.

On 11/12/21 9:50 AM, Mr Flibble wrote:
> You CANNOT solve the halting problem through simulation as simulation
> simply isn't practical: each branch DOUBLES the number of paths which
> have to be analyzed and you soon get to a very large number of paths
> with any non-trivial program that cannot be solved within the lifetime
> of the universe by a classical computer.
>
> /Flibble

That isn't quite true, as you aren't simulating just the program, but
the program with a specific input, so most branches you know which
branch you are going to make,

The problem you run into is when the program includes the ability to ask
the decider a question and that question ask the decider a question,
then you get into a valid recursive trap for the decider.

The second problem is that while there are some simple non-halting
patterns that can be detected, allowing some trivial cases of non-halted
to be detected, in real life, the cases you want to try to catch aren't
so simple.

For instance, A problem I just recently came on, find the second number,
if it exists where the sum of all the factors of the number (including
itself) divided by the number itself give exactly the value of 1.8.

The first number is 10. The second number if it exists sounds to be in
excess of a trillion, but they haven't been able to prove that such a
number doesn't exist.

Simple loop pattern matching is NOT going to be able to solve that
halting problem.

On 11/12/2021 8:50 AM, Mr Flibble wrote:
> You CANNOT solve the halting problem through simulation as simulation

My excellent carefully crafted reply simply didn't show up.
As I have told you many many times I am not trying to make an
omniscient (all-knowing) program that solves the halting problem.
I am only forming a correct rebuttal to the halting theorem:

#include <stdint.h>
typedef void (*ptr)();

int H(ptr x, ptr y)
{ x(y);
return 1;
}

// Minimal essence of Linz(1990) Ĥ
// and Strachey(1965) P
void P(ptr x)
{ H(x, x);
}

int main(void)
{ H(P, P);
}

It is obvious that whether or not the above code is directly executed or
H performs a pure simulation of its input that the above code specifies
infinite recursion.

If H simulates its input in debug step mode it can correctly abort the
simulation of this input as soon as H sees its simulated P call itself
with the same parameters that it was called with. When it does this it
correctly returns 0 for not halting.

Strachey, C 1965. An impossible program The Computer Journal, Volume 7,
Issue 4, January 1965, Page 313, https://doi.org/10.1093/comjnl/7.4.313

Linz, Peter 1990. An Introduction to Formal Languages and Automata.
Lexington/Toronto: D. C. Heath and Company. (318-320)

Halting problem undecidability and infinitely nested simulation (V2)
November 2021 PL Olcott

https://www.researchgate.net/publication/356105750_Halting_problem_undecidability_and_infinitely_nested_simulation_V2

> simply isn't practical: each branch DOUBLES the number of paths which
> have to be analyzed and you soon get to a very large number of paths
> with any non-trivial program that cannot be solved within the lifetime
> of the universe by a classical computer.
>
> /Flibble
>
> --
> This message is a troll.
>

--
Copyright 2021 Pete Olcott "Great spirits have always encountered
violent opposition from mediocre minds." Einstein

On Friday, 12 November 2021 at 15:37:01 UTC, richar...@gmail.com wrote:
>
> The second problem is that while there are some simple non-halting
> patterns that can be detected, allowing some trivial cases of non-halted
> to be detected, in real life, the cases you want to try to catch aren't
> so simple.
>
Depends what you are interested in. If you are interested in solving open
questions in mathematics, than a partial halt decider isn't likely to be
useful. However if you are interested in catching programming errors,
the trivial cases of non-halting behaviour might come up frequently
enough to be worth having a program which detects them. And a few false
"non-halting" calls might be acceptable.

On 11/12/2021 12:22 PM, Malcolm McLean wrote:
> On Friday, 12 November 2021 at 15:37:01 UTC, richar...@gmail.com wrote:
>>
>> The second problem is that while there are some simple non-halting
>> patterns that can be detected, allowing some trivial cases of non-halted
>> to be detected, in real life, the cases you want to try to catch aren't
>> so simple.
>>
> Depends what you are interested in. If you are interested in solving open
> questions in mathematics, than a partial halt decider isn't likely to be
> useful. However if you are interested in catching programming errors,
> the trivial cases of non-halting behaviour might come up frequently
> enough to be worth having a program which detects them. And a few false
> "non-halting" calls might be acceptable.
>

Giving credit where credit is due
Ben posted these very excellent improvements
to my initial syntax in comp.lang.c
On 11/11/2021 2:31 PM, Ben Bacarisse wrote:

#include <stdint.h>
typedef void (*ptr)();

int H(ptr x, ptr y)
{ x(y);
return 1;
}

// Minimal essence of Linz(1990) Ĥ
// and Strachey(1965) P (see below)
void P(ptr x)
{ H(x, x);
}

int main(void)
{ H(P, P);
}

It is obvious that the direct execution of the above code never halts
because it is infinitely recursive. It is equally obvious that when H
performs a correct pure simulation of its input (instead of directly
executing it) that its input never halts.

_P()
[00001a5e](01) 55 push ebp
[00001a5f](02) 8bec mov ebp,esp
[00001a61](03) 8b4508 mov eax,[ebp+08]
[00001a64](01) 50 push eax // push P
[00001a65](03) 8b4d08 mov ecx,[ebp+08]
[00001a68](01) 51 push ecx // push P
[00001a69](05) e810000000 call 00001a7e // call H
[00001a6e](03) 83c408 add esp,+08
[00001a71](01) 5d pop ebp
[00001a72](01) c3 ret
Size in bytes:(0021) [00001a72]

Because there is nothing that H can possibly do to cause or enable P to
reach its final state at 1a72 we correctly conclude that the input to
H(P,P) never halts.

--
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre
minds." Einstein

On 11/12/21 2:00 PM, olcott wrote:
> On 11/12/2021 12:22 PM, Malcolm McLean wrote:
>> On Friday, 12 November 2021 at 15:37:01 UTC, richar...@gmail.com wrote:
>>>
>>> The second problem is that while there are some simple non-halting
>>> patterns that can be detected, allowing some trivial cases of non-halted
>>> to be detected, in real life, the cases you want to try to catch aren't
>>> so simple.
>>>
>> Depends what you are interested in. If you are interested in solving open
>> questions in mathematics, than a partial halt decider isn't likely to be
>> useful. However if you are interested in catching programming errors,
>> the trivial cases of non-halting behaviour might come up frequently
>> enough to be worth having a program which detects them. And a few false
>> "non-halting" calls might be acceptable.
>>
>
> Giving credit where credit is due
> Ben posted these very excellent improvements
> to my initial syntax in comp.lang.c
> On 11/11/2021 2:31 PM, Ben Bacarisse wrote:
>
> #include <stdint.h>
> typedef void (*ptr)();
>
> int H(ptr x, ptr y)
> {
>   x(y);
>   return 1;
> }
>
> // Minimal essence of Linz(1990) Ĥ
> // and Strachey(1965) P (see below)
> void P(ptr x)
> {
>   H(x, x);
> }
>
> int main(void)
> {
>   H(P, P);
> }
>
> It is obvious that the direct execution of the above code never halts
> because it is infinitely recursive. It is equally obvious that when H
> performs a correct pure simulation of its input (instead of directly
> executing it) that its input never halts.

Right, IF H is just an uncoditional execution or simulation of its
input, then P(P) will be non-halting.

That has always been accepted.

>
> _P()
> [00001a5e](01)  55              push ebp
> [00001a5f](02)  8bec            mov ebp,esp
> [00001a61](03)  8b4508          mov eax,[ebp+08]
> [00001a64](01)  50              push eax        // push P
> [00001a65](03)  8b4d08          mov ecx,[ebp+08]
> [00001a68](01)  51              push ecx        // push P
> [00001a69](05)  e810000000      call 00001a7e   // call H
> [00001a6e](03)  83c408          add esp,+08
> [00001a71](01)  5d              pop ebp
> [00001a72](01)  c3              ret
> Size in bytes:(0021) [00001a72]
>
> Because there is nothing that H can possibly do to cause or enable P to
> reach its final state at 1a72 we correctly conclude that the input to
> H(P,P) never halts.
>

Except that your H from above never gives an answer so it isn't a
correct decider.

THis proves comclusively that a Halt Decider that unconditonally
simulates its input fails at the requirements to be a Halt decider.

Once you make H NOT be an uncodintional simulator/executer, then this
logic fails.

For instance, it is totally clear that a 'N step' simulator, that just
automatically decides its input halts after N steps if it didn't Halt,
will NOT result in an 'infinite recursion' as that function will only
execute N steps of the program and then return. You can't get an
infinite recursion in a finite number of steps.

Thus, your 'logic' is clearly false that 'Nothing' that H can do (if you
allow H to stop its simulation) keeps the routine non-halting.

Note, your failure is in part that you want H to SEE that P gets to the
final state, but that is NOT what the problem asks. The problem asks
about the independent execution of the computaition P(I).

Pershaps what you have shown is that it is impossible to build an H that
can PROVE, by simulating to the halting point, that its input reperesnts
a Halting machine.

That is different then the input represents a Halting Machine, it can
easily be one but H not being able to prove it. Stuff being non-provable
by a given method is not uncommon in math.

On 11/12/21 12:10 PM, olcott wrote:
> On 11/12/2021 8:50 AM, Mr Flibble wrote:
>> You CANNOT solve the halting problem through simulation as simulation
>
> My excellent carefully crafted reply simply didn't show up.
> As I have told you many many times I am not trying to make an
> omniscient (all-knowing) program that solves the halting problem.
> I am only forming a correct rebuttal to the halting theorem:
>
> #include <stdint.h>
> typedef void (*ptr)();
>
> int H(ptr x, ptr y)
> {
>   x(y);
>   return 1;
> }
>
> // Minimal essence of Linz(1990) Ĥ
> // and Strachey(1965) P
> void P(ptr x)
> {
>   H(x, x);
> }
>
> int main(void)
> {
>   H(P, P);
> }
>
> It is obvious that whether or not the above code is directly executed or
> H performs a pure simulation of its input that the above code specifies
> infinite recursion.
>
> If H simulates its input in debug step mode it can correctly abort the
> simulation of this input as soon as H sees its simulated P call itself
> with the same parameters that it was called with. When it does this it
> correctly returns 0 for not halting.

Nope. False premise.

The falseness is actually PROVEN by this case, if H does 'debug step'
its input and makes this decision and return non-halting, than we can
show that the actual exection of the program which the input is a
representation of will halt.

Sin=mple proof:

By your stipulation, H(P,P) will simulate its input for a finite number
of instructions, doing so in finite time N, and then return a value of 0.

That means that an actual trace of the execution of P(P) will have P do
what even initial operations it does to initialize itself, and then call
H(P,P). From the stipulation above, we KNOW that at at time N later, H
MUST be returning the value 0 to P, and P then Halts.

Thus P is halting.

I don't CARE what H does, knowing that it answers in finite time N is
enough to prove that P(P) is finite in execution, and that H is WRONG to
say that its input represents a non-halting operation.

Yes, you can show that H never sees that halting itself, but that is
irrelevant to the problem at hand, as halting refers to the behavior of
tha actual machine, not the partial simulation done by the decider.

>
>
> Strachey, C 1965.  An impossible program The Computer Journal, Volume 7,
> Issue 4, January 1965, Page 313, https://doi.org/10.1093/comjnl/7.4.313
>
> Linz, Peter 1990. An Introduction to Formal Languages and Automata.
> Lexington/Toronto: D. C. Heath and Company. (318-320)
>
>
>
>
> Halting problem undecidability and infinitely nested simulation (V2)
> November 2021 PL Olcott
>
> https://www.researchgate.net/publication/356105750_Halting_problem_undecidability_and_infinitely_nested_simulation_V2
>
>
>> simply isn't practical: each branch DOUBLES the number of paths which
>> have to be analyzed and you soon get to a very large number of paths
>> with any non-trivial program that cannot be solved within the lifetime
>> of the universe by a classical computer.
>>
>> /Flibble
>>
>> --
>> This message is a troll.
>>
>
>

On 11/12/2021 8:50 AM, Mr Flibble wrote:
> You CANNOT solve the halting problem through simulation as simulation
> simply isn't practical: each branch DOUBLES the number of paths which
> have to be analyzed and you soon get to a very large number of paths
> with any non-trivial program that cannot be solved within the lifetime
> of the universe by a classical computer.
>
> /Flibble
>
> --
> This message is a troll.
>

This is my latest refutation of the halting problem proof.

Halting problem undecidability and infinitely nested simulation (V3)

https://www.researchgate.net/publication/358009319_Halting_problem_undecidability_and_infinitely_nested_simulation_V3

--
Copyright 2021 Pete Olcott

Talent hits a target no one else can hit;
Genius hits a target no one else can see.
Arthur Schopenhauer

On 1/23/22 5:40 PM, olcott wrote:
> On 11/12/2021 8:50 AM, Mr Flibble wrote:
>> You CANNOT solve the halting problem through simulation as simulation
>> simply isn't practical: each branch DOUBLES the number of paths which
>> have to be analyzed and you soon get to a very large number of paths
>> with any non-trivial program that cannot be solved within the lifetime
>> of the universe by a classical computer.
>>
>> /Flibble
>>
>> --
>> This message is a troll.
>>
>
>
> This is my latest refutation of the halting problem proof.
>
> Halting problem undecidability and infinitely nested simulation (V3)
>
> https://www.researchgate.net/publication/358009319_Halting_problem_undecidability_and_infinitely_nested_simulation_V3
>
>

Which if you read this group you will see a number of flaws in this 'proof'.

It isn't worth the paper it is printed on.