Halting Undecidability proof faulty?

[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]

Originally Posted by Kriminal99

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

Originally Posted by Kriminal99

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,
Buffy

[CraigD]

Originally Posted by Kriminal99

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

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.

Originally Posted by Kriminal99

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:

Originally Posted by CraigD

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.

Originally Posted by Kriminal99

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]

Originally Posted by laurie

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

[Kriminal99]

Moderation note: This post was used to start a new thread discussing the same subject as this existing thread, so it and responses to it were merged with the old thread.

The proof is easily defeated by pointing out that we are assuming that a halting function couldn't just piecewise assign "halts" to itself instead of actually running on itself, which would prevent the existence off any partial function which would attempt to have the halting algorithm run on it's own encoding


Also, Consider the following proof.

Consider a set of Universal Turing Machines that at some point simulate their input machine. Call the set S.

Now we construct another set of machines "G" that takes the encoding of an element of S and copies it, then simulates S on it's self.

G is a subset of S. Therefore G can run on itself. G(G) infinitely loops as defined because it copies it's own input and simulates, then the simulation copies, then simulates, and that simulation copies then simulates etc. forever.

Thus any function G of this sort can not be claimed to be able to do anything BUT loop when run on itself. Thus any proof which depends on the creation and running of such a function on itself and claims that the function retains some ability other than looping is assuming a falsehood. All Halting proofs assume this falsehood, which is the source of the derived contradiction.

[alexander]

this is like a 1/4 of an idea... can you please expand on your first post with the following:

firstly, provide the basis of what lead you to look at this, otherwise why would it interest us? and posts that dont interest don't get replies you are perhaps looking to get.

secondly, explain halting to people who may not know what it is, this is, after all, a public forum where people come to learn and participate and get ideas or answers...

lastly, you say "source of derived contradiction"... what contradiction? this is something that should probably be covered in the pre/intro, but still, consider structuring your post closer to an essay (intro paragraph, or sentence or something, some words describing your problem/delema, introduce the concept, ask questions, post oppinion, close out with some thoughts or more questions), it makes for an easier read, better interest into researching the matter and all around a better discussion.

P.S. don't take me as a prick, and i do what you did in your post all the time, problem is, over time i have developed an understanding of better or worse ways of asking/discussing and creating posts that draw people into conversation, rather then confuse the living hell out of them and make them simply not care, which, as you may imagine, translates into no replies and your frustration with the user base for not helping you get a fresh view point, or bring to your eyes some evidence that you did not consider before.

[phillip1882]

the halting problem is not saying you can't determine whether a particular program will halt.
its saying there's no universal program to determine whether any program will halt.
let me show you what i mean.

let's say we have the program

x =0
while x <10:
   x = x+1
   x = x-1

and want an algorithm to determine whether or not this program will halt. we note that x goes back and forth between two numbers 0, and 1. so one possible algorithm would be
if x value resets, the program will never halt.
now however consider

y = 0
while x <10:
   y=y+1
   x = 0
   x = y

the x value resets every iteration, but then quickly goes to the value y. so we need a new algorithm. one possible algorithm would be, if x repeats its pattern, the program will never halt.
now consider

y = 0
while x <10:
    y = y+1
    x = 0
    x = 1
    if y = 10:
       x = 11

x repeats its pattern 10 times, yet the program still halts.
in short there is no algorithm that will guarantee an accurate halt detection.

[alexander]

I understand what halting is, i am just saying that a clarification, like the above, would make other people more prone to participate in the discussion.


how about an algorithm that first takes note of the condition under which a particular event is supposed to halt.

notes the conditions under which any explicit brakes in the particular process will occur, and what variables will effect those conditions.

steps through the decision process a couple of times, to see how the variables that effect the exit conditions are changed.

finally determines if any of the conditions that cause the algorithm to exit will ever exist.

sounds like some self-modifying code actually to be smart enough to create a child that will monitor the explicit loop conditions...

[phillip1882]

well consider the following code

while z <100:
   y = random.randint(0,100)
   x = random.randint(0,y)
   z = random.randint(0,x)

this should halt, but it could take hours, and there wouldn't be much of a determinable pattern.

[alexander]

Actually that code will never halt, because while you may have a random number equal to 100, your algo will never return z that is larger then 100.

and yes, looking at exit conditions and variable manipulation limits, my algorithm, if implemented properly, will still be able to detect a non ever-ending loop...