Halting Undecidability proof faulty?

[Kriminal99]

Ok time to summarize this thread:

 

1) For the vast majority of programs that anyone is actually going to write (especially if they are not number theorists), the halting problem is decidable.

 

2) The so called proof of undecidability (by contradiction) makes use of a very convaluted setup that is not representitive of a program that anyone would actually write.

 

The halting proof diagnolization argument implies an algorithm that simulates an input machine on it's own encoding. This is the realization of "diagonolization". This algorithm takes one input, copies it, and then gives the original input code the copy as input. It must do so in order to ensure that the program runs only on itself. Call this machine G.

 

Because of the fact that the halting algorithm needs algorithm "code" and input to that code, it is necessary that the halting algorithm traces the input machine to some degree. It must be traced a certain amount in order for it to gain meaningful information. I claim that the amount required ensures it would trace it through the action of copying the input and running H in the case of Machine G.

 

So, G recieves (G) as input. (G) is the code of G. G copies the (G) and gives (G)(G) to the halting algorithm. The halting algorithm traces G on (G). And we are back where we started - an infinite loop.

 

 

This infinite trace loop that causes the halting machine to break down is completely unique to this kind of unrealistic setup. It would not even occur if a halting machine ran on itself without the copying preprocessor, because then the trace loop would stop when the input of what to trace ran out.

 

Because undecidability is technically defined such that it is something that is true or not true for ALL machines, theorists maintain that the proof is valid. However, all this proof shows is that the problem is undecidable for the single machine B. For every other machine it says nothing at all.

 

So Undecidable contains one nonsense element, and decidable contains infinite pratical elements. And then there are some more impratical elements to undecidable, which involve things like using a computer program to answer unanswered questions in number theory.

[Buffy]

A halting machine attempting to operate upon itself would cease it's normal function and simply always loop.

 

A function which gives 0 if the input function is defined would cease it's normal function and always loop if operated upon itself.

The Halting Problem requires *both* the function and a *finite* input. If as you suggest, you do an infinite regress of feeding the halting algorithm itself with the input to the algorithm itself, with the input to the algorithm itself, with the input to the algorithm itself, ad nauseum, then you've really only proved the theorem correct!

 

The Halting Problem theorem is only saying that a *general* algorithm cannot be developed that works for *all* function/finite-input pairs. You could feed the algorithm to itself with a *different* finite input, and it would halt. The fact that the infinite regress case does not work simply proves the theorem.

 

So,

Every Halting problem undecidability proof asks us to assume that such functions could operate on themselves.

is not at all an "assumption" its the fact that proves the theorem....

 

People seldom see the halting and painful steps by which the most insignificant success is achieved, :)

Buffy

[Kriminal99]

The Halting Problem requires *both* the function and a *finite* input. If as you suggest, you do an infinite regress of feeding the halting algorithm itself with the input to the algorithm itself, with the input to the algorithm itself, with the input to the algorithm itself, ad nauseum, then you've really only proved the theorem correct!

 

The Halting Problem theorem is only saying that a *general* algorithm cannot be developed that works for *all* function/finite-input pairs. You could feed the algorithm to itself with a *different* finite input, and it would halt. The fact that the infinite regress case does not work simply proves the theorem.

 

So,

 

is not at all an "assumption" its the fact that proves the theorem....

 

People seldom see the halting and painful steps by which the most insignificant success is achieved, :naughty:

Buffy

 

Aww isn't that cute... I didn't say anything about feeding it anything infinite. I said that any halting machine which was fed a finite encoding of itself would cause an infinite regress instead of going through it's normal function.

 

Thus the only thing proven is that it cannot operate on itself. It could still very well exist and handle all other machine/input combos.

[Buffy]

Aww isn't that cute... I didn't say anything about feeding it anything infinite. I said that any halting machine which was fed a finite encoding of itself would cause an infinite regress instead of going through it's normal function.

That's what I said too! And yes, its very cute! :shrug:

 

The program itself is of finite length. It's input is itself, but the only way to get "infinite regress" is to apply the input to the input to the input, each discrete input is indeed finite, and that's what you appeared to be talking about. Without this, there's no possibility for "infinite regress."

 

There's nothing special about the nature of a Halting Problem Program: it's just an arbitrary algorithm. Saying that *by definition* feeding a Halting Problem Program to itself would cause infinite regress does not really make any sense without making lots of assumptions about what makes up such a program. You'll need to explain what you're talking about in more detail to get past this issue.

 

Thus the only thing proven is that it cannot operate on itself. It could still very well exist and handle all other machine/input combos.

What is clear is that:

1. If your assumption that no Halting Problem Program can resolve its own halting status for itself, then the theorem is by definition proven. Your assumption is that it never completes, then it's halting status is undecidable, showing that there's at least one instance of an algorithm that is not decidable.
   
2. You could even circumscribe the recursive case, and you can still prove that the halting problem is undecidable: Your assumption that "Every Halting problem undecidability proof asks us to assume that such functions could operate on themselves" is actually not the case, heck the proof in the Wikipedia page on the topic doesn't make this assumption, and there are other approaches as well. So its actually unnecessary to make this exception.
   

 

If you'd like to take a stab at the notion that all Halting Problem Programs result in infinite regress or otherwise do not halt given themselves as input, we might have an interesting discussion, but you need to prove it: its not true by definition.

 

But even then, it does not have any impact on whether or not the Halting Problem Theorem is false.

 

Not to see many things, not to hear them, not to let them approach one--first piece of ingenuity, first proof that one is no accident but a necessity, :naughty:

Buffy

[Kriminal99]

That's what I said too! And yes, its very cute! :shrug:

 

The program itself is of finite length. It's input is itself, but the only way to get "infinite regress" is to apply the input to the input to the input, each discrete input is indeed finite, and that's what you appeared to be talking about. Without this, there's no possibility for "infinite regress."

 

There's nothing special about the nature of a Halting Problem Program: it's just an arbitrary algorithm. Saying that *by definition* feeding a Halting Problem Program to itself would cause infinite regress does not really make any sense without making lots of assumptions about what makes up such a program. You'll need to explain what you're talking about in more detail to get past this issue.

 

 

What is clear is that:

1. If your assumption that no Halting Problem Program can resolve its own halting status for itself, then the theorem is by definition proven. Your assumption is that it never completes, then it's halting status is undecidable, showing that there's at least one instance of an algorithm that is not decidable.
   
2. You could even circumscribe the recursive case, and you can still prove that the halting problem is undecidable: Your assumption that "Every Halting problem undecidability proof asks us to assume that such functions could operate on themselves" is actually not the case, heck the proof in the Wikipedia page on the topic doesn't make this assumption, and there are other approaches as well. So its actually unnecessary to make this exception.
   

 

If you'd like to take a stab at the notion that all Halting Problem Programs result in infinite regress or otherwise do not halt given themselves as input, we might have an interesting discussion, but you need to prove it: its not true by definition.

 

But even then, it does not have any impact on whether or not the Halting Problem Theorem is false.

 

Not to see many things, not to hear them, not to let them approach one--first piece of ingenuity, first proof that one is no accident but a necessity, :naughty:

Buffy

 

 

I do not have to prove that this would happen - that it is not true is an assumption that the undecidability proof makes. And therefore it is just as likely if not more likely to be the cause of the contradiction that results.

 

IE if there exists a halting machine H that always loops if run on itself but otherwise works, the halting problem is still possibly decidable except for halting machines. Which is very likely a trivial distinction from the idea that the halting problem is possibly solvable.

 

That being said there is pretty good reason to believe that such an infinite regress really would occur. Any halting machine run on itself would at some point try to trace at least a part of its own computations - at which point it would redo everything it had done up to that point when it would again restart and so forth. Each time it would be tracing an additional level of depth.

 

The wikipedia "proof" does assume that the g function could operate on itself. Note where it says that the function g corresponding to the halting problem is the eth possible input to the halting function. It's asking us to run:

 

g(g()), which tests h(g(),g())

 

So here g traces it's own computation creating the same infinite regress.

[Buffy]

If you'd like to take a stab at the notion that all Halting Problem Programs result in infinite regress or otherwise do not halt given themselves as input, we might have an interesting discussion, but you need to prove it: its not true by definition.

I do not have to prove that this would happen - that it is not true is an assumption that the undecidability proof makes. And therefore it is just as likely if not more likely to be the cause of the contradiction that results.

Yes you do. The theorem makes no assumption of that the Halting Problem Program must use itself as input.

The wikipedia "proof" not only assumes that both involved functions could operate on themselves, they do not specify a finite input as you seemed to require. Note where it says that the function g corresponding to the halting problem is the eth possible input to the halting function. It's asking us to run:

 

g(g()), which tests h(g(),g(?))

But that's not a requirement for the proof! The core of the proof is simply that the f() algorithm is different from h() .

 

For your argument to disprove the theorem, you need to demonstrate why Halting Problem Programs are somehow different than any other algorithm in a fundamental way.

 

That the operation is "recursive" is of no consequence: an algorithm is an algorithm. There's no special effect on *any* algorithm simply because it takes itself as input. That's quite non-sensical.

 

In other words:

IE if there exists a halting machine H that always loops if run on itself but otherwise works, the halting problem is still possibly decidable except for halting machines. Which is very likely a trivial distinction from the idea that the halting problem is possibly solvable.

Yes, it's not only trivial because you've simply assumed that there is such an algorithm, it's more than insufficient in showing any sort of weakness in the proof.

That being said there is pretty good reason to believe that such an infinite regress really would occur. Any halting machine run on itself would at some point try to trace at least a part of its own computations - at which point it would redo everything it had done up to that point when it would again restart and so forth. Each time it would be tracing an additional level of depth.

Why are you making assumptions about what a halting machine would do? Isn't that the very charge that you are laying against the proof?

 

Why should your argument--for which you are providing no evidence or logic at all--be taken at face value when that is the very weakness you're--quite incorrectly--accusing the theorem of doing?

 

Human speech is like a cracked kettle on which we tap crude rhythms for bears to dance to, while we long to make music that will melt the stars,

Buffy

[Kriminal99]

Yes you do. The theorem makes no assumption of that the Halting Problem Program must use itself as input.

But that's not a requirement for the proof! The core of the proof is simply that the f() algorithm is different from h() .

 

For your argument to disprove the theorem, you need to demonstrate why Halting Problem Programs are somehow different than any other algorithm in a fundamental way.

 

That the operation is "recursive" is of no consequence: an algorithm is an algorithm. There's no special effect on *any* algorithm simply because it takes itself as input. That's quite non-sensical.

 

In other words:

 

Yes, it's not only trivial because you've simply assumed that there is such an algorithm, it's more than insufficient in showing any sort of weakness in the proof.

 

Why are you making assumptions about what a halting machine would do? Isn't that the very charge that you are laying against the proof?

 

Why should your argument--for which you are providing no evidence or logic at all--be taken at face value when that is the very weakness you're--quite incorrectly--accusing the theorem of doing?

 

Human speech is like a cracked kettle on which we tap crude rhythms for bears to dance to, while we long to make music that will melt the stars, :confused:

Buffy

 

In a proof by contradiction, you don't have to explicitly state that you are making an assumption. Any logical assumption you make, whether you recognize it or not, can be the cause of the contradiction.

 

The proof assumes that the halting machine can operate on itself, by operating the machine on itself during the course of the proof and assuming it behaves as it normally would.

 

It isn't an issue of disproving the "proof". "proofs" make assertions, and this assertion either fails due to a logical oversight, or if you simply define the halting machine in the proof to be able to operate on itself then it proves nothing more than that there can be no halting machine that operates normally on itself. There could still be one that doesn't work on itself.

 

The fact that my philosophical knowledge alerts me to the fact that it's definition most likely demands that it not be able to operate on itself is not required for the above reasoning.

[CraigD]

The proof assumes that the halting machine can operate on itself, by operating the machine on itself during the course of the proof and assuming it behaves as it normally would.

The halting problem explicitly asks if there exists a program H that can accept as input two data: the enumerated description a program, and that program’s data. The problem places no restriction on the size of value of these data, (other than that they are finite, since obviously we can show that H can’t output its required value of “halts” or “doesn’t halt” if it can never stop reading its input) so both inputs being the description of H is a direct consequence of the lack of a restriction prohibiting it.

 

Turing’s 1936 proof of the undecidability of the halting problem does not have the input to H be exactly H, but be H with a specific change to the so that H does not always halt (the following link’s illustration labels this program K). Since H by definition must halt with an output of “halts” or “doesn’t halt”, this change is essential to his proof. this textbook excerpt has a terse, illustrated summary of Turing’s proof.

 

If we change the question to explicitly prohibit inputs to H of description of modified versions of itself, we would have a new problem, as there are an arbitrarily large number of possible K’s. K’s need not be constructed as suggested by the illustrations – they could be entirely different programs, so long as they produced the same output. The problem would now require the answer of another problem, “is it possible for a program R to always halt with the output “like me” when inputted the description of a program that always halts with the same output it would halt with given the same data, and “not like me” when it does not.

 

If we change the question to explicitly program description and data inputs from being the same, we would again be faced with the “like me” problem, as for this to be effective, not only data inputs identical to program inputs would need to be prohibited, but “like” ones as well.

In a proof by contradiction, you don't have to explicitly state that you are making an assumption. Any logical assumption you make, whether you recognize it or not, can be the cause of the contradiction.

Turing’s halting problem proof is not, upon careful inspection, a proof by contradiction. It does not start with the assumption that a successful H exists, and show that this contradicts some proven or a-priori theorem. Rather, it is a disproof by counterexample. It shows that for any possible candidate H, a K can be built for which it fails. It provides a specific approach for generating K for any H.

 

Also, I’m unsure that Krim is using the term “proof by contradiction” in a conventional sense. Such a proof must state its assumed-true assertion, or it simply isn’t a this type of proof.

The proof assumes that the halting machine can operate on itself, by operating the machine on itself during the course of the proof and assuming it behaves as it normally would.

The halting problem explicitly requires that all programs can be enumerated, and described in the form of input data. Because it explicitly requires that the programs described in it are Turing-complete, it requires only one actual machine, which is either a universal Turing machine running the program of H, a special purpose Turing machine H, or any machine proven equivalent to one of these Turing machines. No machine actually works on another machine: it works on data describing other machines.

[Buffy]

The fact that my philosophical knowledge alerts me to the fact that it's definition most likely demands that it not be able to operate on itself is not required for the above reasoning.

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, :confused:

Buffy

[Kriminal99]

The halting problem explicitly asks if there exists a program H that can accept as input two data: the enumerated description a program, and that program’s data. The problem places no restriction on the size of value of these data, (other than that they are finite, since obviously we can show that H can’t output its required value of “halts” or “doesn’t halt” if it can never stop reading its input) so both inputs being the description of H is a direct consequence of the lack of a restriction prohibiting it.

 

Turing’s 1936 proof of the undecidability of the halting problem does not have the input to H be exactly H, but be H with a specific change to the so that H does not always halt (the following link’s illustration labels this program K). Since H by definition must halt with an output of “halts” or “doesn’t halt”, this change is essential to his proof. this textbook excerpt has a terse, illustrated summary of Turing’s proof.

 

If we change the question to explicitly prohibit inputs to H of description of modified versions of itself, we would have a new problem, as there are an arbitrarily large number of possible K’s. K’s need not be constructed as suggested by the illustrations – they could be entirely different programs, so long as they produced the same output. The problem would now require the answer of another problem, “is it possible for a program R to always halt with the output “like me” when inputted the description of a program that always halts with the same output it would halt with given the same data, and “not like me” when it does not.

 

If we change the question to explicitly program description and data inputs from being the same, we would again be faced with the “like me” problem, as for this to be effective, not only data inputs identical to program inputs would need to be prohibited, but “like” ones as well. Turing’s halting problem proof is not, upon careful inspection, a proof by contradiction. It does not start with the assumption that a successful H exists, and show that this contradicts some proven or a-priori theorem. Rather, it is a disproof by counterexample. It shows that for any possible candidate H, a K can be built for which it fails. It provides a specific approach for generating K for any H.

 

Also, I’m unsure that Krim is using the term “proof by contradiction” in a conventional sense. Such a proof must state its assumed-true assertion, or it simply isn’t a this type of proof. The halting problem explicitly requires that all programs can be enumerated, and described in the form of input data. Because it explicitly requires that the programs described in it are Turing-complete, it requires only one actual machine, which is either a universal Turing machine running the program of H, a special purpose Turing machine H, or any machine proven equivalent to one of these Turing machines. No machine actually works on another machine: it works on data describing other machines.

 

The fact that the H in the proof is "Touring Complete" means the result is extremely weak. There could still be a halting machine that is "Touring - {H} Complete" where H is the halting machine itself.

 

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. It doesn't matter how many K's there are, since it's the entire class that causes the problem.

 

I don't need to assume that H traces the computations of it's input, because I am not the one proposing a proof. Rather Touring's proof assumes that H can function on itself and still do what it is supposed to, when it is very likely that an H by it's very definition could not operate on itself. You can trivially dodge this by simply defining H to be able to operate on itself, but then you cannot sell the result as a proof that the Halting Problem cannot be decided. The removal of H from the set for which the problem is decidable is not very signifigant, much can still be accomplished by solving the problem for everything else.

 

The proofs absolutely are done by contradiction and not counterexample. You cannot counter example the possibility of existance of any halting machine. That doesn't make any sense. A counter example is just the opposite - when someone says "This always is the case" or "This cannnot be ever" (ie uses a universal quantifier) you only need one counter example to disprove their claim.

 

Touring starts by assuming there is a Halting decider H, assumes some other things, and then derives contradictions from the set of assumptions. When you say "possible candidate H", it means assume there is such an H. This is called a proof by contradiction.

 

And it only proves that a certain assumption is false if you are certain that all other assumptions, both recognized and unrecognized are not false. In this case there is no reason to trust the assumption that a Halting machine is in it's own domain.

[Buffy]

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?

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.

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, :shrug:

Buffy

[Kriminal99]

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]

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]

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]

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]

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]

;)

 

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.