[Last Call] Learn how to a build a cloud-first strategyRegister Now

x
Solved

# Turning machines

Posted on 2004-11-22
Medium Priority
261 Views
Hi Experts,

Does anyone know a link to a site that will teach me about turning machines so that i can answer the following questions:

(1) Draw the transition diagram for the following TM, called ADD1 :-
{s0, 0, 1, halt}
{s0, 1, 2, halt}
{s0, 2, 3, halt}
{s0, 3, 4, halt}
{s0, 4, 5, halt}
{s0, 5, 6, halt}
{s0, 6, 7, halt}
{s0, 7, 8, halt}
{s0, 8, 9, halt}
{s0, 9, 0, s1}
{s1, 0, <--, s0}
{s0, _, 1, halt}         [the underbar represents a Space character]

(2) Explain briefly what ADD1 does.

(3) Draw diagrams to show how ADD1 works on the tape, with a diagram for each stage of the operation. Include examples to show how the s1 state is used.

(4) Suppose you had other TMs called SUB1, SKIP_LEFT and SKIP_RIGHT, that move left and right (respectively) to the next number on the tape in either direction. By using these four TMs as sub-machines, and with any extra TM code you need, write a loop that would add together two decimal numbers on a tape, separated by a space. Show your solution as a diagram.

(5) Write a DUP submachine, that will duplicate a binary number on the top of the stack. For example, if the stack is "110 1011", then after DUP the stack will contain "110 1011 1011". Use this to design a machine that multiplies decimal numbers by repeated addition and duplication. You may assume you already have a submachine to do binary addition.

Its revision time and i need to read up on turning machines fast.

Thanks, Chris.
0
Question by:icb01co1
• 2

LVL 4

Accepted Solution

bytta earned 500 total points
ID: 12647175
I assume you mean Turing machine, named after Alan Turing (http://www.turing.org.uk/turing/)...

Here's some info -
Turing machine - Wikipedia, the free encyclopedia
http://en.wikipedia.org/wiki/Turing_machine        <- good example here

Turing Machines in more detail:
http://plato.stanford.edu/entries/turing-machine/

- just note the spelling of TURING
0

Author Comment

ID: 12647674
lol, yeah turning sorry
0

Author Comment

ID: 12647677
Doh, did it again: TURING
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Whether you’re a college noob or a soon-to-be pro, these tips are sure to help you in your journey to becoming a programming ninja and stand out from the crowd.
This article will show how Aten was able to supply easy management and control for Artear's video walls and wide range display configurations of their newsroom.
In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…
Loops Section Overview
###### Suggested Courses
Course of the Month17 days, 15 hours left to enroll