2011-05-16
final review answers.
Originally Posted By: confusedNotle
this is number 6
Elton Murillo
Pin Chang
Jake Askeland
Jerry Wong
Jeremy Lozano
Elton Murillo
Pin Chang
Jake Askeland
Jerry Wong
Jeremy Lozano
'''Originally Posted By: confusedNotle'''
this is number 6 <br><br>Elton Murillo<br>Pin Chang<br>Jake Askeland<br>Jerry Wong<br>Jeremy Lozano
2011-05-18
Originally Posted By: Jake Askeland
For those who can't read the above image:
6. A Universal Turing Machine is a Turing Machine which can simulate any other Turing Machine.
To build a Universal Turing Machine U:
- U will have three tapes and process the input , where M is a Turing machine and w is its input.
- Move to tape 3, leaving on tape 1.
- Underscore the current input symbol on tape 1 (initially w_1).
- Tape 2 will keep track of the current state of M (initially q_start).
To simulate one step of M(w) on U:
- Rewind tapes 2 and 3.
- Scan tape 3 until the transition table of M is found.
- Scan tape 1 until the current input symbol is found (which will be underscored).
- Scan the transition table on tape 3 and:
- Compare each pair (state on tape 2, symbol under head on tape 1) with the transition under the head on tape 3.
- If they match, update the input symbol on tape 1 (advance the underscore) and update the transition state on tape 2 (copy the matching state from tape 3).
- A match should always be found for a deterministic machine M.
6. A Universal Turing Machine is a Turing Machine which can simulate any other Turing Machine.
To build a Universal Turing Machine U:
- U will have three tapes and process the input , where M is a Turing machine and w is its input.
- Move to tape 3, leaving on tape 1.
- Underscore the current input symbol on tape 1 (initially w_1).
- Tape 2 will keep track of the current state of M (initially q_start).
To simulate one step of M(w) on U:
- Rewind tapes 2 and 3.
- Scan tape 3 until the transition table of M is found.
- Scan tape 1 until the current input symbol is found (which will be underscored).
- Scan the transition table on tape 3 and:
- Compare each pair (state on tape 2, symbol under head on tape 1) with the transition under the head on tape 3.
- If they match, update the input symbol on tape 1 (advance the underscore) and update the transition state on tape 2 (copy the matching state from tape 3).
- A match should always be found for a deterministic machine M.
'''Originally Posted By: Jake Askeland'''
For those who can't read the above image:<br><br>6. A Universal Turing Machine is a Turing Machine which can simulate any other Turing Machine.<br><br>To build a Universal Turing Machine U:<br> - U will have three tapes and process the input , where M is a Turing machine and w is its input.<br> - Move to tape 3, leaving on tape 1.<br> - Underscore the current input symbol on tape 1 (initially w_1).<br> - Tape 2 will keep track of the current state of M (initially q_start).<br><br>To simulate one step of M(w) on U:<br> - Rewind tapes 2 and 3.<br> - Scan tape 3 until the transition table of M is found.<br> - Scan tape 1 until the current input symbol is found (which will be underscored).<br> - Scan the transition table on tape 3 and:<br> - Compare each pair (state on tape 2, symbol under head on tape 1) with the transition under the head on tape 3.<br> - If they match, update the input symbol on tape 1 (advance the underscore) and update the transition state on tape 2 (copy the matching state from tape 3).<br> - A match should always be found for a deterministic machine M.
(c) 2024 Yioop - PHP Search Engine