- What is the difference between a transducer and a recognizer (10 words or less)?
Transducer outputs, recognizer only accepts/rejects
- What is the difference between a recognizer and a decider (10 words or less)?
Recognizer may loop, decider always halts
- What is the difference between the Harvard and von Neumann architectures (10 words or less)?
Harvard separates memory and program, von Neumann shares
- What family of languages are recognized by always-halting Turing machines?
- Type-1
- Type-2
- Recursive
- Type-3
- Finite
- Complete the standard 5-column table for the following TM. In your table write $S$ for the scanning state, $F$ for the flipping state, and $I$ for the incremented state:
| In State | Looking At | Write | Move | Next State |
|---|
| S | 0 | 0 | R | S |
| S | 1 | 1 | R | S |
| S | # | # | L | F |
| F | 1 | 0 | L | F |
| F | 0 | 1 | L | I |
| S | # | 1 | L | I |
- Which of the following have strictly less computing power than Turing Machines? Choose all that apply.
- Turing Machine with the tape infinite in only one direction
- Finite Automata
- Pushdown Automata
- Queue Automata
- Rewrite Machines
- Deterministic Turing Machines (only one choice can be made for each state+current_symbol pair)
- After running this 3AC program, what will be in r0?
copy r0, 1
copy r1, 5
mul r0, r0, r1
jzdec r1, -1
5
- Write, in Python, or any other mainstream programming language, the statement corresponding to the stack machine code
load y
load 2
load z
add
mul
store x
x = y * (2 + z)