Re: Correcting the definition of the halting problem --- Computable functions

On 3/25/25 9:01 AM, olcott wrote:

On 3/25/2025 3:47 AM, joes wrote:

Am Mon, 24 Mar 2025 18:04:21 -0500 schrieb olcott:

On 3/24/2025 5:49 PM, André G. Isaak wrote:

On 2025-03-24 16:43, olcott wrote:
>

Computable functions don't have inputs. They have domains. Turing
machines have inputs.

Maybe when pure math objects. In every model of computation they seem
to always have inputs.

Computable functions *are* pure math objects. You seem to want to
conflate them with C functions, but that is not the case.
The crucial point is that the domains of computable functions are *not*
restricted to strings, even if the inputs to Turing Machines are.
>

While the inputs to TMs are restricted to strings, there is no such
such restriction on computable functions.
The vast majority of computable functions of interest do *not* have
strings as their domains, yet they remain computable functions (a
simple example would be the parity function which maps NATURAL
NUMBERS (not strings) to yes/no values.)

Since there is a bijection between natural numbers and strings of
decimal digits your qualification seems vacuous.

There is not a bijection between natural numbers and strings. There is
a one-to-many mapping from natural numbers to strings, just as there is
a one-to-many mapping from computations (i.e. turing machine/input
string pairs, i.e. actual Turing machines directly running on their
inputs) to strings.

>

When III is emulated by pure emulator EEE for any finite number of steps
of emulation according to the semantics of the x86 language it never
reaches its own "ret" instruction final halt state THUS DOES NOT HALT.
When III is directly executed calls an EEE instance that only emulates
finite number of steps then this directly executed III always reaches
its own "ret" instruction final halt state THUS HALTS.

 

A pure simulator can not limit the number of steps. Also III doesn't
halt in, say, 3 steps. Why should III call a different instance
that doesn't abort, when it is being simulated?
>

 The fact that the same states in the program-under-test
keep repeating such that the program-under-test cannot
possibly reach its own final halt state proves that
program-under-test does not halt.
 

What state in the PROGRAM repeated. The program goes into EEE and keeps on looping in EEE as it emulates the code of III then inton EEE as it emulates III then in to EEE as it emulates III.
THe state of the program never "repeats" as its state keeps on growing with more levels of emulation.
Now, it is true that if EEE is actually a correct emulator, this will go on forever, but the HHH that DDD calls can't do that and be a decider, and thus that HHH is not the same as EEE and thus we have a different input.
HHH doing only a partial emulation, and then returning 0, creates a DDD, that when complete emulated (say by our EEE above) will see that DDD calls HHH which will after a bit return to DDD and DDD will halt.
This emulation will begin IDENTICALLY to the trace generated by HHH, and then continue past that point, showing that HHH's emulation can NOT be seen as a proof of non-halting, since a halting emulation had that identical trace.