Sujet : Re: Correcting the definition of the halting problem --- Computable functions
De : mikko.levanto (at) *nospam* iki.fi (Mikko)
Groupes : comp.theoryDate : 26. Mar 2025, 08:29:03
Autres entêtes
Organisation : -
Message-ID : <vs0abv$18vea$1@dont-email.me>
References : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
User-Agent : Unison/2.2
On 2025-03-25 13:34:19 +0000, olcott said:
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.
No, you have not. When you posted a link to the Wikipedia page
https://en.wikipedia.org/wiki/Computable_functionthat means, as you didn't state otherwise, that you use the term
with the same meaning as that page.
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.
That is not a computable function of the available data.
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.
If every Turing machine gives an icorrect answer for at least one input
then the function is not Turing computable. As far as we know there is
no way to compute functions that are not Turing computable.
-- Mikko
Correcting the definition of the halting problem --- Computable functions
Re: Correcting the definition of the halting problem --- Computable functions