Quote:
Originally Posted by Buffy
A Turing Machine is a tape and a finite state automaton. The algorithm is the encoding on that tape.
Do you understand that distinction?
A Universal Turing Machine is simply a Turing Machine whose Finite State Automaton can implement other Turing Machines. This is in fact how all von Neumann architecture machines--99.999999999999999999999% of all computers today--which do not differentiate between data that is potentially program code. This may be what you're trying to refer to, but this is most definitely not what the Halting Problem is refering to, nor is in necessary.
What is being asked of you is why an algorithm that took itself as input would operate differently than it would when provided other input.
There is no obvious reason why this would be true, but it is fundamental to your argument, but honestly, there's no reason we should take this as "most likely" just on your say so!
We can only see a short distance ahead, but we can see plenty there thats needs to be done, 
Buffy |
What I was pointing out is that we need not waste our time making trivial distinctions between things that are theoretically equivalent.
The halting problem proof most definitely DOES involve this case where a machine copies the input and hands it to a Universal touring machine such that giving the composite machine itself causes a n infinite regress. It is irrelevant how you pose the proof with trivial variations between algorithms encodings of touring machines etc. It is all equivalent, and the same objection arises.
You have asked several times "Why" when the explanation was given in the same block of quoted text. I have also shown that it doesn't matter why, only that it is not a trivial assumption that the machine in the proof can operate on itself. A trivial assumption is something that cannot possibly be false. If you have a "proof" by contradiction with non trivial assumptions other than the one you want to be the source of the contradiction then you haven't proven anything.
But for the 8th or so time, if you create this machine which copies input and then enters it into a universal touring machine that traces the computation of the input machine, and then give as input to the composite machine itself, an infinite regress occurs when the Universal machine part of the composite machine operates and attempts to trace the computation.
As in
Input................Composite machine F
encoding(F) ->...............(C -> U)
C copies the input
U simulates the encoded machine on itself.
F takes it's own encoding, copies it, and gives it to U. U does something and at some point traces the computation of encoding(F) on input encoding(F). This involves copying input encoding(F) then giving it to the encoding of U contained in the encoding of F. It continues tracing by starting the process over again: tracing the U part of the encoding involves doing some stuff and tracing the computation of the input to the U encoding which involves copying and tracing, copying and tracing and so on forever. This is a unique reaction to being given itself as input.
