Quote:
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.
Quote:
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:
Quote:
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:
Code:
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:
Code:
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.
Quote:
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.
----------------
Moderator: Computers and Technology; Medical Science; Science Projects and Homework; Philosophy of Science; Physics and Mathematics; Environmental Studies
