Recently in my CS class I\'ve been introduced to the Turing Machine. After the c
ID: 650108 • Letter: R
Question
Recently in my CS class I've been introduced to the Turing Machine.
After the class, I spent over 2 hours trying to figure out what is the relationship between a tape and a machine.
I was completely unaware of the existence of computer tapes or how tapes and machines interacted until today. I still can't see why a machine would read tapes but a scanner is perhaps a closer conception to the Turing machine where paper is considered a tape and whatever goes inside of a scanner is whatever a Turing machine would do.
But in any case, isn't the idea of a Turing machine quite archaic? We have so many physical (rather than hypothetical) devices in our office or living room that seems to do what the Turing Machine does.
Can someone provide a better example drawing from reality so that the essential functionalities of this hypothetical conception is captured?
Explanation / Answer
AFAIK the Turing Machine is modeled on the idea of a human with a pen and paper. The human has a certain state in the brain, looks at the paper like the machine looks at the tape, and writes something on the paper or moves to look at a different place, just as the machine does.
TM is archaic as Peano natural number arithmetic. TM is useless for practical computation, and it is of course not intended to be used for that. It is just a simple way to axiomatize computation so we can reason about what's computable and what isn't - just as Peano arithmetic is useful for defining from first principles what natural numbers are, and what are their properties - but it would be ridiculous to try to do arithmetic by manipulating Peano numbers by hand according to the theoretical definitions.
Just think how difficult it would be to prove different theorems from complexity and computability theory (e.g. prove that the Halting Problem is undecidable), if you had to prove them using the semantics of the C++ programming language instead of the Turing Machine. Your proofs would be ridiculous or impossible - as ridiculous as proving associativity of natural number multiplication by using the grade-school method applied to decimal integers as your definition of what multiplication is.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.