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

On 3/25/2025 9:14 AM, olcott wrote:

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

Am Mon, 24 Mar 2025 22:29:06 -0500 schrieb olcott:

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

On 3/24/2025 10:07 PM, olcott wrote:

On 3/24/2025 8:46 PM, André G. Isaak wrote:

On 2025-03-24 19:33, olcott wrote:

On 3/24/2025 7:00 PM, André G. Isaak wrote:

>

In the post you were responding to I pointed out that computable
functions are mathematical objects.

Computable functions implemented using models of computation would
seem to be more concrete than pure math functions.

Those are called computations or algorithms, not computable
functions.

https://en.wikipedia.org/wiki/Pure_function Is another way to look at
computable functions implemented by some concrete model of
computation.

And not all mathematical functions are computable, such as the halting
function.

>

The halting problems asks whether there *is* an algorithm which can
compute the halting function, but the halting function itself is a
purely mathematical object which exists prior to, and independent of,
any such algorithm (if one existed).

None-the-less it only has specific elements of its domain as its
entire basis. For Turing machines this always means a finite string
that (for example) encodes a specific sequence of moves.

False.  *All* turing machine are the domain of the halting function,
and the existence of UTMs show that all turning machines can be
described by a finite string.

You just aren't paying enough attention. Turing machines are never in
the domain of any computable function. <snip>

 

Fine, their descriptions are, and their behaviour is computable -
by running them.
>

 Halt deciders

Don't exist, because no H satisfies this requirement:
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
(<X>,Y) maps to 0 if and only if X(Y) does not halt when executed directly