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

On 2025-03-25 03:29:06 +0000, olcott said:

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.

 https://en.wikipedia.org/wiki/Computable_function
 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>

There are computable functions that take Turing machines as arguments.
For example, the number of states of a Turing machine.
The computability of a function requires that the domain can be mapped
to finite strings.
--
Mikko