Re: Correcting the definition of the halting problem --- Computable functions ---HHH(DD)

On 3/25/2025 2:27 PM, olcott wrote:

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

On 3/25/2025 1:18 PM, olcott wrote:

On 3/25/2025 12:04 PM, dbush wrote:

On 3/25/2025 12:56 PM, olcott wrote:

On 3/25/2025 11:46 AM, dbush wrote:

On 3/25/2025 12:40 PM, olcott wrote:

On 3/25/2025 10:17 AM, dbush wrote:

On 3/25/2025 11:13 AM, olcott wrote:

On 3/25/2025 10:02 AM, dbush wrote:

On 3/25/2025 10:53 AM, olcott wrote:

On 3/25/2025 9:45 AM, dbush wrote:

On 3/24/2025 11:29 PM, olcott wrote:

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

>
False.  The mathematical function that counts the number of instructions in a turing machine is computable.
>

>
It is impossible for an actual Turing machine to
be input to any other TM.
>

>
But a description of a turing machine can be, for example in the form of source code or a binary.  And a turing machine by definition *always* behaves the same for a given input when executing directly.

>
IT IS COUNTER-FACTUAL THAT A MACHINE DESCRIPTION ALWAYS
SPECIFIES
BEHAVIOR IDENTICAL TO THE DIRECTLY EXECUTED MACHINE.
>
_III()
[00002172] 55         push ebp      ; housekeeping
[00002173] 8bec       mov  ebp,esp  ; housekeeping
[00002175] 6872210000 push 00002172 ; push III
[0000217a] e853f4ffff call 000015d2 ; call EEE(III)
[0000217f] 83c404     add  esp,+04
[00002182] 5d         pop  ebp
[00002183] c3         ret
Size in bytes:(0018) [00002183]

>
That is not the complete description.  The complete description consists of the code of III

>
and the fact that EEE

>
Is called by III makes the code of EEE part of the fixed input, as well as everything that EEE calls down to the OS level.
>

>
Which is not relevant to whether or not III emulated
by EEE reaches its own final halt state.
>

>
Which is why III emulated by EEE is not relevant.
>

>
When the question is:
Does III emulated by EEE reach its final halt state
when III defines a pathological relationship with its emulator?
>

>
>
But that's not the question.  The question is whether or not an H exists that behaves as described below:
>

 Did you ever bother to notice the title of this thread?
 Turing machines are only capable operating on input
finite strings.

And those finite strings can be a complete description of a turing machine

Turing machine computable functions cannot
compute anything that their input doesn't specify.

Translation: algorithms only compute what they're programed to compute.
And the algorithm your EEE is computing is not the mathematical halting function, which has proven to not be computable:
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

 THEIR INPUT NEVER SPECIFIES THE ACTUAL BEHAVIOR OF ANY
OTHER TURING MACHINE
 

What a particular turing machine is able to compute doesn't change whether or not the input string fully describes another turing machine

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