In a Turing machine, what is the difference between the instruction table and the algorithm?
The instruction table seems to be an algorithm for completing the task no?
$\begingroup$
$\endgroup$
0
Add a comment
|
$\begingroup$
$\endgroup$
6
The Turing machine instruction table is a concrete implementation of the abstract algorithm. Usually, in one's everyday life as a computer scientist, there's not much to be gained by distinguishing these two concepts. Indeed, one can take the position that the Turing machine is the definition of "algorithm".
answered Jun 19 '19 at 11:31
-
$\begingroup$ On modern computers, what would the instructions be in a turing machine? I'm guessing the alphabet? By instructions I mean like ADD, MOV $\endgroup$ – WeCanBeFriends Jun 19 '19 at 11:54
-
$\begingroup$ I'm not sure it's productive to equate concepts at this level. Turing machines and real computers are fundamentally different and their equivalence is in terms of being able to simulate one another, not in terms of "this part corresponds to that". If you are going to construct a direct analogy between the two, remember that modern computers are general-purpose, programmable machines, so the equivalence is going to be with universal Turing machines, not arbitrary ones. $\endgroup$ – David Richerby Jun 19 '19 at 12:09
-
1$\begingroup$ At that point, sure, CPU instructions will correspond to parts of the input program to the Turing machine, so they'll either be encoded as individual symbols on the tape, or as patterns of zeros and ones, or whatever other encoding is convenient. $\endgroup$ – David Richerby Jun 19 '19 at 12:10
-
$\begingroup$ Ahh, I finally understand something quite sneaky for a noob like me. A Turing Machine is an implementation of "a" algorithm. One specific algorithm. Which is why we have the universal Turing Machine. $\endgroup$ – WeCanBeFriends Jun 19 '19 at 14:14
-
1$\begingroup$ @WeCanBeFriends Yes! And, of course, the universal Turing machine also implements one specific algorithm: an algorithm that interprets strings as descriptions of Turing machines and executes the corresponding algorithm. $\endgroup$ – David Richerby Jun 19 '19 at 14:29
