This Search Engine

2011-05-16

final review answers .

'''Originally Posted By: confusedNotle'''

this is number 6 Elton Murillo Pin Chang Jake Askeland Jerry Wong Jeremy Lozano

'''Originally Posted By: confusedNotle''' this is number 6 Elton Murillo Pin Chang Jake Askeland Jerry Wong Jeremy Lozano

2011-05-18

-- final review answers

'''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.

'''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.