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

Am Mon, 24 Mar 2025 17:43:14 -0500 schrieb olcott:

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

On 2025-03-24 14:11, olcott wrote:

On 3/24/2025 12:35 PM, dbush wrote:

On 3/24/2025 12:44 PM, olcott wrote:

On 3/24/2025 10:14 AM, dbush wrote:

On 3/24/2025 11:03 AM, olcott wrote:

On 3/24/2025 6:23 AM, Richard Damon wrote:

On 3/23/25 11:09 PM, olcott wrote:

It is impossible for HHH compute the function from the direct
execution of DDD because DDD is not the finite string input
basis from which all computations must begin.
https://en.wikipedia.org/wiki/Computable_function

WHy isn't DDD made into the correct finite string?i

DDD is a semantically and syntactically correct finite stirng of
the x86 machine language.

Which includes the machine code of DDD, the machine code of HHH,
and the machine code of everything it calls down to the OS level.
>
>

That seems to be your own fault.
The problem has always been that you want to use the wrong string
for DDD by excluding the code for HHH from it.

DDD emulated by HHH directly causes recursive emulation because it
calls HHH(DDD) to emulate itself again. HHH complies until HHH
determines that this cycle cannot possibly reach the final halt
state of DDD.

Which is another way of saying that HHH can't determine that DDD
halts when executed directly.

given an input of the function domain it can return the
corresponding output.
Computable functions are only allowed to compute the mapping from
their input finite strings to an output.

The HHH you implemented is computing *a* computable function, but
it's not computing the halting function:

The whole point of this post is to prove that no Turing machine ever
reports on the behavior of the direct execution of another Turing
machine.

UTMs do.

Given any algorithm (i.e. a fixed immutable sequence of instructions)
X described as <X> with input Y:
A solution to the halting problem is an algorithm H that computes the
following mapping:
(<X>,Y) maps to 1 if and only if X(Y) halts when executed directly

Cannot possibly be a computable function because computable functions
cannot possibly have directly executing Turing machines as their
inputs.

Whatever. It can still compute the direct execution from the description,
which is exactly what the described machine would do.

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.
 

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.
 

You really need to learn the difference between a Halt decider and the
halting function. They are distinct things.

A halting function need not be a decider?

No, *the* halting function is undecidable.

In any case no computable function within any model of computation
computes the mapping from the behavior of any other directly executing
process to anything else.

Simulators compute the mapping from a description to the directly
executed behaviour. That is computable.

*THIS MAKES THE FOLLOWING STATEMENT INCORRECT*
On 3/24/2025 12:35 PM, dbush wrote:
 > A solution to the halting problem is an algorithm H that computes the
 > following mapping:
 > (<X>,Y) maps to 1 if and only if X(Y)
 > halts when executed directly
 > (<X>,Y) maps to 0 if and only if X(Y)
 > does not halt when executed directly
A definition can be shown to be incorrect when it contradicts other
definitions in the same system.

And what does it contradict?

--
Am Sat, 20 Jul 2024 12:35:31 +0000 schrieb WM in sci.math:
It is not guaranteed that n+1 exists for every n.