Register Machines Flashcards
(10 cards)
Why are Register Machines theoretically attractive
they can be proven to be equivalent to turing machines
Why are Regitser Machines physically attractive
have clear analogies ot FSM
what are the cons to register machines
come aspects cannot be realised (like infinite sized words stored in registers)
Can be very innefficient
define register machine
a finite number of registers with the ability to store an infinite number
a program holding a fninite number of instructions each with a label
What is a configuration
is a tuple which stores the state of the machine
<li,v0,v1,…,v(r-1)>
how is some computation stored using a register machine
<C0,C1,..,Cn>
where n is the final configuration
What do register machines use godel encoding for
to compress a list of register values or a configuration or a computation into one single number
How does godel encoding work
let K be the sequence of numbers and P be a list of primes
PRODUCT (pi^ki)
How can an RM act as an FSM in disguise
where each configuartion is a state
and teh program determines the transition
describe the FDE cycle
Fetch load instruction in IR
incement PC
decode - determine what IR contents means
translate it into control signals
execute - Do the contents of IR
Memory access stage - perform any memory accesses
Write back stage - store result
