3 ms·

for non-computer scientists, but rather for engineers, how do Turing machines map to the stored-program computer that have instruction sets, stacks, RAM and ROM

by poseid 11y ago

for non-computer scientists, but rather for engineers, how do Turing machines map to the stored-program computer that have instruction sets, stacks, RAM and ROM ?

v-yadli 11y ago
make extensions on the original. use the single tape to simulate multiple tapes, one for stack(or registers), one for ram, one for rom, and another for encoding how the hardware behaves against the other tapes.
- JadeNB 11y ago
  > make extensions on the original. use the single tape to simulate multiple tapes, one for stack(or registers), one for ram, one for rom, and another for encoding how the hardware behaves against the other tapes. Very nice; that is surely about the best information:length ratio one could hope for! I hope you won't mind a slight clarification—obvious, I am sure, to you and to any computer scientist, but not, perhaps, to a non-specialist: this is not an extension of the original, but rather a simulation within the original of an apparently more general concept. This is important, because it means that any theoretical results about the original concept also apply to its apparent generalisation (e.g., multi-tape Turing machines still can't decide undecideable problems).
  - v-yadli 11y ago
    yep, thanks for the clarification!
DonHopkins 11y ago
It's easy to visualize the tape as a physical object [1], but there is another important, "invisible" part of a Turing machine, that is the program state space, which is harder to illustrate or visualize (especially for non-trivial programs and theoretical proofs, which balloon into enormous messes). Your program is a graph of states that the Turing Machine can be in, and the "head" moving over the tape drives a "body" around that graph. So not only is there a tape "head" pointing to a place on the tape, but a state space "body" pointing to a place in the program, walking around a labyrinth of connected places, like a memory palace. And you can encode data in the connections between those "rooms". For example, if you write a turing machine to output "101", where did those numbers come from? From the way a connected series of "rooms" were configured in the program state space. It moves the "body" from room to room to remember what part of the output it's in. The tape can change, but the program state space itself never changes, only your location in the program. (If you enjoy self modifying code, you should check out John von Neumann's 29 state cellular automata [2] and Universal Constructor [3]!) I think of the rooms as being connected by magic one-way exit doors (not the helpful Sirius Cybernetics Corporation variety, which would bring too much complexity and indeterminism to this beautifully simple model). Each door is labeled with the symbols that could be on the tape, and lead to other rooms. (Or back to the same room!) When you walk through a specific door, it writes a certain symbol on the tape and moves the tape head in a certain direction. Each door has a symbol to match from the tape, a symbol to write to the tape, the direction to move the tape head, and a the next room to move into. I don't understand TECO, but I would guess that Marvin Minsky's Universal Turing Machine TECO program used text buffers with cursors to represent the tape with the head position, the instruction table with the state register program counter. By the terminology of Wikipedia's informal description, the location of the "body" is the "state register" or program counter, pointing into the "rooms" or program graph represented by the "finite table of instructions". [4] >A state register that stores the state of the Turing machine, one of finitely many. Among these is the special start state with which the state register is initialized. These states, writes Turing, replace the "state of mind" a person performing computations would ordinarily be in. >A finite table of instructions that, given the state(qi) the machine is currently in and the symbol(aj) it is reading on the tape (symbol currently under the head), tells the machine to do the following in sequence (for the 5-tuple models): >Either erase or write a symbol (replacing aj with aj1), and then >Move the head (which is described by dk and can have values: 'L' for one step left or 'R' for one step right or 'N' for staying in the same place), and then >Assume the same or a new state as prescribed (go to state qi1). >In the 4-tuple models, erasing or writing a symbol (aj1) and moving the head left or right (dk) are specified as separate instructions. Specifically, the table tells the machine to (ia) erase or write a symbol or (ib) move the head left or right, and then (ii) assume the same or a new state as prescribed, but not both actions (ia) and (ib) in the same instruction. In some models, if there is no entry in the table for the current combination of symbol and state then the machine will halt; other models require all entries to be filled. [1] http://www.worldofcomputing.net/wp-content/uploads/2013/01/turingMachine.gif http://www.worldofcomputing.net/wp-content/uploads/2013/01/t... [2] https://en.wikipedia.org/wiki/Von_Neumann_cellular_automaton https://en.wikipedia.org/wiki/Von_Neumann_cellular_automaton [3] https://en.wikipedia.org/wiki/Von_Neumann_universal_constructor https://en.wikipedia.org/wiki/Von_Neumann_universal_construc... [4] https://en.wikipedia.org/wiki/Turing_machine#Informal_description https://en.wikipedia.org/wiki/Turing_machine#Informal_descri...
- poseid 11y ago
  thanks; still a bit confusing. but I get that a Von Neumann machine can be simulated with a Turing machine. So, the Turing machine is more fundamental. Still, let's say my instruction set is ADD, LOAD, STORE, where do these instruction live in a Turing machine?

by poseid 11y ago

for non-computer scientists, but rather for engineers, how do Turing machines map to the stored-program computer that have instruction sets, stacks, RAM and ROM ?

v-yadli 11y ago

make extensions on the original. use the single tape to simulate multiple tapes, one for stack(or registers), one for ram, one for rom, and another for encoding how the hardware behaves against the other tapes.

JadeNB 11y ago
> make extensions on the original. use the single tape to simulate multiple tapes, one for stack(or registers), one for ram, one for rom, and another for encoding how the hardware behaves against the other tapes. Very nice; that is surely about the best information:length ratio one could hope for! I hope you won't mind a slight clarification—obvious, I am sure, to you and to any computer scientist, but not, perhaps, to a non-specialist: this is not an extension of the original, but rather a simulation within the original of an apparently more general concept. This is important, because it means that any theoretical results about the original concept also apply to its apparent generalisation (e.g., multi-tape Turing machines still can't decide undecideable problems).
- v-yadli 11y ago
  yep, thanks for the clarification!

DonHopkins 11y ago

It's easy to visualize the tape as a physical object [1], but there is another important, "invisible" part of a Turing machine, that is the program state space, which is harder to illustrate or visualize (especially for non-trivial programs and theoretical proofs, which balloon into enormous messes). Your program is a graph of states that the Turing Machine can be in, and the "head" moving over the tape drives a "body" around that graph. So not only is there a tape "head" pointing to a place on the tape, but a state space "body" pointing to a place in the program, walking around a labyrinth of connected places, like a memory palace. And you can encode data in the connections between those "rooms". For example, if you write a turing machine to output "101", where did those numbers come from? From the way a connected series of "rooms" were configured in the program state space. It moves the "body" from room to room to remember what part of the output it's in. The tape can change, but the program state space itself never changes, only your location in the program. (If you enjoy self modifying code, you should check out John von Neumann's 29 state cellular automata [2] and Universal Constructor [3]!) I think of the rooms as being connected by magic one-way exit doors (not the helpful Sirius Cybernetics Corporation variety, which would bring too much complexity and indeterminism to this beautifully simple model). Each door is labeled with the symbols that could be on the tape, and lead to other rooms. (Or back to the same room!) When you walk through a specific door, it writes a certain symbol on the tape and moves the tape head in a certain direction. Each door has a symbol to match from the tape, a symbol to write to the tape, the direction to move the tape head, and a the next room to move into. I don't understand TECO, but I would guess that Marvin Minsky's Universal Turing Machine TECO program used text buffers with cursors to represent the tape with the head position, the instruction table with the state register program counter. By the terminology of Wikipedia's informal description, the location of the "body" is the "state register" or program counter, pointing into the "rooms" or program graph represented by the "finite table of instructions". [4] >A state register that stores the state of the Turing machine, one of finitely many. Among these is the special start state with which the state register is initialized. These states, writes Turing, replace the "state of mind" a person performing computations would ordinarily be in. >A finite table of instructions that, given the state(qi) the machine is currently in and the symbol(aj) it is reading on the tape (symbol currently under the head), tells the machine to do the following in sequence (for the 5-tuple models): >Either erase or write a symbol (replacing aj with aj1), and then >Move the head (which is described by dk and can have values: 'L' for one step left or 'R' for one step right or 'N' for staying in the same place), and then >Assume the same or a new state as prescribed (go to state qi1). >In the 4-tuple models, erasing or writing a symbol (aj1) and moving the head left or right (dk) are specified as separate instructions. Specifically, the table tells the machine to (ia) erase or write a symbol or (ib) move the head left or right, and then (ii) assume the same or a new state as prescribed, but not both actions (ia) and (ib) in the same instruction. In some models, if there is no entry in the table for the current combination of symbol and state then the machine will halt; other models require all entries to be filled. [1] http://www.worldofcomputing.net/wp-content/uploads/2013/01/turingMachine.gif http://www.worldofcomputing.net/wp-content/uploads/2013/01/t... [2] https://en.wikipedia.org/wiki/Von_Neumann_cellular_automaton https://en.wikipedia.org/wiki/Von_Neumann_cellular_automaton [3] https://en.wikipedia.org/wiki/Von_Neumann_universal_constructor https://en.wikipedia.org/wiki/Von_Neumann_universal_construc... [4] https://en.wikipedia.org/wiki/Turing_machine#Informal_description https://en.wikipedia.org/wiki/Turing_machine#Informal_descri...

poseid 11y ago
thanks; still a bit confusing. but I get that a Von Neumann machine can be simulated with a Turing machine. So, the Turing machine is more fundamental. Still, let's say my instruction set is ADD, LOAD, STORE, where do these instruction live in a Turing machine?