A UTM halt decider <is> a pure function of its inputs

[olcott]

An at least partial halt decider based on adapting a UTM <is> a pure
function of its inputs.

This adapted UTM would simply simulate the execution of its input until
its input halts on its own or its halt decider determines that its input
would never halt on its own and stops simulating it.

In order for the UTM to see what its input does it must keep track of an
execution trace of its input. This execution trace <is not> another
input it is merely the internal state of the halt decider / UTM.

http://www.liarparadox.org/Halting_problem_undecidability_and_infinite_recursion.pdf


--
Copyright 2021 Pete Olcott

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

[Richard Fateman]

I suggest you find something else to work on. The UTM (universal Turing machine) "Halt Decider" referenced in your essay cannot do what it is supposed to do. Presenting some program, even if it is in assembler, does not "solve" the halting problem. Good luck.

[olcott]

On 3/19/2021 1:35 PM, André G. Isaak wrote:
> On 2021-03-19 11:50, olcott wrote:
>> On 3/19/2021 12:32 PM, André G. Isaak wrote:
>>> On 2021-03-19 10:37, olcott wrote:
>>>> On 3/19/2021 11:16 AM, Richard Damon wrote:
>>>>> On 3/19/21 11:54 AM, olcott wrote:
>>>>>> On 3/19/2021 10:50 AM, Richard Damon wrote:
>>>>>
>>>>>>> If you are building a Halt decider based on the design of a UTM,
>>>>>>> then
>>>>>>> you are going to MODIFY that UTM to add the halt deciding logic
>>>>>>> to it.
>>>>>>> You know only have the Turing Machine H in operation.
>>>>>>>
>>>>>>> In any given computation, when done with Turing Machines, you
>>>>>>> only have
>>>>>>> exactly ONE Turing Machine in operation, not two working together.
>>>>>>>
>>>>>>
>>>>>> Conceptually it is far easier to understand as a pair of pure
>>>>>> functions
>>>>>> hooked together. The UTM derives its execution trace as a pure
>>>>>> function
>>>>>> of its inputs. The halt decider derives a transition to one of two
>>>>>> final
>>>>>> states as a pure function of this execution trace.
>>>>>
>>>>> But that isn't Turing Theory. Note, this combination IS a Turing
>>>>> Machine
>>>>> when seen in total, and it is THAT combined machine that H^ needs
>>>>> to wrap.
>>>>>
>>>>
>>>> Linz has H embedded in H_Hat, not wrapped by H_Hat and Sipser has:
>>>>      Now we construct a new Turing machine D with H as a
>>>>      subroutine. This new TM calls H to determine what M
>>>>      does when the input to M is its own description ⟨M⟩.
>>>>
>>>> It is not the embedding that makes halting undecidable. It is that
>>>> the input does the opposite of whatever the halt decider says that
>>>> it will do that makes halting undecidable.
>>>
>>> Both Linz and Sipser do this in the exact same way. This has been
>>> pointed out to you numerous times.
>>
>> Yes and it is pointed on entirely on the basis of a false assumption
>> that contradict what Sipser actually says.
>
> What exactly is it that Sipser says that you think I am contradicting?
> There is no false assumption here. The problem is that you know
> virtually nothing about Turing Machines, but suffer from an extremely
> bad case of Dunning-Kruger syndrome.
>
> When talking about C or Pascal, a 'subroutine' may be some external
> routine which is called by pushing arguments and a return address onto
> the stack.
>
> When talking about Turing Machines, 'subroutine' simply means some
> subset of the state transitions which define the machine. There is no
> calling mechanism where Turing Machines are concerned, nor any access to
> anything external to the machine itself. Sipser doesn't need to spell
> this out because he assumes people reading him actually know what a
> Turing Machine is. You do not.
>
>>> The problem is that you keep getting hung-up on the word
>>> 'subroutine', which in the Sipser proof means 'embedded copy' just as
>>> in the Linz proof. You cannot use C-based definitions when talking
>>> about Turing Machines. Turing Machines are self-contained
>>> computations. They don't have the ability to call on instructions
>>> contained in an operating system or another Turing Machine.
>>
>> It is not the embedding that makes halting undecidable.
>> It is defining an input that does the opposite of whatever the halt
>> decider that that is will do that is the undecidability basis.
>
> And exactly how is H_Hat supposed to 'know' what H would decide so it
> can show the opposite behaviour without actually performing the
> computation performed by H? The *entire* computation performed by H.
> That requires that it include a complete copy of that computation as
> part of itself since it does not have the ability to call H.

OK so your whole basis in anchored in the notion that a Turing
equivalent machine cannot possibly derive a protocol for a simulated
computation to invoke any functionality of its simulator.

Since I have accomplished this using a very simple subset of the x86
language if this simple subset is RASP equivalent then you are proven
wrong. I really only use sequence / selection / iteration / function
calls and memory access.

The UTM / x86 emulator derives a set of execution traces as a pure
function of its input finite strings.

The halt decider is a pure function of these individual finite string
execution traces.


// This is halting decidable as infinite recursion

void H_Hat(u32 P)
{
u32 Input_Would_Halt = Halts(P, P);
if (Input_Would_Halt)
HERE: goto HERE;
}

int main()
{
u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
Output("Input_Would_Halt = ", Input_Would_Halt);
}


Here is the whole paper explaining the details:

[olcott]

Your words indicate that you certainly were not paying attention.