Halting Undecidability proof faulty?

[Buffy]

Originally Posted by Kriminal99

The fact that the H in the proof is "Touring Complete" means the result is extremely weak.

That's an interesting and unsupported opinion. How do you define "weakness" in this case?

Originally Posted by Kriminal99

There could still be a halting machine that is "Touring - {H} Complete" where H is the halting machine itself.

There could, indeed, there's no reason to believe there is not. This is the fourth time you've been asked to distinguish why this is a special case.

Originally Posted by Kriminal99

Encompassing any Universal machine in a larger machine that also contains a machine capable of copying input causes an infinite regress if that Universal machine attempts to trace the computations of the machine encoding it recieves as input. Why? When it traced the computations it would just start the whole process over again, and make a new copy of the input for the next level of recursion. This is done in the proof.

Well, no it's not done in the proof: You've fallen into the trap that both Craig and I described previously. There's no requirement--although no reason it cannot be done--for the machine itself to be implemented as a level of indirection. That is not implied or necessary in the proof.

But more importantly it does *not* require the machine to do--again as I stated in an earlier post--an infinite recursion on the the inputs to the data, and to say so is to misunderstand what the theorem is saying.

If you want to change the theorem so that it fails, that's not a disproof of the theorem, something that I think that would be obvious to anyone with philosophical training even if they did not understand computer science.

Machines take me by surprise with great frequency,
Buffy

[Kriminal99]

Originally Posted by Buffy

I would hope that your "philosophical knowledge" would alert you to the fact that the phrase "most likely" has no truth-value, and that even if you dropped that qualifier to more explicitly state that "[a halting program's] definition demands that it not be able to operate on itself" requires at least some sort of outline of a proof to show the validity of the statement.

Craig's clarification that "operating on itself" refers to the program as a representation of an algorithm rather than the machine, is a different distinction which I had not considered might be tripping you up, but if this is what you mean by that inability to work on itself--something that's not clear because you still haven't gotten around to telling us anything about why you think this is problematic--then it's important to recognize that as Craig points out, the machine itself is not the subject of the Halting Problem, only the
algorithm is.

You cannot depend on your eyes when your imagination is out of focus,
Buffy

In the part you just quoted, it clearly states that there is no need to prove that a halting machine could not operate on itself because I am only bringing it up to outline the non triviality of Touring's assumption that a halting machine could opereate on itself..

That distinction is irrelevant. The machine is the algorithm and vice versa. Touring machines can do what any algorithm can do, and they can be encoded in a way that any Touring machine or algorithm could operate on them.

[Buffy]

Originally Posted by Kriminal99

In the part you just quoted, it clearly states that there is no need to prove that a halting machine could not operate on itself because I am only bringing it up to outline the non triviality of Touring's assumption that a halting machine could opereate on itself..

So you get to claim its non-trivial just by saying so? Fair enough...

Patriotism is your conviction that this country is superior to all other countries because you were born in it,
Buffy

[Kriminal99]

Originally Posted by Buffy

That's an interesting and unsupported opinion. How do you define "weakness" in this case?

There could, indeed, there's no reason to believe there is not. This is the fourth time you've been asked to distinguish why this is a special case.
Well, no it's not done in the proof: You've fallen into the trap that both Craig and I described previously. There's no requirement--although no reason it cannot be done--for the machine itself to be implemented as a level of indirection. That is not implied or necessary in the proof.

But more importantly it does *not* require the machine to do--again as I stated in an earlier post--an infinite recursion on the the inputs to the data, and to say so is to misunderstand what the theorem is saying.

If you want to change the theorem so that it fails, that's not a disproof of the theorem, something that I think that would be obvious to anyone with philosophical training even if they did not understand computer science.

Machines take me by surprise with great frequency,
Buffy

The signifigance of a Halting machine that works for anything but itself is that the halting problem is generally solvable...

I don't have to change the theorem. The theorem assumes that the machine can operate on itself as part of it's proof by contradiciton. The assumption is non trivial because any Universal Touring machine in this situation would cease it's normal situation and go into an infinite regress if it attempted to trace it's own computation. Thus, by assuming the Halting machine can do what it does in the proof by contradiction, he is saying that it cannot trace the computations of the machine it is fed as input.

[Buffy]

Originally Posted by Kriminal99

The machine is the algorithm and vice versa. Touring machines can do what any algorithm can do, and they can be encoded in a way that any Touring machine or algorithm could operate on them.

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

[Buffy]

Originally Posted by Kriminal99

The assumption is non trivial because any Universal Touring machine in this situation would cease it's normal situation and go into an infinite regress if it attempted to trace it's own computation.

I'll keep repeating: Why?

Remember, your assumption that there would have to be infinite looping of the machine taking input farther than the first "recursion" IS FALSE. That's what the first several posts in this thread are about.

You appear to continue to assume that a halting machine must operate by observing its operation given the input, which is also a false and unnecessary assumption.

You need to get past these issues before your claim has any validity at all.

On my income tax 1040 it says 'Check this box if you are blind.' I wanted to put a check mark about three inches away,
Buffy

[Kriminal99]

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.

[Buffy]

Originally Posted by Kriminal99

The halting problem most definitely DOES involve a machine operating on the encoding of another machine, which it would then trace the computations of.

No, that is an assumption on your part!

Determining the termination of a program can proceed by a deconstruction of the logical structure of the code itself. Or do you have some reason to insist that this is not a possible approach to constructing a Halting Program? If you have no evidence or theory to back up this assertion, its simply an unsupported assumption on your part.

There is nothing in the theorem that requires tracing whatsoever: again you tar the theory for doing exactly what you insist on doing to disprove it!

Not everything that is faced can be changed, but nothing can be changed until it is faced,
Buffy

[Kriminal99]

Originally Posted by Buffy

No, that is an assumption on your part!

Determining the termination of a program can proceed by a deconstruction of the logical structure of the code itself. Or do you have some reason to insist that this is not a possible approach to constructing a Halting Program? If you have no evidence or theory to back up this assertion, its simply an unsupported assumption on your part.

There is nothing in the theorem that requires tracing whatsoever: again you tar the theory for doing exactly what you insist on doing to disprove it!

Not everything that is faced can be changed, but nothing can be changed until it is faced,
Buffy

The only part of that the proof does not explicitly state is the part about tracing the computations. So we are left to wonder how on earth the Halting Machine would operate without tracing the input machine.

But that is irrelevant, and I need not prove that a proposed Halting Machine H such as that in the proof would involve tracing computations. Touring Assumes it doesn't in his proof by contradiction, thus provided the more likely source of the contradiction he derives.

So to recap, the things touring assumes to start with are:

There exists an H

H retains its normal function when operated as part of the constructed machine which is given itself as input.

and by logical consequence of that assumption

H does not trace computations of machines input into it, since doing so in the constructed composite machine would cause an infinite regress that would cease the machines normal function. IE such a machine is outside of it's own domain.

And also many other trivial things or things that he has previously proven that allow him to construct his argument.

These second and third assumptions are by no means trivial, which means he cannot reasonably say that there is no such H upon reaching the contradiction.

[Buffy]

Originally Posted by Kriminal99

The only part of that the proof does not explicitly state is the part about tracing the computations. So we are left to wonder how on earth the Halting Machine would operate without tracing the input machine.

I appreciate that you are left to wonder this, however your inability to conceive of other approaches is not sufficient to make a substantiated claim that this is the only approach, which is exactly what you are doing!

Originally Posted by Kriminal99

But that is irrelevant, and I need not prove that a proposed Halting Machine H such as that in the proof would involve tracing computations. Touring Assumes it doesn't in his proof by contradiction, thus provided the more likely source of the contradiction he derives.

Right, but you did use it as your claim for infinite regress. In order to substantiate your claim you must also prove that non-tracing approaches *also* result in infinite regress...

An undefined problem has an infinite number of solutions,
Buffy