Turing machines anyone?

Turing machines anyone?

Post by Dave » Sun, 08 Aug 2004 17:07:56


Hi, I'm currently studying for an exam which includes turing machines used
to compute fucntions. I can understand how I can derive a turing machine
for certain functions but other questions are baffling me. I would
appreciate some on the following from past exam papers. Thanks. I have made
attempts at these questions so it you would like me to show you how far I've
got, please ask.

Build turing machines that compute the following functions..

1: f(n) = 2(n) where n is positive

2: x / 2, where x>= 2, and x is an even fucntion

3: f(x) = x div 2 (i.e. x divided by 2, rounded down)

4: f(n) = { 0, if n = 2,
{ n, otherwise