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

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.
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).

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.

>
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é
--
To email remove 'invalid' & replace 'gm' with well known Google mail service.