L10 - Register Machine and Cellular Automata

Question 1

What is a Register Machine?

Answer 1

A machine-like computation model (Machine program)

Question 2

What is the difference between Register Machine and Turing Machine?

Answer 2

TM operates by moving left of right on a tape, RM operation is enabled by random access to memory.

Question 3

What is the syntax for resetting, incrementing, decrementing, moving a value in Register Machine?

Answer 3

Xi := 0
Xi := Xi + 1
Xi := Xi - 1
Xi := Xj

Question 4

How is a conditional statement performed in RM?

Answer 4

if Xi = 0 goto Xj l2 else l7

Question 5

What is the syntax for moving the content of a register addressed by Xj?

Answer 5

Xi := <Xj></Xj>

Question 6

What is the syntax for moving into a register addressed by Xi?

Answer 6

<Xi> := Xj
</Xi>

Question 7

What is the Store of RM?

Answer 7

Memory that is indexed via natural numbers.

Question 8

What is the syntax for the Readin and Readout operations?

Answer 8

X0

Question 9

What does Xi represent in RM?

Answer 9

A register value

Question 10

Conways Game of Life is Turing Complete. What does this mean?

Answer 10

It is a set of data-manipulation rules that can simulate any Turing Machine.