Debug trace of Halts() deciding halting on H_Hat() ---Halts returns a value to main()

[olcott]

If you have a good understanding of:
(a) software engineering,
(b) The C programming language
(c) The x86 programming language

You will be able to easily verify that Halts() does correctly decide the
halt status of H_Hat().

The x86utm operating system provides the operating environment to
execute virtual machines computationally equivalent to universal Turing
machines having the x86 language as their machine description language.
x86utm executes the COFF object file output of the Microsoft C compiler.
The x86utm operating system is based on a world class x86 emulator that
has been developed and tested for decades.

x86 language ≡ von Neumann architecture ≡ UTM ≡ RASP Machine
It is common knowledge that all x86 based programs are computationally
equivalent to UTMs for every computation that does not require more
memory than they have.

This is the generic halt deciding criteria:
On Saturday, November 28, 2020 at 2:00:28 PM UTC-8, olcott wrote:
> Every computation that would not halt if its simulation
> were not halted is by logical necessity a non-halting computation.

We can verify that the following execution trace of the computational
equivalent of:
(a) {Peter Linz: H, Michael Sipser: H, Dexter Kozen: K}
Correctly decides halting on the the computational equivalent of:
(b) {Peter Linz: Ĥ, Michael Sipser: D, Dexter Kozen: N}

The following execution trace can be verified as correctly deciding the
halting status of its input with only these three prerequisites and
nothing more:

(a) An elementary understanding of software engineering, such things as:
(a) infinite loops do not have a fixed number of iterations and (b)
infinitely recursive invocations never return any value to their caller.

(b) A basic understanding of how the C programming language maps to x86
instructions. This is used to verify that the translations of the "C"
functions into their x86 equivalents are correct. It is also used to
verifiy that the execution trace of these x86 functions is correct.

(c) An understanding of one very elementary infinite recursion detection
algorithm: Whenever an execution trace shows a second call to the same
function from the same machine address with no control flow instructions
in-between this second invocation is always an instance of infinite
recursion. From this it is very easy to see that the halt decider did
apply this simple criteria in its halt deciding decision, thus meeting
he generic criteria shown above.

Actual debug trace of Halts() deciding halting on H_Hat()

#define HALT __asm hlt

void H_Hat(u32 P)
{
u32 Input_Halts = Halts(P, P);
if (Input_Halts)
HERE: goto HERE;
else
HALT
}

int main()
{
u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
Output_Debug_Trace();
Output("Input_Would_Halt =", Input_Would_Halt);
HALT;
}

_H_Hat()
[000005e6](01) 55 push ebp
[000005e7](02) 8bec mov ebp,esp
[000005e9](01) 51 push ecx
[000005ea](03) 8b4508 mov eax,[ebp+08]
[000005ed](01) 50 push eax
[000005ee](03) 8b4d08 mov ecx,[ebp+08]
[000005f1](01) 51 push ecx
[000005f2](05) e8effdffff call 000003e6
[000005f7](03) 83c408 add esp,+08
[000005fa](03) 8945fc mov [ebp-04],eax
[000005fd](04) 837dfc00 cmp dword [ebp-04],+00
[00000601](02) 7404 jz 00000607
[00000603](02) ebfe jmp 00000603
[00000605](02) eb01 jmp 00000608
[00000607](01) f4 hlt
[00000608](02) 8be5 mov esp,ebp
[0000060a](01) 5d pop ebp
[0000060b](01) c3 ret

_main()
[00000616](01) 55 push ebp
[00000617](02) 8bec mov ebp,esp
[00000619](01) 51 push ecx
[0000061a](05) 68e6050000 push 000005e6
[0000061f](05) 68e6050000 push 000005e6
[00000624](05) e8bdfdffff call 000003e6
[00000629](03) 83c408 add esp,+08
[0000062c](03) 8945fc mov [ebp-04],eax
[0000062f](05) e8f2fcffff call 00000326
[00000634](03) 8b45fc mov eax,[ebp-04]
[00000637](01) 50 push eax
[00000638](05) 68a3020000 push 000002a3
[0000063d](05) e894fcffff call 000002d6
[00000642](03) 83c408 add esp,+08
[00000645](01) f4 hlt
[00000646](02) 8be5 mov esp,ebp
[00000648](01) 5d pop ebp
[00000649](01) c3 ret

Output_Debug_Trace() Trace_List.size(24)
---[00000616](01) 55 push ebp
---[00000617](02) 8bec mov ebp,esp
---[00000619](01) 51 push ecx
---[0000061a](05) 68e6050000 push 000005e6
---[0000061f](05) 68e6050000 push 000005e6
---[00000624](05) e8bdfdffff call 000003e6 --CALL [000003e6]
---[000005e6](01) 55 push ebp
---[000005e7](02) 8bec mov ebp,esp
---[000005e9](01) 51 push ecx
---[000005ea](03) 8b4508 mov eax,[ebp+08]
---[000005ed](01) 50 push eax
---[000005ee](03) 8b4d08 mov ecx,[ebp+08]
---[000005f1](01) 51 push ecx
---[000005f2](05) e8effdffff call 000003e6 --CALL [000003e6]
---[000005e6](01) 55 push ebp
---[000005e7](02) 8bec mov ebp,esp
---[000005e9](01) 51 push ecx
---[000005ea](03) 8b4508 mov eax,[ebp+08]
---[000005ed](01) 50 push eax
---[000005ee](03) 8b4d08 mov ecx,[ebp+08]
---[000005f1](01) 51 push ecx
---[000005f2](05) e8effdffff call 000003e6 --CALL [000003e6]
Input Aborted because of INFINITE RECURSION from [000005f2] to [000003e6]
---[00000629](03) 83c408 add esp,+08
---[0000062c](03) 8945fc mov [ebp-04],eax
===[0000062f](05) e8f2fcffff call 00000326
...[00000634](03) 8b45fc mov eax,[ebp-04]
...[00000637](01) 50 push eax
...[00000638](05) 68a3020000 push 000002a3
===[0000063d](05) e894fcffff call 000002d6
Input_Would_Halt = 0
...[00000642](03) 83c408 add esp,+08
...[00000645](01) f4 hlt

Every time that the same function is called from the same machine
address a second time without any control flow instructions in-between
is a case of infinite recursion.
This is shown at execution trace lines 14-22 above.

http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf

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

http://www.liarparadox.org/sipser_165.pdf

Sipser, Michael 1997. Introduction to the Theory of Computation. Boston:
PWS Publishing Company (165-167)

http://www.liarparadox.org/kozen_233.pdf

The Kozen computation is identical to the Peter Linz computation merely
swapping function names Linz.H is swapped for Kozen.K and Linz.Ĥ is
swapped for Kozen.N

Kozen, Dexter 1997. Automata and Computability. New York:
Springer-Verlag. (231-234).



--
Copyright 2020 Pete Olcott

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

[Rick C. Hodgin]

On 12/16/20 4:27 PM, olcott wrote:
> #define HALT __asm hlt
>
> void H_Hat(u32 P)
> {
>   u32 Input_Halts = Halts(P, P);
>   if (Input_Halts)
>     HERE: goto HERE;

This terminating spin-loop will sit there and consume power and generate
heat as fast as possible and unnecessarily. You'd be better off to
write it as:

if (Input_Halts)
{
HERE:
HALT;
goto HERE;
}

The HLT instruction causes the CPU to wait for an external interrupt to
signal before proceeding. It slows down the spin-loop, consuming less
power, and generating less heat.

BTW, using HLT in your main kernel OS code when you've exhausted every
current task that's demanding CPU time for this time slice can reduce
your CPU's idle temperature down to about 22C in my experience.

HLT is one of the most under-utilized instructions IMO. Especially in
scheduler code because the clock will signal an interrupt when the next
test of anything that needs to fire off at a specific time is ready to go.

>   else
>     HALT
> }

Philosophy is important in understanding what's going on inside a CPU,
and especially when you get into multi-thread / multi-core programming.

You are on a good path IMO. Keep going.

--
Rick C. Hodgin

[Mr Flibble]

On 16/12/2020 21:27, olcott wrote:

> (a) An elementary understanding of software engineering, such things as: (a) infinite loops do not have a fixed number of iterations and (b) infinitely recursive invocations never return any value to their caller.

However to refute Turing and "solve" the Halting Problem any halt decider has to consider loops and recursions that contain conditionals (i.e. branching logic) which your "solution" doesn't.

You still have failed to add anything of substance regarding the Halting Problem due to your bloody minded obsession with corner case "counter examples" in some "proofs" that nobody cares about.

/Flibble

--
😎

[Kaz Kylheku]

On 2020-12-16, Rick C. Hodgin <rick.c...@gmail.com> wrote:
> On 12/16/20 4:27 PM, olcott wrote:
>> #define HALT __asm hlt
>>
>> void H_Hat(u32 P)
>> {
>>   u32 Input_Halts = Halts(P, P);
>>   if (Input_Halts)
>>     HERE: goto HERE;
>
> This terminating spin-loop will sit there and consume power and generate
> heat as fast as possible and unnecessarily. You'd be better off to
> write it as:
>
> if (Input_Halts)
> {
> HERE:
> HALT;
> goto HERE;
> }
>
> The HLT instruction causes the CPU to wait for an external interrupt to
> signal before proceeding. It slows down the spin-loop, consuming less
> power, and generating less heat.

Peter Olcott has redefined the halt instruction in his emulator
framework to perform a final halt. (As "THe The Halting Problem"
definition of "halt" not "wait in a power-efficient way until an
interrupt occcurs" definition.)

> BTW, using HLT in your main kernel OS code when you've exhausted every
> current task that's demanding CPU time for this time slice can reduce
> your CPU's idle temperature down to about 22C in my experience.

The usual OS 101 trick is to implement a scheduler in which at least one
task is always runnable. When there is nothing else to do, an idle task
is executed. That idle task does this:

for (;;)
relax(); // macro that calls HALT on x86 or whatever

There is no reason for the HALT instruction to appear anywhere
else in the system.

If there are muliple cores, each one gets its own instance of this idle
task, pinned to that core.

--
TXR Programming Language: http://nongnu.org/txr

[Juha Nieminen]

In comp.lang.c++ olcott <No...@nowhere.com> wrote:
> (c) The x86 programming language

There's no such a thing as "the x86 programming language". For someone who
pretends to be academic you don't seem to care much about using correct
terminology.

x86 is a CPU architecture, not a programming language. This CPU architecture
supports a particular machine code, which can be written in an assembly
language, using the Intel syntax or the AT&T syntax (and, possibly, a few
other more obscure variants).

The closest thing to what you meant would probably be "the x86 assembly
language".

Anyway, this is a newsgroup about C++, not about computing science.
Your posts are off-topic here.

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

It's the archetypal sign of a pseudoscientist to quote Einstein (often
with a misquote) to try to justify his wacky conjectures.

[Jorgen Grahn]

On Thu, 2020-12-17, Juha Nieminen wrote:
...

>> "Great spirits have always encountered violent opposition from mediocre
>> minds." Einstein
>
> It's the archetypal sign of a pseudoscientist to quote Einstein (often
> with a misquote) to try to justify his wacky conjectures.

/Please/ resist the urge to respond to crap like this. /You/ know
he's a crank, /I/ know it, /he/ has surely been told for years (by
people with "mediocre minds") -- no need to give him a free ticket
past everyone's killfile [1].

/Jorgen

[1] This is probably a mixed metaphor, but I like it :-)

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .

[Keith Thompson]

Jorgen Grahn <grahn...@snipabacken.se> writes:
> On Thu, 2020-12-17, Juha Nieminen wrote:
> ...
>>> "Great spirits have always encountered violent opposition from mediocre
>>> minds." Einstein
>>
>> It's the archetypal sign of a pseudoscientist to quote Einstein (often
>> with a misquote) to try to justify his wacky conjectures.
>
> /Please/ resist the urge to respond to crap like this. /You/ know
> he's a crank, /I/ know it, /he/ has surely been told for years (by
> people with "mediocre minds") -- no need to give him a free ticket
> past everyone's killfile [1].

[...]

Agreed. And if you feel the need to respond, he's pretty much taken
over comp.theory. He does have a bad habit of cross-posting to other
newsgroups, so be sure to edit your Newsgroups: line as needed.

--
Keith Thompson (The_Other_Keith) Keith.S.T...@gmail.com
Working, but not speaking, for Philips Healthcare
void Void(void) { Void(); } /* The recursive call of the void */

[olcott]

On 12/17/2020 3:10 PM, Jorgen Grahn wrote:
> On Thu, 2020-12-17, Juha Nieminen wrote:
> ...
>>> "Great spirits have always encountered violent opposition from mediocre
>>> minds." Einstein
>>
>> It's the archetypal sign of a pseudoscientist to quote Einstein (often
>> with a misquote) to try to justify his wacky conjectures.
>
> /Please/ resist the urge to respond to crap like this. /You/ know
> he's a crank, /I/ know it, /he/ has surely been told for years (by
> people with "mediocre minds") -- no need to give him a free ticket
> past everyone's killfile [1].
>
> /Jorgen
>
> [1] This is probably a mixed metaphor, but I like it :-)
>

I only cross-post the most significant developments and I always put the
follow-up to comp.theory.

--
Copyright 2020 Pete Olcott

[Mike Terry]

On 17/12/2020 21:10, Jorgen Grahn wrote:
> On Thu, 2020-12-17, Juha Nieminen wrote:
> ...
>>> "Great spirits have always encountered violent opposition from mediocre
>>> minds." Einstein
>>
>> It's the archetypal sign of a pseudoscientist to quote Einstein (often
>> with a misquote) to try to justify his wacky conjectures.
>
> /Please/ resist the urge to respond to crap like this. /You/ know
> he's a crank, /I/ know it, /he/ has surely been told for years (by
> people with "mediocre minds") -- no need to give him a free ticket
> past everyone's killfile [1].
>
> /Jorgen
>
> [1] This is probably a mixed metaphor, but I like it :-)
>

Maybe "ignore subthread" would be a good option for people wanting to
ignore PO's posts and ALSO any responses to PO's posts. (It works well
for me, in certain other newsgroups.)

Mike.