Re: Solution To The Halting Problem [ C/x86 defines computable functions ]

[olcott]

On 5/4/2021 2:24 PM, Kaz Kylheku wrote:
> ["Followup-To:" header set to comp.theory.]
> On 2021-05-04, olcott <No...@NoWhere.com> wrote:
>> On 5/4/2021 12:06 PM, Kaz Kylheku wrote:
>>> On 2021-05-04, olcott <No...@NoWhere.com> wrote:
>>>> On 5/3/2021 6:27 PM, Ben Bacarisse wrote:
>>>>> Did you have a question about what I wrote? You seem to be having
>>>>> trouble understanding it.
>>>>>
>>>>
>>>> The notion of data passed to a function in the x86 architecture has zero
>>>
>>> There is no "function" in x86. Some assemblers for x86 in fact have
>>> pseudo-ops for delimiting a procedure using syntax like "PROC FAR" and
>>> "ENDP".
>>>
>>
>> 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)
>
> And nothing but the tape, so help you god.
>
> Each call Halts(P, P) is a new Turing machine, where the tape contents
> depend only on Halts and P, and not any global execution traces gathered
> by a larger surrouding machine.
>

int Halts(u32 P, u32 I)
{
Simulate(P,I) until decided not halts or halts.
if decided not halts return 0.
else return 1.
}

>> When we unify on the Sipser and Kozen definitions of "computable
>> function" we have the mapping from one possibly empty finite string to
>> another possibly empty finite string.
>
> Sure, and when Halts is invoked in you apparatus with apparently the
> same formal arguments, it does not represent the same mapping each time,
> as required.
>
> The tape is different each time. Since the arguments are not, and
> the function is the same, it means that the tape contains something
> not coming from the arguments.
>
> That arrangement cannot refute a proof in which it is critically
> important that the corresponding computations are one and the same.
>
>> It seems that we can define this in terms of a generic model of
>
> Well, things are not as they seem. If you were confident, you wouldn't
> use weasel words like "seem", would you.
>
>> computation as a machine that computes the mapping from one possibly
>> empty finite string input to another possibly empty finite string output
>> and and then halts.
>>
>> A C function that returns a 0 or 1 value on the basis of an input finite
>> string pair would meet the above definition of computable function.
>
> It could, but not necessarily so. To write a C function that behaves
> like function, in particular a function of the arguments given to its
> formal parameters, we have to follow certain coding rules.
>
> Your apparatus does not follow those rules.
>
> (By your own admission, Halts is not even an ordinary C function
> in the first place, but a special operator of the "x86 UTM".)
>


--
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre
minds." Einstein

[Kaz Kylheku]

["Followup-To:" header set to comp.theory.]

All you're showing is that Halts is a wrapper for Simulate.

OK, so the problem is coming from Simulate.

Simulate does not decide the same arguments the same way each time.

It depends on existing values global variables such as buffers of
execution traces.

To meet the conditions of the halting proof, any such globals must be
reset to the same state before Simulate is called.