### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# THEORY OF COMPUTATION CSCE 551

GPA 3.61

### View Full Document

## 26

## 0

## Popular in Course

## Popular in Computer Science and Engineering

This 15 page Class Notes was uploaded by Trace Mante MD on Monday October 26, 2015. The Class Notes belongs to CSCE 551 at University of South Carolina - Columbia taught by M. Alekseyev in Fall. Since its upload, it has received 26 views. For similar materials see /class/229570/csce-551-university-of-south-carolina-columbia in Computer Science and Engineering at University of South Carolina - Columbia.

## Reviews for THEORY OF COMPUTATION

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/26/15

Theory of Computation Lecture 10 Turning Machines Max Alekseyev University of South Carolina February 17 2009 Computing Models We have already studied some computing models gt Finite automata are good model for devices that have small amount of memory gt Pushdown automata are good models for devices that have an unlimited but LIFO type of memory However as we have seen some very simple tasks are still beyond the capabilities of these models We need a new model that would represent general purpose computers Turing Machine Turing machine TM was first proposed by Alan Turing in 1936 It is similar to finite automata but has unlimited and unrestricted memory Hence it is a more accurate model of general purpose computers The TM model uses an infinite tape as its memory It has a tape head that can read and overwrite symbols and move along the tape Initially the tape contains only the input finite string and is blank everywhere else Turing machine computing consists of moving the head and reading or writing symbols until it reaches designated accept or reject states If it never happens the machine loops forever Differences from Finite Automata M 93 Turing machine can both write symbols on the tape and read from it The read write head can move both to the left and to the right The tape ie memory is infinite The special accept and reject states take effect immediately Sample Computing Consider a language B WW l W 6 01 A TM that recognizes this language can be informally described as follows gt Go along the input string and check that every symbols is either 0 1 or and there exactly one If not reject V Repeat find the left most symbols equal 0 or 1 and replace with a special symbol X move the head to the right reading symbols and looking for then find a first symbol 0 or 1 at the right hand side of compare it with s and replace it with X If they are not equal reject otherwise continue gt If no 0 or 1 symbols left at the left hand side and at the right hand side of accept Otherwise if it run out of 01 symbols at one hand side of but not the other reject See Fig 32 p 139 in the textbook Turing Machine Formal Definition A Turing machine is a 7 tuple Q7 X I397 6 qo qaccept qrejed where gt Q is a finite set of states gt X is the input finite alphabet not containing the blank symbol U gt I is the tape finite alphabet where U E I and X Q I39 gt 6 Q x I a Q x I x L7 R is the transition function gt qo7 qaccept qrejed E Q are the start accept and reject states respectively and qaccept 75 qrejed Tu ring Machine Computation A M Q7 X7 l v 67 707 qacceph qreject on lnPUt W W1W2 Wn E X written in the left most n squares of the tape the rest of the tape is filled with U computes as follows 1 It starts from the start state qo with the head located at the left most square of the tape N Repeat for the current state q reading symbol 5 from the tape M behaves according to the value 6q7 s q s 7 d as follows it replaces s with the symbol 5 possible with the same symbol if s 5 goes to the state 7 and moves the head in the direction d ie to Left or Right A On arriving at the state qaccep or qrejed M accepts or rejects accordingly Note that it is not possible to move the head beyond the left end of the tape the head remains in the left most position if even it is instructed to move to the left Tu ring Machine Configuration The current state tape content and head location describing a TM at any intermediate step of computation is called configuration Configurations are represented as triples uqv where q E Q is the state u7 v E 39 form the tape content uv and the head location is the first symbol of v Everything beyond the last symbol of v is blank In particular gt the start configuration of a TM on input W is qow where qo is the start state gt a accepting configuration is uqacceptv for any u7 v E 39 gt a rejecting configuration is uqrejedv for any u7 v E 39 gt a halting configuration is either accepting or rejecting configuration Tu ring Machine Configuration A TM configuration C1 yields a configuration C2 if it can legally go from C1 into C2 in a single step For example for qqj E Q uv E 39 and abc E I39 a configuration uaqibv yields a configuration quacv if 6q7 b qj7 67 L Similarly a configuration uaqibv yields a configuration uacqjv if 6q7 b qj7 67 R Tu ring Machine Configuration A TM configuration C1 yields a configuration C2 if it can legally go from C1 into C2 in a single step For example for qqj E Q uv E 39 and abc E I39 a configuration uaqibv yields a configuration quacv if 6q7 b qj7 67 L Similarly a configuration uaqibv yields a configuration uacqjv if 6q7 b qj7 67 R A Turing machine M accepts an input W if there is a sequence of configurations C17 C2 Ck such that 1 C1 is the start configuration of M on the input W 2 C yields CH1 for every 139 127 7 k7 1 3 Ck is the accepting configuration Q Describe similarly when M rejects an input W Turing Machine Languages A collection of strings that a TM M accepts is called the language ofM or language recognized by M denoted LM A language is Turing recognizable or recursively enumerable if it is recognized by some Turing machine Turing Machine Languages A collection of strings that a TM M accepts is called the language ofM or language recognized by M denoted LM A language is Turing recognizable or recursively enumerable if it is recognized by some Turing machine A TM M on an input that is not in LM can either reject or loop We distinguish TMs that never loop and call them deciders A decider M decides the language that it recognizes A language is Turing decidable or recursive if it is decided by some Turing machine Turing Machine Languages A collection of strings that a TM M accepts is called the language ofM or language recognized by M denoted LM A language is Turing recognizable or recursively enumerable if it is recognized by some Turing machine A TM M on an input that is not in LM can either reject or loop We distinguish TMs that never loop and call them deciders A decider M decides the language that it recognizes A language is Turing decidable or recursive if it is decided by some Turing machine Q What can you say about the complement of a Turing decidable language Turing Machine Variations A number of variations of TM possible such as gt a TM with possible stay put moves of the head gt a TM with a tape infinite in both directions gt a TM with multiple tapes gt a non deterministic TM It turns out that such variations have no more computation power than the regular TM as we defined it To prove that it is enough to show that there is a regular TM simulates a particular variation ie they always produce the same result for the same input Turing Machine Simulation Note that configuration of a TM can be encoded by a finite string that other TM can read and write on its tape Furthermore the transition function of a TM can be also described by a finite string These observations lead to idea of encoding and running the whole TM by another TM

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.