How things work college course/Turing machine quiz

From Wikiversity
Jump to navigation Jump to search


Wikiversity Sunflower Logo.svg

      The version of this quiz associated with Quizbank is located at QB/b_busyBeaver


This quiz covers Wikipedia's Computer (Wikipedia permalink) and its links: w:Turing machine * w:Busy beaver * w:Halting problem * w:Bombe. For another quiz on this topic, see Computer quiz.

The un-shuffled version of this quiz serves as a good pre-reading activity for the article. For randomized versions of this quiz, use the testbank. For information on how to print out test copies (and other questions) see How to use testbank.

Turing machine: 2-state 2-symbol busy beaver[edit]

The 2-state 2-symbol busy beaver starts with all zeros and proceed as follows:

  • If head reads 0 and
    • In State A: Print 1. Move head Right. Go to State B.
    • In State B: Print 1. Move head Left. Go to State A.
  • If head reads 1 and
    • In State A: Print 1. Move head Left. Go to State B.
    • In State B: Print 1. Move head Right. Go to State H (Halt).

The following table should be made available to students as they take the quiz:

A B
0 1RB 1LA
1 1LB 1RH

Computer TURING MACHINE[edit]







  

1

If the machine is at A: 000000, what's next?
2-state 2-symbol busy beaver.svg

B: 000010
B: 000100
A: 000100
A: 000010

2

If the machine is at B: 000100, what's next?
2-state 2-symbol busy beaver.svg

B: 000110
A: 001100
B: 000110
A: 000110

3

If the machine is at A: 000110, what's next?
2-state 2-symbol busy beaver.svg

B: 001100
B: 000110
A: 000110
A: 001110

4

If the machine is at B: 000110 , what's next?
2-state 2-symbol busy beaver.svg

B: 000111
B: 001110
A: 001110
A: 001110

5

If the machine is at A: 001110, what's next?
2-state 2-symbol busy beaver.svg

B: 011110
H: 011110
A: 011110
H: 011110

6

If the machine is at B: 011110, what's next?
2-state 2-symbol busy beaver.svg

B: 011110
H: 011110
A: 011110
H: 011110