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

On 2025-03-25 13:14:43 +0000, olcott said:

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 only report on the behavior that
their input finite string specifies.

Quite obviously. A decider reports only one thing - otherwise it is not a decider. If that one thing is not whether the described computation halts
then it is not a halt decider.
--
Mikko