[Buffy]

Originally Posted by Kriminal99

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

Again, please state why this is a non-trivial assumption.

Stating that it results in infinite regress is not a valid conclusion, so I understand why you try to layer on this as an "additional implied assumption":

Originally Posted by Kriminal99

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.

Although I entertained your assumption that the theorem incorporates this infinite regress, in fact it does not.

The input to H is simply a function and its initial input. There is no mechanism either implied or required that that "input" causes a recursion: that is, if you do use H as its own input, the parameters have no way of knowing that the input is code to be called rather than being data.

Again, realize that the theorem refers specifically to algorithms and not (necessarily) to machines running those algorithms.

Do not bite at the bait of pleasure till you know there is no hook beneath it,
Buffy

[TZK]

Originally Posted by Buffy

Again, please state why this is a non-trivial assumption.

Stating that it results in infinite regress is not a valid conclusion, so I understand why you try to layer on this as an "additional implied assumption":

Although I entertained your assumption that the theorem incorporates this infinite regress, in fact it does not.

The input to H is simply a function and its initial input. There is no mechanism either implied or required that that "input" causes a recursion: that is, if you do use H as its own input, the parameters have no way of knowing that the input is code to be called rather than being data.

Again, realize that the theorem refers specifically to algorithms and not (necessarily) to machines running those algorithms.

Do not bite at the bait of pleasure till you know there is no hook beneath it,
Buffy

Your definition of trivial assumption needs revision badly. A trivial assumption is something that could not possibly be wrong. No proof is ever required to show that an assumption is not trivial, it works the other way around.

<Yawn> The supposed halting machine takes other Touring machines as input. Machines and algorithms are theoretically equivalent, so it doesn't matter which one you talk about. The algorithm can take another algorithm as input. The halting machine/algorithm recognizes it's input as another machine or algorithm. That is it's job. It takes encodings of machines or algorithms and determines if they are going to halt. To say that it can't recognize the encoding as a machine or algorithm directly contradicts it's definition.

Originally Posted by Buffy

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!

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

You seem to be forgetting that Touring started this conversation. The man comes up with an arbitrary manipulation of a supposed halting machine, and then claims that it creates a contradiction such that no such halting machine could occur.

Using this tactic an infinite amount of false "proofs" could be created. For example

1. My mother makes pies with alcohol on sunday's
2. It's illegal to sell alcohol on sundays where my mother lives.
Conclusion: My mother doesn't really make pies with alcohol on sundays since the local law really is against it.

Well, here we have assumed (but not recognized) that the mother couldn't have bought the ingrediants on a different day, a different place, or illegally, one of which is obviously the source of the contradiction. This is the form of proof that Touring has used.

Your claim is that I have to prove that the mother obtains pie ingrediants on different days or in a different place, or illegally . This is incorrect. The proof was faulty to begin with, so I don't need to prove anything.

But here you could say, it is possible to prove it, and since a bunch of non logically discriminating people believe it, perhaps you should. This type of thinking, besides just being wrong, creates a serious problem. It is easy to come up with such a proof where the assumption could not be proven one way or another. Example:

1. My mother died
2. My mother is in a better place.
3. Dying is a terrible thing to happen to someone.
Conclusion: Being in a better place is a terrible thing to happen to someone.

A contradiction has occured so it must be false that dying is a terrible thing to happen to someone or that my mother is in a better place right?

Wrong - I left out the assumption that people continue to exist after dying. This can neither be proven or disproven. It not only invalidates the proof, it makes the "proof" practically nonsense.

[Buffy]

Originally Posted by TZK

Your definition of trivial assumption needs revision badly. A trivial assumption is something that could not possibly be wrong. No proof is ever required to show that an assumption is not trivial, it works the other way around.

Great so you agree with me!

As you say, "No proof is ever required to show that an assumption is not trivial," so of course the halting problem does not!

The problem is, you haven't even proposed a theory, you're trying to disprove it by showing that one of its assumptions is not trivial.

Unfortunately so far, you've only stated that the assumption is not trivial and provided no evidence to support your statement.

Your OP is thus still unsupported and as far as anyone watching this is concerned both irrelevant and uninformed....

Originally Posted by TZK

<Yawn> The supposed halting machine takes other Touring machines as input. Machines and algorithms are theoretically equivalent, so it doesn't matter which one you talk about. The algorithm can take another algorithm as input. The halting machine/algorithm recognizes it's input as another machine or algorithm. That is it's job. It takes encodings of machines or algorithms and determines if they are going to halt. To say that it can't recognize the encoding as a machine or algorithm directly contradicts it's definition.

Nothing I've said and nothing you've proposed indicates that there is even a single case where a proposed Halting Program cannot recognize its encoding as a machine or an algorithm.

For some completely unexplainable reason you've chosen to *complexify* the theorem beyond its definition by insisting on adding a level of indirection by including it.

As you agree in this quote, it is indeed irrelevant, but its still your completely unsupported and quite frankly completely illogical insistence that problems will occur when you give an algorithm itself as input.

Unfortunately in this last post you've continued to demonstrate your lack of understanding of the difference between "giving a program itself as input" and "recursion." I know you have had some training in programming, but you might want to investigate the difference between these two concepts before you continue to discuss this topic.

On a related note, I've gotten several notes from people who have expressed dismay at the fact that the topic of the Halting Problem proof and its implications is so interesting and so ripe for discussion while you've seemingly insisted on simply going off on a tremendously boring "Einstein is wrong" wild goose chase....it might even be interesting if you'd actually respond honestly to our requests for explanation instead of acting like the whole point is to simply create conflict by making "controversial" claims and hoping it causes and argument.

You may consider this a formal warning that you have not bothered to provide any support for your claims, and you're simply annoying our membership with your bad attitude and haughty self-importance.

Though thou canst swim like a duck, thou art made like a goose,
Buffy

[LaurieAG]

Originally Posted by Buffy

Unfortunately in this last post you've continued to demonstrate your lack of understanding of the difference between "giving a program itself as input" and "recursion." I know you have had some training in programming, but you might want to investigate the difference between these two concepts before you continue to discuss this topic.

Hi Buffy, Krim/TZK,

Turing Machine -- from Wolfram MathWorld

A Turing machine consists of a line of cells known as a "tape" that can be moved back and forth, an active element known as the "head" that possesses a property known as "state" and that can change the property known as "color" of the active cell underneath it, and a set of instructions for how the head should modify the active cell and move the tape. At each step, the machine may modify the color of the active cell, change the state of the head, and then move the tape one unit to the left or right.

Out of all the basic parts: states, colors and tapes of colors the tape is the only 'moving' part of a universal Turing machine.

[alexander]

hehe, good link, laurie, time to get started on base 6 computing platform.... hehehe

3 states 2 colors... sounds like a quantum computing device, though there you may not refer to them as colors, but more of polarities or directions... This would be neat for storage, we would tripple the capacity of the same size storage device if we were able to store in it using 6 state qbit system even quadruple with an 8 state qbit system... also access speed would increase, because they would have to accomodate the 8 states, you will now be able to write 4 times more efficiently then with binary over the same speed bus, all those minutes you spent learning octal would not have been spent for nothing

[LaurieAG]

Originally Posted by alexander

3 states 2 colors... sounds like a quantum computing device, though there you may not refer to them as colors, but more of polarities or directions... This would be neat for storage, we would tripple the capacity of the same size storage device if we were able to store in it using 6 state qbit system even quadruple with an 8 state qbit system... also access speed would increase, because they would have to accomodate the 8 states, you will now be able to write 4 times more efficiently then with binary over the same speed bus, all those minutes you spent learning octal would not have been spent for nothing

Hi Alexander,

Unfortunately the relationship between states and colors means that less colors require more states for a Universal Turing Machine.

Universal Turing Machine -- from Wolfram MathWorld

A Turing machine which, by appropriate programming using a finite length of input tape, can act as any Turing machine whatsoever. In his seminal paper, Turing himself gave the first construction for a universal Turing machine (Turing 1937, 1938). Shannon (1956) showed that two colors were sufficient, so long as enough states were used. Minsky (1962) discovered a 7-state 4-color universal Turing machine, illustrated above (Wolfram 2002, p. 706). Note that the 20th rule specifies that the Turing machine should halt, as indicated by leaving the head stationary and not changing its state. Upon conversion to a 2-color machine, Minsky's universal Turing machine requires 43 states.

[Kriminal99]

Originally Posted by Buffy

Great so you agree with me!

As you say, "No proof is ever required to show that an assumption is not trivial," so of course the halting problem does not!

The problem is, you haven't even proposed a theory, you're trying to disprove it by showing that one of its assumptions is not trivial.

Unfortunately so far, you've only stated that the assumption is not trivial and provided no evidence to support your statement.

Your OP is thus still unsupported and as far as anyone watching this is concerned both irrelevant and uninformed....


Nothing I've said and nothing you've proposed indicates that there is even a single case where a proposed Halting Program cannot recognize its encoding as a machine or an algorithm.

For some completely unexplainable reason you've chosen to *complexify* the theorem beyond its definition by insisting on adding a level of indirection by including it.

As you agree in this quote, it is indeed irrelevant, but its still your completely unsupported and quite frankly completely illogical insistence that problems will occur when you give an algorithm itself as input.

Unfortunately in this last post you've continued to demonstrate your lack of understanding of the difference between "giving a program itself as input" and "recursion." I know you have had some training in programming, but you might want to investigate the difference between these two concepts before you continue to discuss this topic.

On a related note, I've gotten several notes from people who have expressed dismay at the fact that the topic of the Halting Problem proof and its implications is so interesting and so ripe for discussion while you've seemingly insisted on simply going off on a tremendously boring "Einstein is wrong" wild goose chase....it might even be interesting if you'd actually respond honestly to our requests for explanation instead of acting like the whole point is to simply create conflict by making "controversial" claims and hoping it causes and argument.

You may consider this a formal warning that you have not bothered to provide any support for your claims, and you're simply annoying our membership with your bad attitude and haughty self-importance.

Though thou canst swim like a duck, thou art made like a goose,
Buffy

So that would mean ( I can see how the logical calculations could get difficult with that many nots) that Touring must prove that a Halting machine definitely would not trace computations of it's input machine for his "proof" to have any bearing on the possible existence of a Halting machine at all. The fact that he is assuming things about something that he wants to claim doesn't exist is a big no - no and a dead give away that something is wrong with the proof in of itself.

I am not doing anything. Touring proposes a logically flawed proof - a proof by contradiction with unrecognized assumptions about that which he tries to prove does not exist. The fact that some people were inept enough logically to accept it does not somehow magically change it's objective truth status.

Your ideas regarding science, math and logic seem to be backwards at best, as you always demonstrate by arguments which implicitly define truth as being whatever the majority of people believe. This type of thinking has no place here.

The notion that I have somehow attempted to "complexify" a completely contrived and invalid proof is laugable at best.

Infinite Recursion occurs when a copy and trace machine runs on itself (it's own encoding for the layman).

When you fail to understand someone else's argument, it does not validate the claim that they somehow failed. This attitude could easily create this situation where you refuse to consider any argument you don't find emotionally convenient and then declare that the argument failed because it didn't make sense to you (as you didn't even look at it properly). Nor can this be resolved by taking some sort of poll of people who share biases with you. The truth is the truth and it is not subject to your whims.

I really don't think anyone is concerned with your silly little warnings or any other form of emotional outburst you may choose to display...

[Buffy]

Originally Posted by Kriminal99

So that would mean...that Touring must prove that a Halting machine definitely would not trace computations of it's input machine for his "proof" to have any bearing on the possible existence of a Halting machine at all.

That's ridiculous!

Just because you choose an algorithm that traces and that does not halt, does not invalidate the proof. What Turing is saying is that there aren't *any* that work!

If you identify a class of programs intended to solve the Halting Problem that by definition do not halt, it has no impact on the whether the theorem is valid.

Nor does it matter that the weaker claim that there exist programs that can solve the Halting Problem as long as they do not try to work on themselves: that's just an alternate theorem that its up to you to prove if you wish.

What you're arguing is somewhat interesting, heck it would be interesting to have a discussion concerning the validity of the assertion "all programs that use a tracing algorithm to determine halting states will not halt," which might even be true!

But as should be clear from the discussion so far, it bears absolutely no relevance in determining the validity of Turing's theorem. Any inability to see this simply comes from a misunderstanding of it.

The last part of your argument simply seems to be that nothing can be proven by contradiction, which would certainly be an interesting philosophical problem to attack, but it should be done in my opinion without the obfuscation of a particular theorem.

Such an approach is, to use your own term, "weak."

Originally Posted by Kriminal99

I am not doing anything.

Well, nothing useful at any rate!

That's exactly what a 4 year old says when being scolded to stop poking his little sister....

Originally Posted by Kriminal99

When you fail to understand someone else's argument, it does not validate the claim that they somehow failed. This attitude could easily create this situation where you refuse to consider any argument you don't find emotionally convenient and then declare that the argument failed because it didn't make sense to you (as you didn't even look at it properly). Nor can this be resolved by taking some sort of poll of people who share biases with you. The truth is the truth and it is not subject to your whims.

Need a mirror?

Originally Posted by Kriminal99

I really don't think anyone is concerned with your silly little warnings or any other form of emotional outburst you may choose to display...

Nor should they! I'm perfectly harmless!

Idealism is fine, but as it approaches reality the cost becomes prohibitive,
Buffy

[Kriminal99]

Originally Posted by Buffy

That's ridiculous!

Just because you choose an algorithm that traces and that does not halt, does not invalidate the proof. What Turing is saying is that there aren't *any* that work!

If you identify a class of programs intended to solve the Halting Problem that by definition do not halt, it has no impact on the whether the theorem is valid.

Nor does it matter that the weaker claim that there exist programs that can solve the Halting Problem as long as they do not try to work on themselves: that's just an alternate theorem that its up to you to prove if you wish.

What you're arguing is somewhat interesting, heck it would be interesting to have a discussion concerning the validity of the assertion "all programs that use a tracing algorithm to determine halting states will not halt," which might even be true!

But as should be clear from the discussion so far, it bears absolutely no relevance in determining the validity of Turing's theorem. Any inability to see this simply comes from a misunderstanding of it.

The last part of your argument simply seems to be that nothing can be proven by contradiction, which would certainly be an interesting philosophical problem to attack, but it should be done in my opinion without the obfuscation of a particular theorem.

Such an approach is, to use your own term, "weak."

Well, nothing useful at any rate!

That's exactly what a 4 year old says when being scolded to stop poking his little sister....

Need a mirror?

Nor should they! I'm perfectly harmless!

Idealism is fine, but as it approaches reality the cost becomes prohibitive,
Buffy

What Turing says is of no interest to anyone, rather only what he can prove is useful. It is claimed that he has proved no Halting machine/algorithm exists, but upon closer inspection it is revealed just to be logical magicianry.

What I have been trying to argue for several pages now is that the setup that Turing proposes in his proof is most likely self contradicting. IE one of his assumptions is A does not equal A, thus trivially creating the contradiction that led him to claim that there is no Halting Machine.

That is he claims there is a halting machine that can be part of a composite machine that includes an input copying machine that then feeds its output to the (inverted) halting machine. This machine is then fed itself as input and then expected to retain it's normal function in order for the proof to hold.

That is, despite this machine being fed it's own encoding, it is expected to still return a result of whether or not the input machine would halt on it's input which was also given. However in this situatiton a Halting Machine would uniquely be unable to provide a proper result - instead it would always loop. It doesn't always loop, just went given it's own encoding.

The machine Turing creates for his proof, if it existed, would have a domain that would exclude it's own encoding. Refering to the fact that the encodingn is just 1's and 0's (or colors or anything else) changes nothing. It is an encoding that the machine is designed to recognize as another machine.

The assumption in Turing's proof by contradiction that this machine would continue to function normally outside of it's domain is absurd and the obvious cause of the contradiction he derives. Thus anyone who believes this as a disproof of the existence of a Halting Machine has been had.

At best I can see that if what I claim truly is the source of the contradiction, there probably exists some proof that a Halting machine has to trace the computatitons of the machine encoding it was given as input. However, a proof precludes the possibillity of any alternative, and Turing's argument does not do this.

[CraigD]

Originally Posted by Kriminal99

That is he claims there is a halting machine that can be part of a composite machine that includes an input copying machine that then feeds its output to the (inverted) halting machine. This machine is then fed itself as input and then expected to retain it's normal function in order for the proof to hold.

That is, despite this machine being fed it's own encoding, it is expected to still return a result of whether or not the input machine would halt on it's input which was also given. However in this situatiton a Halting Machine would uniquely be unable to provide a proper result - instead it would always loop. It doesn't always loop, just went given it's own encoding.

This is not at all what Turing’s 1936 proof of the unsolvability of the halting problem claims.

It claims that a Turing machine K can be created in an specific way by slightly modifying any proposed machine H that is a successful solution of the halting problem, and that when H is provided with an program input of K and a input input of K, either of H’s possible outputs (“halts” or “doesn’t halt”) are incorrect. As H is assumed to be a successful solution to the halting problem, which requires that it eventually halt with one of these two outputs, H must always halt. The proof doesn’t claim that for some pair of inputs H does not halt, it claims that for some pairs of inputs, H’s output must be incorrect. No “input copying machine” is explicitly or implicitly stated in the halting problem or Turing’s proof if its unsolvability.

Originally Posted by Kriminal99

At best I can see that if what I claim truly is the source of the contradiction, there probably exists some proof that a Halting machine has to trace the computatitons of the machine encoding it was given as input.

A successful solution H of the halting problem cannot simulate its program input P program’s processing of its input input I input, because if it did, H would not halt if P with input I did not.

One may be tempted to circumvent this problem by extending P to include not only its state diagram (a Turing machine is synonymous with a state diagram that consists only next states, a character to be outputted to the tape, and a zero or one position movement of the tape depending on previous states and the value of the tape at the read head), put every possible state of its entire tape. This is, however, not allowed, because P must have a finite number of states, while its tape may not be limited in length. No finite state machine P is possible for which a tape with more states that P is not possible. Turing machine are infinite-state machines.

If one restricts the halting problem to finite state machines, it’s possible to create a solution to the halting problem using the above technique. (such a solution, while not difficult, is left as an exercise to the reader) In other words, the halting problem is only unvolvable for infinite state machines.

From you simple misunderstandings of the halting problem, Kriminal99, I suspect that you’ve not had much if any experience writing Turing machines, and think you would benefit from it. Try writing one to do something simple, such as add two numbers (in the base of your choice) appearing on the tape, bound and separated with unique characters, writing the result to the tape, then halting. I suspect if you had the familiarity that comes from exercise of this kind, which are typically in introductory computing theory classes, you would not have the objections you do to Turing’s widely accepted proof.