On 3/24/2025 12:35 PM, dbush wrote:
On 3/24/2025 12:44 PM, olcott wrote:
On 3/24/2025 10:14 AM, dbush wrote:
On 3/24/2025 11:03 AM, olcott wrote:
On 3/24/2025 6:23 AM, Richard Damon wrote:
On 3/23/25 11:09 PM, olcott wrote:
It is impossible for HHH compute the function from the direct
execution of DDD because DDD is not the finite string input
basis from which all computations must begin.
https://en.wikipedia.org/wiki/Computable_function
WHy isn't DDD made into the correct finite string?i
DDD is a semantically and syntactically correct finite
stirng of the x86 machine language.
Which includes the machine code of DDD, the machine code of HHH, and
the machine code of everything it calls down to the OS level.
That seems to be your own fault.
The problem has always been that you want to use the wrong string
for DDD by excluding the code for HHH from it.
DDD emulated by HHH directly causes recursive emulation
because it calls HHH(DDD) to emulate itself again. HHH
complies until HHH determines that this cycle cannot
possibly reach the final halt state of DDD.
Which is another way of saying that HHH can't determine that DDD
halts when executed directly.
given an input of the function domain it can
return the corresponding output.
https://en.wikipedia.org/wiki/Computable_function
Computable functions are only allowed to compute the
mapping from their input finite strings to an output.
The HHH you implemented is computing *a* computable function, but it's
not computing the halting function:
The whole point of this post is to prove that
no Turing machine ever reports on the behavior
of the direct execution of 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
Cannot possibly be a computable function because computable
functions cannot possibly have directly executing Turing
machines as their inputs.
Computable functions don't have inputs. They have domains. Turing
machines have inputs.p
Maybe when pure math objects. In every model of
computation they seem to always have inputs. https://en.wikipedia.org/wiki/Computable_function
While the inputs to TMs are restricted to strings, there is no such
such restriction on computable functions.
The vast majority of computable functions of interest do *not* have
strings as their domains, yet they remain computable functions (a
simple example would be the parity function which maps NATURAL NUMBERS
(not strings) to yes/no values.)
Since there is a bijection between natural numbers
and strings of decimal digits your qualification
seems vacuous.
On 3/24/2025 5:49 PM, André G. Isaak wrote:
On 2025-03-24 16:43, olcott wrote:
Computable functions don't have inputs. They have domains. Turing
machines have inputs.p
Maybe when pure math objects. In every model of
computation they seem to always have inputs.
https://en.wikipedia.org/wiki/Computable_function
Computable functions *are* pure math objects. You seem to want to
conflate them with C functions, but that is not the case.
The crucial point is that the domains of computable functions are
*not* restricted to strings, even if the inputs to Turing Machines are.
While the inputs to TMs are restricted to strings, there is no such
such restriction on computable functions.
The vast majority of computable functions of interest do *not* have
strings as their domains, yet they remain computable functions (a
simple example would be the parity function which maps NATURAL
NUMBERS (not strings) to yes/no values.)
Since there is a bijection between natural numbers
and strings of decimal digits your qualification
seems vacuous.
There is not a bijection between natural numbers and strings. There is
a one-to-many mapping from natural numbers to strings, just as there
is a one-to-many mapping from computations (i.e. turing machine/input
string pairs, i.e. actual Turing machines directly running on their
inputs) to strings.
André
_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]
When III is emulated by pure emulator EEE for any finite
number of steps of emulation according to the semantics
of the x86 language it never reaches its own "ret"
instruction final halt state THUS DOES NOT HALT.
When III is directly executed calls an EEE instance
that only emulates finite number of steps then this
directly executed III always reaches its own "ret"
instruction final halt state THUS HALTS.
On 3/24/2025 6:05 PM, André G. Isaak wrote:
On 2025-03-24 17:04, olcott wrote:
_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]
When III is emulated by pure emulator EEE for any finite
number of steps of emulation according to the semantics
of the x86 language it never reaches its own "ret"
instruction final halt state THUS DOES NOT HALT.
When III is directly executed calls an EEE instance
that only emulates finite number of steps then this
directly executed III always reaches its own "ret"
instruction final halt state THUS HALTS.
And that has what, exactly, to do with the post you are allegedly
responding to?
André
THE INPUT FINITE STRING DOES SPECIFY RECURSIVE EMULATION.
The behavior specified by the finite string input to a
computable function implemented on a model of computation
does differ from the direct execution of this same finite
string because the direct execution avoids the pathological
self-reference that causes the recursive emulation.
THE INPUT FINITE STRING DOES SPECIFY RECURSIVE EMULATION.
On 3/24/2025 10:14 AM, dbush wrote:
On 3/24/2025 11:03 AM, olcott wrote:
On 3/24/2025 6:23 AM, Richard Damon wrote:
On 3/23/25 11:09 PM, olcott wrote:
It is impossible for HHH compute the function from the direct
execution of DDD because DDD is not the finite string input
basis from which all computations must begin.
https://en.wikipedia.org/wiki/Computable_function
WHy isn't DDD made into the correct finite string?i
DDD is a semantically and syntactically correct finite
stirng of the x86 machine language.
Which includes the machine code of DDD, the machine code of HHH, and
the machine code of everything it calls down to the OS level.
That seems to be your own fault.
The problem has always been that you want to use the wrong string
for DDD by excluding the code for HHH from it.
DDD emulated by HHH directly causes recursive emulation
because it calls HHH(DDD) to emulate itself again. HHH
complies until HHH determines that this cycle cannot
possibly reach the final halt state of DDD.
Which is another way of saying that HHH can't determine that DDD halts
when executed directly.
given an input of the function domain it can
return the corresponding output. https://en.wikipedia.org/wiki/Computable_function
Computable functions are only allowed to compute the
mapping from their input finite strings to an output.
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.
For example pure math functions don't have any specific
storage like a tape or machine registers.
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.
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.
On 3/24/2025 10:12 PM, dbush wrote:Fine, their descriptions are, and their behaviour is computable -
On 3/24/2025 10:07 PM, olcott wrote:
On 3/24/2025 8:46 PM, André G. Isaak wrote:And not all mathematical functions are computable, such as the halting
On 2025-03-24 19:33, olcott wrote:https://en.wikipedia.org/wiki/Pure_function Is another way to look at
On 3/24/2025 7:00 PM, André G. Isaak wrote:Those are called computations or algorithms, not computable
In the post you were responding to I pointed out that computableComputable functions implemented using models of computation would
functions are mathematical objects.
seem to be more concrete than pure math functions.
functions.
computable functions implemented by some concrete model of
computation.
function.
You just aren't paying enough attention. Turing machines are never inFalse. *All* turing machine are the domain of the halting function,The halting problems asks whether there *is* an algorithm which canNone-the-less it only has specific elements of its domain as its
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).
entire basis. For Turing machines this always means a finite string
that (for example) encodes a specific sequence of moves.
and the existence of UTMs show that all turning machines can be
described by a finite string.
the domain of any computable function. <snip>
What details?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.
Circular reasoning. You'll have to prove HHH simulates correctly first.There are no details abstracted away. The halting function is simplyWhen the measure of the behavior specified by a finite string input DD
uncomputable.
is when correctly emulated by HHH then DD can't reach its own final halt state then not-halting is decidable.
--A halt decider cannot existSo again, you explicitly agree with the Linz proof and all other proofs
of the halting function.
because the halting problem is defined incorrectlyThere'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.
On 3/24/2025 5:49 PM, André G. Isaak wrote:A pure simulator can not limit the number of steps. Also III doesn't
On 2025-03-24 16:43, olcott wrote:
Computable functions *are* pure math objects. You seem to want toComputable functions don't have inputs. They have domains. TuringMaybe when pure math objects. In every model of computation they seem
machines have inputs.
to always have inputs.
conflate them with C functions, but that is not the case.
The crucial point is that the domains of computable functions are *not*
restricted to strings, even if the inputs to Turing Machines are.
There is not a bijection between natural numbers and strings. There isWhile the inputs to TMs are restricted to strings, there is no suchSince there is a bijection between natural numbers and strings of
such restriction on computable functions.
The vast majority of computable functions of interest do *not* have
strings as their domains, yet they remain computable functions (a
simple example would be the parity function which maps NATURAL
NUMBERS (not strings) to yes/no values.)
decimal digits your qualification seems vacuous.
a one-to-many mapping from natural numbers to strings, just as there is
a one-to-many mapping from computations (i.e. turing machine/input
string pairs, i.e. actual Turing machines directly running on their
inputs) to strings.
When III is emulated by pure emulator EEE for any finite number of steps
of emulation according to the semantics of the x86 language it never
reaches its own "ret" instruction final halt state THUS DOES NOT HALT.
When III is directly executed calls an EEE instance that only emulates
finite number of steps then this directly executed III always reaches
its own "ret" instruction final halt state THUS HALTS.
On 3/24/2025 10:14 AM, dbush wrote:
On 3/24/2025 11:03 AM, olcott wrote:
On 3/24/2025 6:23 AM, Richard Damon wrote:
On 3/23/25 11:09 PM, olcott wrote:
It is impossible for HHH compute the function from the direct
execution of DDD because DDD is not the finite string input
basis from which all computations must begin.
https://en.wikipedia.org/wiki/Computable_function
WHy isn't DDD made into the correct finite string?i
DDD is a semantically and syntactically correct finite
stirng of the x86 machine language.
Which includes the machine code of DDD, the machine code of HHH, and
the machine code of everything it calls down to the OS level.
That seems to be your own fault.
The problem has always been that you want to use the wrong string for
DDD by excluding the code for HHH from it.
DDD emulated by HHH directly causes recursive emulation
because it calls HHH(DDD) to emulate itself again. HHH
complies until HHH determines that this cycle cannot
possibly reach the final halt state of DDD.
Which is another way of saying that HHH can't determine that DDD halts
when executed directly.
given an input of the function domain it can
return the corresponding output. https://en.wikipedia.org/wiki/Computable_function
Computable functions are only allowed to compute the
mapping from their input finite strings to an output.
On 3/24/2025 4:49 PM, André G. Isaak wrote:UTMs do.
On 2025-03-24 14:11, olcott wrote:
On 3/24/2025 12:35 PM, dbush wrote:
On 3/24/2025 12:44 PM, olcott wrote:
On 3/24/2025 10:14 AM, dbush wrote:
On 3/24/2025 11:03 AM, olcott wrote:
On 3/24/2025 6:23 AM, Richard Damon wrote:
On 3/23/25 11:09 PM, olcott wrote:
The whole point of this post is to prove that no Turing machine everThe HHH you implemented is computing *a* computable function, butgiven an input of the function domain it can return theWhich includes the machine code of DDD, the machine code of HHH,DDD is a semantically and syntactically correct finite stirng of >>>>>>> the x86 machine language.It is impossible for HHH compute the function from the direct >>>>>>>>> execution of DDD because DDD is not the finite string inputWHy isn't DDD made into the correct finite string?i
basis from which all computations must begin.
https://en.wikipedia.org/wiki/Computable_function
and the machine code of everything it calls down to the OS level.
Which is another way of saying that HHH can't determine that DDDThat seems to be your own fault.DDD emulated by HHH directly causes recursive emulation because it >>>>>>> calls HHH(DDD) to emulate itself again. HHH complies until HHH
The problem has always been that you want to use the wrong string >>>>>>>> for DDD by excluding the code for HHH from it.
determines that this cycle cannot possibly reach the final halt
state of DDD.
halts when executed directly.
corresponding output.
Computable functions are only allowed to compute the mapping from
their input finite strings to an output.
it's not computing the halting function:
reports on the behavior of the direct execution of another Turing
machine.
Whatever. It can still compute the direct execution from the description,Given any algorithm (i.e. a fixed immutable sequence of instructions)Cannot possibly be a computable function because computable functions
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
cannot possibly have directly executing Turing machines as their
inputs.
No, *the* halting function is undecidable.Computable functions don't have inputs. They have domains. TuringMaybe when pure math objects. In every model of computation they seem to always have inputs.
machines have inputs.
While the inputs to TMs are restricted to strings, there is no suchSince there is a bijection between natural numbers and strings of
such restriction on computable functions.
The vast majority of computable functions of interest do *not* have
strings as their domains, yet they remain computable functions (a
simple example would be the parity function which maps NATURAL NUMBERS
(not strings) to yes/no values.)
decimal digits your qualification seems vacuous.
You really need to learn the difference between a Halt decider and theA halting function need not be a decider?
halting function. They are distinct things.
In any case no computable function within any model of computationSimulators compute the mapping from a description to the directly
computes the mapping from the behavior of any other directly executing process to anything else.
*THIS MAKES THE FOLLOWING STATEMENT INCORRECT*And what does it contradict?
On 3/24/2025 12:35 PM, dbush wrote:
A solution to the halting problem is an algorithm H that computes the following mapping:A definition can be shown to be incorrect when it contradicts other definitions in the same system.
(<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
On 2025-03-24 16:43, olcott wrote:
Computable functions don't have inputs. They have domains. Turing
machines have inputs.p
Maybe when pure math objects. In every model of
computation they seem to always have inputs.
https://en.wikipedia.org/wiki/Computable_function
Computable functions *are* pure math objects. You seem to want to
conflate them with C functions, but that is not the case.
The crucial point is that the domains of computable functions are *not* restricted to strings, even if the inputs to Turing Machines are.
While the inputs to TMs are restricted to strings, there is no such
such restriction on computable functions.
The vast majority of computable functions of interest do *not* have
strings as their domains, yet they remain computable functions (a
simple example would be the parity function which maps NATURAL NUMBERS
(not strings) to yes/no values.)
Since there is a bijection between natural numbers
and strings of decimal digits your qualification
seems vacuous.
There is not a bijection between natural numbers and strings.
On 3/24/2025 12:35 PM, dbush wrote:
On 3/24/2025 12:44 PM, olcott wrote:
On 3/24/2025 10:14 AM, dbush wrote:
On 3/24/2025 11:03 AM, olcott wrote:
On 3/24/2025 6:23 AM, Richard Damon wrote:
On 3/23/25 11:09 PM, olcott wrote:
It is impossible for HHH compute the function from the direct
execution of DDD because DDD is not the finite string input
basis from which all computations must begin.
https://en.wikipedia.org/wiki/Computable_function
WHy isn't DDD made into the correct finite string?i
DDD is a semantically and syntactically correct finite
stirng of the x86 machine language.
Which includes the machine code of DDD, the machine code of HHH, and
the machine code of everything it calls down to the OS level.
That seems to be your own fault.
The problem has always been that you want to use the wrong string for >>>>>> DDD by excluding the code for HHH from it.
DDD emulated by HHH directly causes recursive emulation
because it calls HHH(DDD) to emulate itself again. HHH
complies until HHH determines that this cycle cannot
possibly reach the final halt state of DDD.
Which is another way of saying that HHH can't determine that DDD halts >>>> when executed directly.
given an input of the function domain it can
return the corresponding output.
https://en.wikipedia.org/wiki/Computable_function
Computable functions are only allowed to compute the
mapping from their input finite strings to an output.
The HHH you implemented is computing *a* computable function, but it's
not computing the halting function:
The whole point of this post is to prove that
no Turing machine ever reports on the behavior
of the direct execution of another Turing machine.
On 3/24/2025 3:18 PM, dbush wrote:The description of a TM completely specifies whether that maching halts. UTMs/Simulators compute that behaviour from that string.
On 3/24/2025 4:11 PM, olcott wrote:
On 3/24/2025 12:35 PM, dbush wrote:
On 3/24/2025 12:44 PM, olcott wrote:
On 3/24/2025 10:14 AM, dbush wrote:
On 3/24/2025 11:03 AM, olcott wrote:
On 3/24/2025 6:23 AM, Richard Damon wrote:
On 3/23/25 11:09 PM, olcott wrote:
It has no way of directly computing this. It can only compute theSure it can. Any that takes a description of a turning machine thatThe whole point of this post is to prove that no Turing machine everThe HHH you implemented is computing *a* computable function, butgiven an input of the function domain it can return theWhich is another way of saying that HHH can't determine that DDDThat seems to be your own fault.DDD emulated by HHH directly causes recursive emulation because it >>>>>>> calls HHH(DDD) to emulate itself again. HHH complies until HHH
The problem has always been that you want to use the wrong string >>>>>>>> for DDD by excluding the code for HHH from it.
determines that this cycle cannot possibly reach the final halt
state of DDD.
halts when executed directly.
corresponding output.
Computable functions are only allowed to compute the mapping from
their input finite strings to an output.
it's not computing the halting function:
reports on the behavior of the direct execution of another Turing
machine.
halt when executed directly is correct to return 1, regardless
of the logic used to do so.
behavior that the finite string specifies.
On 3/24/2025 12:35 PM, dbush wrote:
On 3/24/2025 12:44 PM, olcott wrote:
On 3/24/2025 10:14 AM, dbush wrote:
On 3/24/2025 11:03 AM, olcott wrote:
On 3/24/2025 6:23 AM, Richard Damon wrote:
On 3/23/25 11:09 PM, olcott wrote:
It is impossible for HHH compute the function from the direct
execution of DDD because DDD is not the finite string input
basis from which all computations must begin.
https://en.wikipedia.org/wiki/Computable_function
WHy isn't DDD made into the correct finite string?i
DDD is a semantically and syntactically correct finite
stirng of the x86 machine language.
Which includes the machine code of DDD, the machine code of HHH, and
the machine code of everything it calls down to the OS level.
That seems to be your own fault.
The problem has always been that you want to use the wrong string
for DDD by excluding the code for HHH from it.
DDD emulated by HHH directly causes recursive emulation
because it calls HHH(DDD) to emulate itself again. HHH
complies until HHH determines that this cycle cannot
possibly reach the final halt state of DDD.
Which is another way of saying that HHH can't determine that DDD
halts when executed directly.
given an input of the function domain it can
return the corresponding output.
https://en.wikipedia.org/wiki/Computable_function
Computable functions are only allowed to compute the
mapping from their input finite strings to an output.
The HHH you implemented is computing *a* computable function, but it's
not computing the halting function:
The whole point of this post is to prove that
no Turing machine ever reports on the behavior
of the direct execution of 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
Cannot possibly be a computable function because computable
functions cannot possibly have directly executing Turing
machines as their inputs.
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>
On 3/24/2025 7:00 PM, André G. Isaak wrote:
On 2025-03-24 17:42, olcott wrote:
On 3/24/2025 6:05 PM, André G. Isaak wrote:
On 2025-03-24 17:04, olcott wrote:
_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]
When III is emulated by pure emulator EEE for any finite
number of steps of emulation according to the semantics
of the x86 language it never reaches its own "ret"
instruction final halt state THUS DOES NOT HALT.
When III is directly executed calls an EEE instance
that only emulates finite number of steps then this
directly executed III always reaches its own "ret"
instruction final halt state THUS HALTS.
And that has what, exactly, to do with the post you are allegedly
responding to?
André
THE INPUT FINITE STRING DOES SPECIFY RECURSIVE EMULATION.
The behavior specified by the finite string input to a
computable function implemented on a model of computation
does differ from the direct execution of this same finite
string because the direct execution avoids the pathological
self-reference that causes the recursive emulation.
THE INPUT FINITE STRING DOES SPECIFY RECURSIVE EMULATION.
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.
For example pure math functions don't have any specific
storage like a tape or machine registers.
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.
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.
code of correctly
emulated by EEE machine code does not map to its direct
execution.
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.
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.
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.
A halt decider cannot exist because the halting problem is
defined incorrectly ignoring key details that change
everything.
To unequivocally see these key details we examine x86 code
such that every control flow instruction is implemented
within a directed graph of 100% specific state transitions.
---
Copyright 2025 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer
On 3/25/2025 1:37 PM, dbush wrote:Therefore we encode it.
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:
It is impossible for an actual Turing machine to be input to >>>>>>>>>>>>> any other TM.
WTF, a TM is specified by its description.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.
I don't care what some simulator says, I want to know whether theDoes III emulated by EEE reach its final halt state when III defines >>>>> a pathological relationship with its emulator?Which is why III emulated by EEE is not relevant.Which is not relevant to whether or not III emulated by EEEIs 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.That is not the complete description. The complete description >>>>>>>>>> consists of the code of IIIand the fact that EEE
reaches its own final halt state.
And that is its direct execution.The input to a Turing machine cannot possibly be the actual behavior ofAnd those finite strings can be a complete description of a turingBut that's not the question. The question is whether or not an HTuring machines are only capable operating on input finite strings.
exists that behaves as described below:
machine
any executing process.
A Turing machine can only port on the behavior that a finite string
input specifies.
Yes, exactly.NO WRONG. Turing machine computable functions cannot compute any mappingTuring machine computable functions cannot compute anything that theirTranslation: algorithms only compute what they're programed to compute.
input doesn't specify.
from anything that their input DOES NOT SAY.
THEIR INPUT CANNOT POSSIBLY SAY THE ACTUAL BEHAVIOR OF ANY EXECUTINGWrong, that is exactly what the description of a TM says.
PROCESS
No, DD halts.And the algorithm your EEE is computing is not the mathematical haltingWhen HHH rejects DD as specifying a computation that does not reach its
function, which has proven to not be computable:
final halt state HHH IS CORRECT.
How else would you specify a TM?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
On 3/25/2025 3:47 AM, joes wrote:They don't repeat, though, not in the same stack frame. And the test
A pure simulator can not limit the number of steps. Also III doesn'tThe fact that the same states in the program-under-test keep repeating
halt in, say, 3 steps. Why should III call a different instance that
doesn't abort, when it is being simulated?
such that the program-under-test cannot possibly reach its own final
halt state proves that program-under-test does not halt.
On 3/25/2025 3:47 AM, joes wrote:
Am Mon, 24 Mar 2025 18:04:21 -0500 schrieb olcott:
On 3/24/2025 5:49 PM, André G. Isaak wrote:
On 2025-03-24 16:43, olcott wrote:
Computable functions *are* pure math objects. You seem to want toComputable functions don't have inputs. They have domains. TuringMaybe when pure math objects. In every model of computation they seem >>>>> to always have inputs.
machines have inputs.
conflate them with C functions, but that is not the case.
The crucial point is that the domains of computable functions are *not* >>>> restricted to strings, even if the inputs to Turing Machines are.
There is not a bijection between natural numbers and strings. There is >>>> a one-to-many mapping from natural numbers to strings, just as there is >>>> a one-to-many mapping from computations (i.e. turing machine/inputWhile the inputs to TMs are restricted to strings, there is no such >>>>>> such restriction on computable functions.Since there is a bijection between natural numbers and strings of
The vast majority of computable functions of interest do *not* have >>>>>> strings as their domains, yet they remain computable functions (a
simple example would be the parity function which maps NATURAL
NUMBERS (not strings) to yes/no values.)
decimal digits your qualification seems vacuous.
string pairs, i.e. actual Turing machines directly running on their
inputs) to strings.
When III is emulated by pure emulator EEE for any finite number of steps >>> of emulation according to the semantics of the x86 language it never
reaches its own "ret" instruction final halt state THUS DOES NOT HALT.
When III is directly executed calls an EEE instance that only emulates
finite number of steps then this directly executed III always reaches
its own "ret" instruction final halt state THUS HALTS.
A pure simulator can not limit the number of steps. Also III doesn't
halt in, say, 3 steps. Why should III call a different instance
that doesn't abort, when it is being simulated?
The fact that the same states in the program-under-test
keep repeating such that the program-under-test cannot
possibly reach its own final halt state proves that
program-under-test does not halt.
On 3/25/2025 9:59 AM, dbush wrote:
On 3/25/2025 9:14 AM, olcott wrote:
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:And not all mathematical functions are computable, such as the
On 2025-03-24 19:33, olcott wrote:https://en.wikipedia.org/wiki/Pure_function Is another way to
On 3/24/2025 7:00 PM, André G. Isaak wrote:Those are called computations or algorithms, not computable
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.
functions.
look at
computable functions implemented by some concrete model of
computation.
halting
function.
You just aren't paying enough attention. Turing machines are never in >>>>> the domain of any computable function. <snip>False. *All* turing machine are the domain of the halting function, >>>>>> and the existence of UTMs show that all turnBing machines can beThe 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, andNone-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.
independent of,
any such algorithm (if one existed).
described by a finite string.
Fine, their descriptions are, and their behaviour is computable -
by running them.
Halt deciders
Don't exist, because no H satisfies this requirement:
Because no TM can ever take another actual TM as an input.
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
On 3/25/2025 4:22 AM, Mikko wrote:
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.
IT IS COUNTER-FACTUAL THAT A MACHINE DESCRIPTION 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]
When any finite number of steps of III is emulated by
EEE according to the semantics of the x86 language the
emulated III never reaches its "ret" instruction final
halt state and the directly executed III does halt.
This conclusively proves that a machine description does
not always specify the same behavior as the directly
executed machine.
On 3/25/2025 4:29 PM, joes wrote:
Am Tue, 25 Mar 2025 08:01:14 -0500 schrieb olcott:
On 3/25/2025 3:47 AM, joes wrote:
A pure simulator can not limit the number of steps. Also III doesn'tThe fact that the same states in the program-under-test keep repeating
halt in, say, 3 steps. Why should III call a different instance that
doesn't abort, when it is being simulated?
such that the program-under-test cannot possibly reach its own final
halt state proves that program-under-test does not halt.
They don't repeat, though, not in the same stack frame. And the test
program is part of the program under test. Can you answer my question?
Your question was incorrect.
_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]
The first four instructions of the finite string
of machine code at machine address 00002172 are
repeated until EEE reaches its finite limit.
On 3/25/2025 3:54 AM, joes wrote:
Am Mon, 24 Mar 2025 17:43:14 -0500 schrieb olcott:
On 3/24/2025 4:49 PM, André G. Isaak wrote:UTMs do.
On 2025-03-24 14:11, olcott wrote:
On 3/24/2025 12:35 PM, dbush wrote:
On 3/24/2025 12:44 PM, olcott wrote:
On 3/24/2025 10:14 AM, dbush wrote:
On 3/24/2025 11:03 AM, olcott wrote:
On 3/24/2025 6:23 AM, Richard Damon wrote:
On 3/23/25 11:09 PM, olcott wrote:
The whole point of this post is to prove that no Turing machine ever >>>>> reports on the behavior of the direct execution of another TuringThe HHH you implemented is computing *a* computable function, butgiven an input of the function domain it can return theWhich includes the machine code of DDD, the machine code of HHH, >>>>>>>> and the machine code of everything it calls down to the OS level. >>>>>>>>DDD is a semantically and syntactically correct finite stirng of >>>>>>>>> the x86 machine language.It is impossible for HHH compute the function from the direct >>>>>>>>>>> execution of DDD because DDD is not the finite string input >>>>>>>>>>> basis from which all computations must begin.WHy isn't DDD made into the correct finite string?i
https://en.wikipedia.org/wiki/Computable_function
Which is another way of saying that HHH can't determine that DDD >>>>>>>> halts when executed directly.That seems to be your own fault.DDD emulated by HHH directly causes recursive emulation because it >>>>>>>>> calls HHH(DDD) to emulate itself again. HHH complies until HHH >>>>>>>>> determines that this cycle cannot possibly reach the final halt >>>>>>>>> state of DDD.
The problem has always been that you want to use the wrong string >>>>>>>>>> for DDD by excluding the code for HHH from it.
corresponding output.
Computable functions are only allowed to compute the mapping from >>>>>>> their input finite strings to an output.
it's not computing the halting function:
machine.
They never do, they only report on the behavior that
their input finite string specifies. When their input
finite string defines a pathological relationship
with its simulator then the specified behavior can
differ from the behavior of the direct execution.
Everyone here has been happily denying this verified
fact disagreeing with the behavior that the semantics
of the x86 language species. That is like disagreeing
with arithmetic just to make sure to be disagreeable.
On 3/25/2025 3:47 AM, joes wrote:
Am Mon, 24 Mar 2025 18:04:21 -0500 schrieb olcott:
On 3/24/2025 5:49 PM, André G. Isaak wrote:
On 2025-03-24 16:43, olcott wrote:
Computable functions *are* pure math objects. You seem to want toComputable functions don't have inputs. They have domains. TuringMaybe when pure math objects. In every model of computation they seem >>>>> to always have inputs.
machines have inputs.
conflate them with C functions, but that is not the case.
The crucial point is that the domains of computable functions are *not* >>>> restricted to strings, even if the inputs to Turing Machines are.
There is not a bijection between natural numbers and strings. There is >>>> a one-to-many mapping from natural numbers to strings, just as there is >>>> a one-to-many mapping from computations (i.e. turing machine/inputWhile the inputs to TMs are restricted to strings, there is no such >>>>>> such restriction on computable functions.Since there is a bijection between natural numbers and strings of
The vast majority of computable functions of interest do *not* have >>>>>> strings as their domains, yet they remain computable functions (a
simple example would be the parity function which maps NATURAL
NUMBERS (not strings) to yes/no values.)
decimal digits your qualification seems vacuous.
string pairs, i.e. actual Turing machines directly running on their
inputs) to strings.
When III is emulated by pure emulator EEE for any finite number of steps >>> of emulation according to the semantics of the x86 language it never
reaches its own "ret" instruction final halt state THUS DOES NOT HALT.
When III is directly executed calls an EEE instance that only emulates
finite number of steps then this directly executed III always reaches
its own "ret" instruction final halt state THUS HALTS.
A pure simulator can not limit the number of steps. Also III doesn't
halt in, say, 3 steps. Why should III call a different instance
that doesn't abort, when it is being simulated?
There is no different instance of EEE that doesn't abort.
They all stop emulating after a finite number of steps.
When EEE emulates 4 billion steps of III, III never
reaches its final halt state.
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:And not all mathematical functions are computable, such as the halting >>>> function.
On 2025-03-24 19:33, olcott wrote:https://en.wikipedia.org/wiki/Pure_function Is another way to look at >>>>> computable functions implemented by some concrete model of
On 3/24/2025 7:00 PM, André G. Isaak wrote:Those are called computations or algorithms, not computable
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.
functions.
computation.
You just aren't paying enough attention. Turing machines are never inFalse. *All* turing machine are the domain of 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.
and the existence of UTMs show that all turning machines can be
described by a finite string.
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.
On 3/25/2025 3:54 AM, Mikko wrote:
On 2025-03-24 16:44:52 +0000, olcott said:
On 3/24/2025 10:14 AM, dbush wrote:
On 3/24/2025 11:03 AM, olcott wrote:
On 3/24/2025 6:23 AM, Richard Damon wrote:
On 3/23/25 11:09 PM, olcott wrote:
It is impossible for HHH compute the function from the direct
execution of DDD because DDD is not the finite string input
basis from which all computations must begin.
https://en.wikipedia.org/wiki/Computable_function
WHy isn't DDD made into the correct finite string?i
DDD is a semantically and syntactically correct finite
stirng of the x86 machine language.
Which includes the machine code of DDD, the machine code of HHH, and
the machine code of everything it calls down to the OS level.
That seems to be your own fault.
The problem has always been that you want to use the wrong string for >>>>>> DDD by excluding the code for HHH from it.
DDD emulated by HHH directly causes recursive emulation
because it calls HHH(DDD) to emulate itself again. HHH
complies until HHH determines that this cycle cannot
possibly reach the final halt state of DDD.
Which is another way of saying that HHH can't determine that DDD halts >>>> when executed directly.
given an input of the function domain it can
return the corresponding output.
https://en.wikipedia.org/wiki/Computable_function
Computable functions are only allowed to compute the
mapping from their input finite strings to an output.
A comutable function does not compute. A Turing machine can compute
a value of a computable function.
Whenever I have referred to a computable function
I have always been referring to computable functions
implemented within some model of computation that
like Turing machines have finite strings as their
only input.
All computations are allowed. There are not other restrictions on
computable functions that that it must be a function and thane it
must be computable.
Computing who will win the next presidential election
on the basis of the finite string "the" violates what
computations are and how they work thus does not derive
any undecidable decision problem.
Likewise computing the behavior of the direct execution
of a Turing Machine based on its machine description can
be incorrect when this machine has defined a pathological
relationship with its emulator.
On 3/25/2025 4:22 AM, Mikko wrote:
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.
IT IS COUNTER-FACTUAL THAT A MACHINE DESCRIPTION SPECIFIES
BEHAVIOR IDENTICAL TO THE DIRECTLY EXECUTED MACHINE.
On 3/25/2025 4:22 AM, Mikko wrote:It is not very interesting to know whether a simulator is able to report
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.
IT IS COUNTER-FACTUAL THAT A MACHINE DESCRIPTION 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]
When any finite number of steps of III is emulated by
EEE according to the semantics of the x86 language the
emulated III never reaches its "ret" instruction final
halt state and the directly executed III does halt.
On 3/25/2025 3:54 AM, Mikko wrote:
On 2025-03-24 16:44:52 +0000, olcott said:
On 3/24/2025 10:14 AM, dbush wrote:
On 3/24/2025 11:03 AM, olcott wrote:
On 3/24/2025 6:23 AM, Richard Damon wrote:
On 3/23/25 11:09 PM, olcott wrote:
It is impossible for HHH compute the function from the direct
execution of DDD because DDD is not the finite string input
basis from which all computations must begin.
https://en.wikipedia.org/wiki/Computable_function
WHy isn't DDD made into the correct finite string?i
DDD is a semantically and syntactically correct finite
stirng of the x86 machine language.
Which includes the machine code of DDD, the machine code of HHH, and
the machine code of everything it calls down to the OS level.
That seems to be your own fault.
The problem has always been that you want to use the wrong string
for DDD by excluding the code for HHH from it.
DDD emulated by HHH directly causes recursive emulation
because it calls HHH(DDD) to emulate itself again. HHH
complies until HHH determines that this cycle cannot
possibly reach the final halt state of DDD.
Which is another way of saying that HHH can't determine that DDD
halts when executed directly.
given an input of the function domain it can
return the corresponding output.
https://en.wikipedia.org/wiki/Computable_function
Computable functions are only allowed to compute the
mapping from their input finite strings to an output.
A comutable function does not compute. A Turing machine can compute
a value of a computable function.
Whenever I have referred to a computable function
I have always been referring to computable functions
implemented within some model of computation that
like Turing machines have finite strings as their
only input.
All computations are allowed. There are not other restrictions on
computable functions that that it must be a function and thane it
must be computable.
Computing who will win the next presidential election
on the basis of the finite string "the" violates what
computations are and how they work thus does not derive
any undecidable decision problem.
Likewise computing the behavior of the direct execution
of a Turing Machine based on its machine description can
be incorrect when this machine has defined a pathological
relationship with its emulator.
_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]
When any finite number of steps of III is emulated by
EEE according to the semantics of the x86 language the
emulated III never reaches its "ret" instruction final
halt state and the directly executed III does halt.
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:Those are called computations or algorithms, not computable >>>>>>>>>>>> functions.
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. >>>>>>>>>>>>
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.
On 3/25/2025 3:47 AM, joes wrote:
Am Mon, 24 Mar 2025 18:04:21 -0500 schrieb olcott:
On 3/24/2025 5:49 PM, André G. Isaak wrote:
On 2025-03-24 16:43, olcott wrote:
Computable functions *are* pure math objects. You seem to want toComputable functions don't have inputs. They have domains. TuringMaybe when pure math objects. In every model of computation they seem >>>>> to always have inputs.
machines have inputs.
conflate them with C functions, but that is not the case.
The crucial point is that the domains of computable functions are *not* >>>> restricted to strings, even if the inputs to Turing Machines are.
There is not a bijection between natural numbers and strings. There is >>>> a one-to-many mapping from natural numbers to strings, just as there is >>>> a one-to-many mapping from computations (i.e. turing machine/inputWhile the inputs to TMs are restricted to strings, there is no such >>>>>> such restriction on computable functions.Since there is a bijection between natural numbers and strings of
The vast majority of computable functions of interest do *not* have >>>>>> strings as their domains, yet they remain computable functions (a
simple example would be the parity function which maps NATURAL
NUMBERS (not strings) to yes/no values.)
decimal digits your qualification seems vacuous.
string pairs, i.e. actual Turing machines directly running on their
inputs) to strings.
When III is emulated by pure emulator EEE for any finite number of steps >>> of emulation according to the semantics of the x86 language it never
reaches its own "ret" instruction final halt state THUS DOES NOT HALT.
When III is directly executed calls an EEE instance that only emulates
finite number of steps then this directly executed III always reaches
its own "ret" instruction final halt state THUS HALTS.
A pure simulator can not limit the number of steps. Also III doesn't
halt in, say, 3 steps. Why should III call a different instance
that doesn't abort, when it is being simulated?
There is no different instance of EEE that doesn't abort.
They all stop emulating after a finite number of steps.
When EEE emulates 4 billion steps of III, III never
reaches its final halt state.
On 3/25/2025 10:02 AM, dbush wrote:is unable to reach the end of the simulation of a program that halts in
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]
When any finite number of steps of III is emulated by
EEE according to the semantics of the x86 language the
emulated III never reaches its "ret" instruction final
halt state and the directly executed III does halt.
It is not very interesting to know whether a simulator reports that it
On 3/25/2025 1:37 PM, dbush wrote:
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: >>>>>>>>>>>>>>>>>>Those are called computations or algorithms, not >>>>>>>>>>>>>>>>>> computable functions.
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. >>>>>>>>>>>>>>>>>>
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
The input to a Turing machine cannot possibly be
the actual behavior of any executing process.
A Turing machine can only port on the behavior that a
finite string input specifies.
Turing machine computable functions cannot
compute anything that their input doesn't specify.
Translation: algorithms only compute what they're programed to compute.
NO WRONG. Turing machine computable functions cannot
compute any mapping from anything that their input DOES NOT SAY.
THEIR INPUT CANNOT POSSIBLY SAY THE ACTUAL BEHAVIOR OF ANY
EXECUTING PROCESS
And the algorithm your EEE is computing is not the mathematical
halting function, which has proven to not be computable:
When HHH rejects DD as specifying a computation
that does not reach its final halt state HHH IS CORRECT.
On 3/25/2025 4:29 PM, joes wrote:How so? You said III calls a non-aborting simulator instead of the one
Am Tue, 25 Mar 2025 08:01:14 -0500 schrieb olcott:
On 3/25/2025 3:47 AM, joes wrote:
A pure simulator can not limit the number of steps. Also III doesn'tThe fact that the same states in the program-under-test keep repeating
halt in, say, 3 steps. Why should III call a different instance that
doesn't abort, when it is being simulated?
such that the program-under-test cannot possibly reach its own final
halt state proves that program-under-test does not halt.
They don't repeat, though, not in the same stack frame. And the testYour question was incorrect.
program is part of the program under test. Can you answer my question?
The first four instructions of the finite string of machine code atA simulator shouldn't be limited. And again, the instructions are not
machine address 00002172 are repeated until EEE reaches its finite
limit.
| Sysop: | Keyop |
|---|---|
| Location: | Huddersfield, West Yorkshire, UK |
| Users: | 546 |
| Nodes: | 16 (0 / 16) |
| Uptime: | 169:34:33 |
| Calls: | 10,385 |
| Calls today: | 2 |
| Files: | 14,057 |
| Messages: | 6,416,552 |