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

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.

 

For example pure math functions don't have any specific
storage like a tape or machine registers.

>
No they don't. Why would they? A mathematical function is simply a static mapping from elements of a domain to elements of a codomain.
>

This also would seem to mean that they would require
some actual input.
>
>

The above copypasta doesn't address this.
>
I pointed out that the domain of a computable function needn't be a string. The above copypasta doesn't address this.
>

>
When implemented using an actual model of computation
some concrete form or input seems required.
>

I pointed out that there is no bijection natural numbers and strings,

>
finite strings of decimal digits: [0123456789]
>

but rather a one-to-many relation. The above copypasta doesn't address this.

>
"12579" would seem to have a bijective mapping to
a single natural number.

>
The natural number 12579 maps equally to the (decimal) string '012579', '0012579',... so there is no bijection.
>

 The bijection is then to decimal digits without leading zeroes to Natural numbers.
 

>
I pointed out that the exact same sort of one-to-many relation exists between computations and strings. The above copypasta doesn't address this.
>

>
I pointed out above that the finite string of x86
machine code correctly emulated by EEE DOES
NOT MAP TO THE BEHAVIOR OF ITS DIRECT EXECUTION.

>
But I was not talking about EEE. I was talking about the halting function. All you seem to be claiming above is that whatever EEE computes, it isn't the halting function. Everyone already agrees to that.
>
André
>

 The math halting function is free to "abstract away" key
details that change everything. That is why I have never
been talking about the pure math and have always been
referring to its implementation in a model of computation.
 

There are no details abstracted away.  The halting function is simply uncomputable.

A halt decider cannot exist

So again, you explicitly agree with the Linz proof and all other proofs of the halting function.

because the halting problem is defined incorrectly

There's nothing incorrect about wanting something that would solve the Goldbach conjecture and make unknowable truths knowable.  Your alternate definition won't provide that.
There's no requirement that a function be computable.