On 12/13/2021 7:55 PM, Richard Damon wrote:
> On 12/13/21 8:49 PM, olcott wrote:
>> On 12/13/2021 7:36 PM, André G. Isaak wrote:
>>> On 2021-12-13 18:09, olcott wrote:
>>>> On 12/13/2021 5:40 PM, André G. Isaak wrote:
>>>>> On 2021-12-13 16:25, olcott wrote:
>>>>>> On 12/13/2021 2:10 PM, André G. Isaak wrote:
>>>>>>> On 2021-12-13 11:37, olcott wrote:
>>>>>>>> On 12/13/2021 12:20 PM, André G. Isaak wrote:
>>>>>>>>> On 2021-12-13 11:10, olcott wrote:
>>>>>>>>>> On 12/13/2021 11:33 AM, André G. Isaak wrote:
>>>>>>>>>>> On 2021-12-13 09:33, olcott wrote:
>>>>>>>>>>>> On 12/13/2021 10:22 AM, André G. Isaak wrote:
>>>>>>>>>>>>> On 2021-12-13 08:50, olcott wrote:
>>>>>>>>>>>>>> On 12/13/2021 9:24 AM, André G. Isaak wrote:
>>>>>>>>>>>>>
>>>>>>>>>>>>>>> Your problem is that, despite the fact that you are
>>>>>>>>>>>>>>> talking about a theorem which concerns Turing Machines,
>>>>>>>>>>>>>>> you continue to think about things in terms of C programs
>>>>>>>>>>>>>>> and/or x86 programs which are very different animals from
>>>>>>>>>>>>>>> Turing Machines.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> As long as a C function is a pure function then it is a
>>>>>>>>>>>>>> computable function through the RASP model of computation
>>>>>>>>>>>>>> for every input that it derives an output.
>>>>>>>>>>>>>
>>>>>>>>>>>>> No C function is a computable function. Computable
>>>>>>>>>>>>> functions are a subset of *mathematical* functions. The
>>>>>>>>>>>>> word 'function' in C means something entirely different
>>>>>>>>>>>>> than the word 'function' in maths.
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> A function f with domain D is said to be Turing-computable
>>>>>>>>>>>> or just computable if there exists some Turing machine
>>>>>>>>>>>> M = (Q, Σ, Γ, δ, q0, □, F) such that q0 w ⊢* Mqff(w), qf ∈ F
>>>>>>>>>>>> for all w ∈ D (Linz:1990:243)
>>>>>>>>>>>
>>>>>>>>>>> Which perfectly agrees with what I just said.
>>>>>>>>>>>
>>>>>>>>>>>> Olcott paraphrase of above machine definition: Machine M
>>>>>>>>>>>> begins at start state q0 on input w and transitions to qf as
>>>>>>>>>>>> a function of input w.
>>>>>>>>>>>
>>>>>>>>>>> Which is not a paraphrase of the above.
>>>>>>>>>>>
>>>>>>>>>>>> Linz says that machine M computes the function f(w).
>>>>>>>>>>> Yes, machine M *computes* function f(w). This does not mean
>>>>>>>>>>> that machine M is a function. It is not. It is an algorithm.
>>>>>>>>>>> The whole point of my post was to try to get you to actually
>>>>>>>>>>> grasp the distinction between a function and an algorithm
>>>>>>>>>>> which computes that function. The two are not the same thing.
>>>>>>>>>>> The terms are not interchangeable. There isn't a one-to-one
>>>>>>>>>>> correspondence between the two.
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> When H(P,P) computes the halting function it is only the
>>>>>>>>>> behavior of the actual sequence of configurations specified by
>>>>>>>>>> (P,P) as if H was a UTM and not a halt decider that provides
>>>>>>>>>> the correct basis for the halt status decision. This is
>>>>>>>>>> consistently always the case for every input.
>>>>>>>>>
>>>>>>>>> So we're back to the "I don't understand what you wrote so I'll
>>>>>>>>> respond with something completely unrelated" approach. Do you
>>>>>>>>> know understand the difference between a function and an
>>>>>>>>> algorithm? If so, will you stop misusing them in future?
>>>>>>>>>
>>>>>>>>
>>>>>>>> H is not a computable function H computes the halting function.
>>>>>>>
>>>>>>> OK. So now you've finally gotten that part right.
>>>>>>>
>>>>>>> But now you need to think about what that actually *means*
>>>>>>>
>>>>>>> The halting function maps every member of the set of all possible
>>>>>>> computation to either 'HALTS' or 'DOESN'T HALT'. Note that this
>>>>>>> is simply a mapping. It exists independently of any algorithm
>>>>>>> (i.e. halt decider). It has a domain and a codomain. It has no
>>>>>>> 'inputs' since it is not an algorithm.
>>>>>>>
>>>>>>
>>>>>> H(P,P) computes the halting function for a domain that includes P.
>>>>>
>>>>> What on earth does that mean?
>>>>
>>>> You don't know what the domain of a function is?
>>>
>>> Yes, I do. And P isn't in the domain of the halting function. P(P) is
>>> in its domain but P is not.
>>>
>>>>> The domain of the halting function is the set of all possible
>>>>> computations.
>>>>
>>>> How many hundreds of times do I have to repeat that I am not solving
>>>> the halting problem merely refuting the conventional proofs???
>>>>
>>>> To refute the conventional proofs only requires correctly deciding
>>>> the halt status of a single element of the domain of a universal
>>>> halt function.
>>>
>>> And both P(P) and H_Hat(<H_Hat) *are* in the domain of the halting
>>> function and those are the two elements you claim to be concerned with.
>>>
>>> Both of these are mapped to 'HALTS' by the halting function because
>>> the halting function is concerned with how computations behave when
>>> they are actually run.
>>>
>>>>> A computation is a pair of a Turing Machine and an input string. P
>>>>> isn't such a pair.
>>>>>
>>>>
>>>> H does correctly compute the halt function of its domain and it need
>>>> not be a TM.
>>>>
>>>>>>> Because we've observed that P(P) and H_Hat(H_Hat) both halt when
>>>>>>> run, it will include P(P) -> HALTS and H_Hat(H_Hat) -> HALTS as
>>>>>>> part of its
>>>>>>
>>>>>> Neither of those are ACTUAL INPUTS in the domain.
>>>>>
>>>>> You may think this means something but I can't for the life of me
>>>>> figure out what it could be. Functions have domains. Turing
>>>>> Machines have inputs.
>>>>>
>>>>
>>>> Linz says input w is in the domain of f:
>>>> A function f with domain D is said to be Turing-computable
>>>> or just computable if there exists some Turing machine
>>>> M = (Q, Σ, Γ, δ, q0, □, F) such that q0 w ⊢* Mqff(w), qf ∈ F
>>>> for all w ∈ D (Linz:1990:243)
>>>>
>>>> Sipser says functions have inputs:
>>>> A Turing machine computes a function by starting with the input to
>>>> the function on the tape and halting with the output of the function
>>>> on the tape (Sipser:1997:190).
>>>>
>>>> So when I say that int main() { P(P); } is outside the scope of
>>>> computable function H because it is not an input to H I am correct.
>>>
>>> Again, what you write is nonsense. P(P) *is* in the domain of the
>>
>> It looks like both Sipser and Linz correct your "corrections", thus
>> proving that your "corrections" are incorrect.
>>
>> The C code that computes the halting function for a domain including
>> the x86 machine code of the following:
>>
>> void P(u32 x)
>> {
>>    if (H(x, x))
>>      HERE: goto HERE;
>> }
>>
>> void Infinite_Loop(int N)
>> {
>>    HERE: goto HERE;
>> }
>>
>> void Infinite_Recursion(int N)
>> {
>>    Infinite_Recursion(N);
>> }
>>
>> correctly determines that none of the above inputs ever stops running
>> without being aborted
>
> Except the P(P) does Halt if H(P,P) returns 0.

Computable functions are only accountable for their inputs the input to
H(P,P) never stops running unless aborted. The P(P) that you refer to is
not an actual input to the computable function H so its behavior is
totally irrelevant.

I am surprised that so many people here have been persisting so long in
the misconception that the behavior of a non-input in any way pertains
to a computable function.

Input w is in the domain of f
A function f with domain D is said to be Turing-computable
or just computable if there exists some Turing machine
M = (Q, Σ, Γ, δ, q0, □, F) such that q0 w ⊢* Mqff(w), qf ∈ F
for all w ∈ D (Linz:1990:243)

Olcott paraphrase of above machine definition: Machine M begins at start
state q0 on input w and transitions to qf as a function of input w.

COMPUTABLE FUNCTIONS
A Turing machine computes a function by starting with the input to the
function on the tape and halting with the output of the function on the
tape (Sipser:1997:190).

DEFINITION 5.12
A function f: Σ* → Σ* is a computable function if some Turing machine
M, on every input w, halts with just f(w) on its tape.

A partial function σ : Σ* → Σ* is said to be a computable function if
σ(x) = M(x) for some Turing machine M (Kozen:1997:347).

--
Copyright 2021 Pete Olcott

Talent hits a target no one else can hit;
Genius hits a target no one else can see.
Arthur Schopenhauer