Turning machines

Posted on 2004-11-22
Last Modified: 2008-03-10
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.
Advanced Activities

(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.
Question by:icb01co1
    LVL 4

    Accepted Solution

    I assume you mean Turing machine, named after Alan Turing (

    Here's some info -
    Turing machine - Wikipedia, the free encyclopedia        <- good example here

    Turing Machines in more detail:

    More links can be found on, or (eeech)
    - just note the spelling of TURING

    Author Comment

    lol, yeah turning sorry

    Author Comment

    Doh, did it again: TURING

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    Maximize Your Threat Intelligence Reporting

    Reporting is one of the most important and least talked about aspects of a world-class threat intelligence program. Here’s how to do it right.

    Entering a date in Microsoft Access can be tricky. A typo can cause month and day to be shuffled, entering the day only causes an error, as does entering, say, day 31 in June. This article shows how an inputmask supported by code can help the user a…
    A short article about problems I had with the new location API and permissions in Marshmallow
    Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …
    In this fourth video of the Xpdf series, we discuss and demonstrate the PDFinfo utility, which retrieves the contents of a PDF's Info Dictionary, as well as some other information, including the page count. We show how to isolate the page count in a…

    794 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    16 Experts available now in Live!

    Get 1:1 Help Now