Halting Undecidability proof faulty?

[Buffy]

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]

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]

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!

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

[Buffy]

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":

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]

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

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.

 

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

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]

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....

 

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

Buffy

[LaurieAG]

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 :Glasses:

[LaurieAG]

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]

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

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]

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."

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....

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? :)

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! :phones:

 

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

Buffy

[Kriminal99]

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]

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.

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.

[Kriminal99]

So, the depcition I have created is one frequently used to describe the Halting undecidability proof in more detail. At first glance one might come to the mistaken conclusion that the strict diagonalization proof might be different from this depiction. Actually the depiction is a more explicit demonstration of what is happening in the diagonalizatiton proof. For instance, if you say machine G takes Machine H on input encoding of Machine H as input, then you have implicitly created the copy Machine referenced in the above depiction.

 

Furthermore, your claim regarding program tracing is incorrect. For a Halting (or even Universal Turing Machine) that partially traces the computations of it's input encoding, it is not necessary that the machine completely trace the computations. It could for example stop when any loop has occured by comparing the current state with any previously obtained state. Perhaps if you had more experience working with theoretical touring machines, you would know this.

 

However attempting to trace it at all is enough to create the infinite regress in the setup Touring has implicitly provided.

 

I find it amusing that you attempt to attribute the blind obedience that is a direct result of social pressures to the working of simple problems in a university setting. If a student in a "introductory computer science class" objected in any way to the presented proof, the professor would just declare by fiat his grade to be an F either directly or through concealed logic errors in grading. This not only means that the student would keep quiet if something did appear to be off, it also means he would not bother to think about it to the degree required to notice anything "fishy".

 

You then want to look at this abuse of power as some sort of evidence that the proof is widely accepted. This is bandwagon fallacy of the simplest form. If everyone agrees solely because everyone agrees, then nobody really knows.

 

Thus he who finally has an objection is truly dealing only with the person in ancient histotry who originally presented the idea, and maybe some peers of that time who could see no error with it. Thre is no reason to believe anyone after that who is under social pressure to conform has subjected it to an appropriate amount of skepticism.

[Buffy]

Furthermore, your claim regarding program tracing is incorrect. For a Halting (or even Universal Turing Machine) that partially traces the computations of it's input encoding, it is not necessary that the machine completely trace the computations. It could for example stop when any loop has occured by comparing the current state with any previously obtained state. Perhaps if you had more experience working with theoretical touring machines, you would know this.

First you claim that it does need to trace and then that it doesn't need to trace.

 

Are you going to decide, or are you going to endlessly change your position in a somewhat transparent effort to create conflict?

 

Perhaps if you had more experience in working with programming languages and parser construction you would understand how silly either side of what you're arguing is.

 

The absurdity of your claims on this particular topic is of course true no matter whether you're discussing Turing Machines or your Calvinball-like "Touring Machines" (how many gears does that have?)

I find it amusing that you attempt to attribute the blind obedience that is a direct result of social pressures to the working of simple problems in a university setting. If a student in a "introductory computer science class" objected in any way to the presented proof, the professor would just declare by fiat his grade to be an F either directly or through concealed logic errors in grading.

So finally we get to the autobiographical part of the thread, and your somewhat transparent intent in your original post.

 

I know lots of teachers and professors, and the vast majority actually love questions like this: it's exactly why they became teachers in the first place. At the same time, there are certain students who's intent is not to learn but to disrupt the class in order to prove that they are in control by incessantly questioning every conceivable assumption that is taken in the presentation of material.

 

In an "Introductory" class, such behavior goes from an opportunity to let everyone learn into a battle of wills between a student who cares only about inflating their own ego by "showing that professor that he's just stuck in old ways of thinking."

 

In a University of course, a professor does not have the option of sending you to the chancellor for a spanking, so in some cases, yes, a bad grade is in return for actually disrupting the class and selfishly stealing costly class time from the other students. So, in that respect, such grading tactics are indeed quite logical.

 

I find it highly likely given your "debating tactics" in this thread that you've run into that constantly in your life.

 

How's that workin' for ya?

 

Even paranoids have real enemies, :phones:

Buffy

[CraigD]

So, the depcition I have created is one frequently used to describe the Halting undecidability proof in more detail.

:QuestionM :phones: Can you provide a link to such a description? A google search of ‘+“copy machine” +halting’ finds in its first pages only this thread and some references in which “copy machine” and the halting problem appear in unrelated discussions.

I find it amusing that you attempt to attribute the blind obedience that is a direct result of social pressures to the working of simple problems in a university setting.

I attempted nothing of the kind. I stated:

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.

In short, I asked you to perform a simple exercise, coincidentally one that appeared in the chapter on Turing machines of the textbook I used in my only for-academic-credit class on computing theory.

 

No blind obedience or bowing to social pressure or authority is required, nor more adherence to convention than necessary to be understood by a reader familiar with Turing machines. All I’ve asked for a Turing machine that adds 2 numbers, written in any of the various conventional ways, such as table with 5 column containing “old state”, “old tape symbol”, “new tape symbol”, “tape movement”, and “new state”, or an equivalent (number of states) by (number of symbols) by 3 table, or state diagram sketch. Here’s an example for the problem I gave:

Old	Old	New		New
State	Tape	Tape	Move	State
0	a		R	10
1	a		R	11
10	0	a	R	20
1	a	R	21
d	a	R	20d
11	0	a	R	21
1	a	R	22
d	a	R	21
20	b	d	R	30
c		L	40
else		R	20
20d	b	d	R	30d
c		L	STOP
else		R	20d
21	b	d	R	31
c		L	41
else		R	21
22	b	d	R	32
c		L	42
else		R	22
30	0	b	L	40
1	b	L	41
c		L	40
30d	0	b	L	40d
1	b	L	41d
c		L	STOP
31	0	b	L	41
1	b	L	42
c		L	41
31d	0	b	L	41
1	b	L	42
c		L	41
32	0	b	L	42
1	b	L	43
c		L	42
40	a		L	50
else		L	40
41	a		L	51
else		L	41
42	a		L	52
else		L	42
43	a		L	53
else		L	43
50		0	R	0
51		1	R	0
52		0	R	1
53		1	R	1

That adds 2 base 2 numbers. Here’re its states running it on a sample tape:

a|0|1|1|1|b|1|1|1|0|1|1|0|0|1|1|c
0
a|0|1|1|1|b|1|1|1|0|1|1|0|0|1|1|c
 10
a|a|1|1|1|b|1|1|1|0|1|1|0|0|1|1|c
   20
a|a|1|1|1|b|1|1|1|0|1|1|0|0|1|1|c
     20
a|a|1|1|1|b|1|1|1|0|1|1|0|0|1|1|c
       20
a|a|1|1|1|b|1|1|1|0|1|1|0|0|1|1|c
         20
a|a|1|1|1|d|1|1|1|0|1|1|0|0|1|1|c
           30
a|a|1|1|1|d|b|1|1|0|1|1|0|0|1|1|c
         41
a|a|1|1|1|d|b|1|1|0|1|1|0|0|1|1|c
       41
a|a|1|1|1|d|b|1|1|0|1|1|0|0|1|1|c
     41
a|a|1|1|1|d|b|1|1|0|1|1|0|0|1|1|c
   41
a|a|1|1|1|d|b|1|1|0|1|1|0|0|1|1|c
 41
a|a|1|1|1|d|b|1|1|0|1|1|0|0|1|1|c
51
1|a|1|1|1|d|b|1|1|0|1|1|0|0|1|1|c
 0
1|a|1|1|1|d|b|1|1|0|1|1|0|0|1|1|c
   10
1|a|a|1|1|d|b|1|1|0|1|1|0|0|1|1|c
     21
1|a|a|1|1|d|b|1|1|0|1|1|0|0|1|1|c
       21
1|a|a|1|1|d|b|1|1|0|1|1|0|0|1|1|c
         21
1|a|a|1|1|d|b|1|1|0|1|1|0|0|1|1|c
           21
1|a|a|1|1|d|d|1|1|0|1|1|0|0|1|1|c
             31
1|a|a|1|1|d|d|b|1|0|1|1|0|0|1|1|c
           42
1|a|a|1|1|d|d|b|1|0|1|1|0|0|1|1|c
         42
1|a|a|1|1|d|d|b|1|0|1|1|0|0|1|1|c
       42
1|a|a|1|1|d|d|b|1|0|1|1|0|0|1|1|c
     42
1|a|a|1|1|d|d|b|1|0|1|1|0|0|1|1|c
   42
1|a|a|1|1|d|d|b|1|0|1|1|0|0|1|1|c
 52
1|0|a|1|1|d|d|b|1|0|1|1|0|0|1|1|c
   1
1|0|a|1|1|d|d|b|1|0|1|1|0|0|1|1|c
     11
1|0|a|a|1|d|d|b|1|0|1|1|0|0|1|1|c
       22
1|0|a|a|1|d|d|b|1|0|1|1|0|0|1|1|c
         22
1|0|a|a|1|d|d|b|1|0|1|1|0|0|1|1|c
           22
1|0|a|a|1|d|d|b|1|0|1|1|0|0|1|1|c
             22
1|0|a|a|1|d|d|d|1|0|1|1|0|0|1|1|c
               32
1|0|a|a|1|d|d|d|b|0|1|1|0|0|1|1|c
             43
1|0|a|a|1|d|d|d|b|0|1|1|0|0|1|1|c
           43
1|0|a|a|1|d|d|d|b|0|1|1|0|0|1|1|c
         43
1|0|a|a|1|d|d|d|b|0|1|1|0|0|1|1|c
       43
1|0|a|a|1|d|d|d|b|0|1|1|0|0|1|1|c
     43
1|0|a|a|1|d|d|d|b|0|1|1|0|0|1|1|c
   53
1|0|1|a|1|d|d|d|b|0|1|1|0|0|1|1|c
     1
1|0|1|a|1|d|d|d|b|0|1|1|0|0|1|1|c
       11
1|0|1|a|a|d|d|d|b|0|1|1|0|0|1|1|c
         22
1|0|1|a|a|d|d|d|b|0|1|1|0|0|1|1|c
           22
1|0|1|a|a|d|d|d|b|0|1|1|0|0|1|1|c
             22
1|0|1|a|a|d|d|d|b|0|1|1|0|0|1|1|c
               22
1|0|1|a|a|d|d|d|d|0|1|1|0|0|1|1|c
                 32
1|0|1|a|a|d|d|d|d|b|1|1|0|0|1|1|c
               42
1|0|1|a|a|d|d|d|d|b|1|1|0|0|1|1|c
             42
1|0|1|a|a|d|d|d|d|b|1|1|0|0|1|1|c
           42
1|0|1|a|a|d|d|d|d|b|1|1|0|0|1|1|c
         42
1|0|1|a|a|d|d|d|d|b|1|1|0|0|1|1|c
       42
1|0|1|a|a|d|d|d|d|b|1|1|0|0|1|1|c
     52
1|0|1|0|a|d|d|d|d|b|1|1|0|0|1|1|c
       1
1|0|1|0|a|d|d|d|d|b|1|1|0|0|1|1|c
         11
1|0|1|0|a|a|d|d|d|b|1|1|0|0|1|1|c
           21
1|0|1|0|a|a|d|d|d|b|1|1|0|0|1|1|c
             21
1|0|1|0|a|a|d|d|d|b|1|1|0|0|1|1|c
               21
1|0|1|0|a|a|d|d|d|b|1|1|0|0|1|1|c
                 21
1|0|1|0|a|a|d|d|d|d|1|1|0|0|1|1|c
                   31
1|0|1|0|a|a|d|d|d|d|b|1|0|0|1|1|c
                 42
1|0|1|0|a|a|d|d|d|d|b|1|0|0|1|1|c
               42
1|0|1|0|a|a|d|d|d|d|b|1|0|0|1|1|c
             42
1|0|1|0|a|a|d|d|d|d|b|1|0|0|1|1|c
           42
1|0|1|0|a|a|d|d|d|d|b|1|0|0|1|1|c
         42
1|0|1|0|a|a|d|d|d|d|b|1|0|0|1|1|c
       52
1|0|1|0|0|a|d|d|d|d|b|1|0|0|1|1|c
         1
1|0|1|0|0|a|d|d|d|d|b|1|0|0|1|1|c
           11
1|0|1|0|0|a|a|d|d|d|b|1|0|0|1|1|c
             21
1|0|1|0|0|a|a|d|d|d|b|1|0|0|1|1|c
               21
1|0|1|0|0|a|a|d|d|d|b|1|0|0|1|1|c
                 21
1|0|1|0|0|a|a|d|d|d|b|1|0|0|1|1|c
                   21
1|0|1|0|0|a|a|d|d|d|d|1|0|0|1|1|c
                     31
1|0|1|0|0|a|a|d|d|d|d|b|0|0|1|1|c
                   42
1|0|1|0|0|a|a|d|d|d|d|b|0|0|1|1|c
                 42
1|0|1|0|0|a|a|d|d|d|d|b|0|0|1|1|c
               42
1|0|1|0|0|a|a|d|d|d|d|b|0|0|1|1|c
             42
1|0|1|0|0|a|a|d|d|d|d|b|0|0|1|1|c
           42
1|0|1|0|0|a|a|d|d|d|d|b|0|0|1|1|c
         52
1|0|1|0|0|0|a|d|d|d|d|b|0|0|1|1|c
           1
1|0|1|0|0|0|a|d|d|d|d|b|0|0|1|1|c
             11
1|0|1|0|0|0|a|a|d|d|d|b|0|0|1|1|c
               21
1|0|1|0|0|0|a|a|d|d|d|b|0|0|1|1|c
                 21
1|0|1|0|0|0|a|a|d|d|d|b|0|0|1|1|c
                   21
1|0|1|0|0|0|a|a|d|d|d|b|0|0|1|1|c
                     21
1|0|1|0|0|0|a|a|d|d|d|d|0|0|1|1|c
                       31
1|0|1|0|0|0|a|a|d|d|d|d|b|0|1|1|c
                     41
1|0|1|0|0|0|a|a|d|d|d|d|b|0|1|1|c
                   41
1|0|1|0|0|0|a|a|d|d|d|d|b|0|1|1|c
                 41
1|0|1|0|0|0|a|a|d|d|d|d|b|0|1|1|c
               41
1|0|1|0|0|0|a|a|d|d|d|d|b|0|1|1|c
             41
1|0|1|0|0|0|a|a|d|d|d|d|b|0|1|1|c
           51
1|0|1|0|0|0|1|a|d|d|d|d|b|0|1|1|c
             0
1|0|1|0|0|0|1|a|d|d|d|d|b|0|1|1|c
               10
1|0|1|0|0|0|1|a|a|d|d|d|b|0|1|1|c
                 20d
1|0|1|0|0|0|1|a|a|d|d|d|b|0|1|1|c
                   20d
1|0|1|0|0|0|1|a|a|d|d|d|b|0|1|1|c
                     20d
1|0|1|0|0|0|1|a|a|d|d|d|b|0|1|1|c
                       20d
1|0|1|0|0|0|1|a|a|d|d|d|d|0|1|1|c
                         30d
1|0|1|0|0|0|1|a|a|d|d|d|d|b|1|1|c
                       40
1|0|1|0|0|0|1|a|a|d|d|d|d|b|1|1|c
                     40
1|0|1|0|0|0|1|a|a|d|d|d|d|b|1|1|c
                   40
1|0|1|0|0|0|1|a|a|d|d|d|d|b|1|1|c
                 40
1|0|1|0|0|0|1|a|a|d|d|d|d|b|1|1|c
               40
1|0|1|0|0|0|1|a|a|d|d|d|d|b|1|1|c
             50
1|0|1|0|0|0|1|0|a|d|d|d|d|b|1|1|c
               0
1|0|1|0|0|0|1|0|a|d|d|d|d|b|1|1|c
                 10
1|0|1|0|0|0|1|0|a|a|d|d|d|b|1|1|c
                   20d
1|0|1|0|0|0|1|0|a|a|d|d|d|b|1|1|c
                     20d
1|0|1|0|0|0|1|0|a|a|d|d|d|b|1|1|c
                       20d
1|0|1|0|0|0|1|0|a|a|d|d|d|b|1|1|c
                         20d
1|0|1|0|0|0|1|0|a|a|d|d|d|d|1|1|c
                           30d
1|0|1|0|0|0|1|0|a|a|d|d|d|d|b|1|c
                         41
1|0|1|0|0|0|1|0|a|a|d|d|d|d|b|1|c
                       41
1|0|1|0|0|0|1|0|a|a|d|d|d|d|b|1|c
                     41
1|0|1|0|0|0|1|0|a|a|d|d|d|d|b|1|c
                   41
1|0|1|0|0|0|1|0|a|a|d|d|d|d|b|1|c
                 41
1|0|1|0|0|0|1|0|a|a|d|d|d|d|b|1|c
               51
1|0|1|0|0|0|1|0|1|a|d|d|d|d|b|1|c
                 0
1|0|1|0|0|0|1|0|1|a|d|d|d|d|b|1|c
                   10
1|0|1|0|0|0|1|0|1|a|a|d|d|d|b|1|c
                     20d
1|0|1|0|0|0|1|0|1|a|a|d|d|d|b|1|c
                       20d
1|0|1|0|0|0|1|0|1|a|a|d|d|d|b|1|c
                         20d
1|0|1|0|0|0|1|0|1|a|a|d|d|d|b|1|c
                           20d
1|0|1|0|0|0|1|0|1|a|a|d|d|d|d|1|c
                             30d
1|0|1|0|0|0|1|0|1|a|a|d|d|d|d|b|c
                           41
1|0|1|0|0|0|1|0|1|a|a|d|d|d|d|b|c
                         41
1|0|1|0|0|0|1|0|1|a|a|d|d|d|d|b|c
                       41
1|0|1|0|0|0|1|0|1|a|a|d|d|d|d|b|c
                     41
1|0|1|0|0|0|1|0|1|a|a|d|d|d|d|b|c
                   41
1|0|1|0|0|0|1|0|1|a|a|d|d|d|d|b|c
                 51
1|0|1|0|0|0|1|0|1|1|a|d|d|d|d|b|c
                   0
1|0|1|0|0|0|1|0|1|1|a|d|d|d|d|b|c
                     10
1|0|1|0|0|0|1|0|1|1|a|a|d|d|d|b|c
                       20d
1|0|1|0|0|0|1|0|1|1|a|a|d|d|d|b|c
                         20d
1|0|1|0|0|0|1|0|1|1|a|a|d|d|d|b|c
                           20d
1|0|1|0|0|0|1|0|1|1|a|a|d|d|d|b|c
                             20d
1|0|1|0|0|0|1|0|1|1|a|a|d|d|d|d|c
                               30d
1|0|1|0|0|0|1|0|1|1|a|a|d|d|d|d|c
                             STOP

This isn’t a particularly ingenious Turing machine, just one that performs the requested computation, and was easy to write. It doesn’t address the halting problem. It’s only a demonstration that the writer (myself) has at least a little competency with writing Turing machines.

 

Krim, if you’re interested in demonstrating that you also have at least a little practical familiarity with Turing machines, write one and post it. For instance, note that the example above is “destructive” – the original tape data is overwritten by the result. Can you write a Turing machine that adds 2 numbers and writes the result to the tape without destroying the original data?

 

If you’re unwilling or unable to demonstrate your ability to complete a typical introductory exercise, I’ll be forced to conclude that you have been writing about a subject you don’t fundamentally understand.

If a student in a "introductory computer science class" objected in any way to the presented proof, the professor would just declare by fiat his grade to be an F either directly or through concealed logic errors in grading. This not only means that the student would keep quiet if something did appear to be off, it also means he would not bother to think about it to the degree required to notice anything "fishy". …

This wasn’t my experience, either as a student or a teacher. Good teachers encourage skepticism, while requiring mastery of the subject matter necessary for such skepticism to be competent.

 

If your experience has been otherwise, Krim, you’ve been poorly served by your school, and I recommend you avail yourself of its available counseling services, academic appeal policies, or if these are ineffective, change teachers or schools.

[alexander]

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

 

true, but you dont get colors with qbits... you have an equivalent of a 2 color system with polarty... or if you wan to use the state terminology then angles would be states and an 8-state system would be exactly that... 8 angles of qbits... mmmm octal computing :)