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


Turning machines

Posted on 2004-11-22
Medium Priority
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
  • 2

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:

More links can be found on Google.com, Altavista.com or (eeech) msn.search
- just note the spelling of TURING

Author Comment

ID: 12647674
lol, yeah turning sorry

Author Comment

ID: 12647677
Doh, did it again: TURING

Featured Post

Vote for the Most Valuable Expert

It’s time to recognize experts that go above and beyond with helpful solutions and engagement on site. Choose from the top experts in the Hall of Fame or on the right rail of your favorite topic page. Look for the blue “Nominate” button on their profile to vote.

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

830 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