### Create a StudySoup account

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

Already have a StudySoup account? Login here

# THEORY OF COMPUTATION CS 215

UCR

GPA 3.88

### View Full Document

## 19

## 0

## Popular in Course

## Popular in ComputerScienence

This 4 page Class Notes was uploaded by Adele Schaden MD on Thursday October 29, 2015. The Class Notes belongs to CS 215 at University of California Riverside taught by Staff in Fall. Since its upload, it has received 19 views. For similar materials see /class/231746/cs-215-university-of-california-riverside in ComputerScienence at University of California Riverside.

## 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/29/15

The Birth cont d In 1936 several papers appeared that shed light on that question Church39s Lambda calculus Kleene39s general recursive functions Turing39s system now called Turing machines and Post39s production systems si r to Turing machines All these systems were proved equivalent Church and Turing then proposed equivalent theses viz Church s Thesis Turing s Thesis orthe ChurchTuring Thesis which states that the classes of mathematical problems that are effectively solvable in the intuitive sense are those that are effectively solvable 39n one of and thus any of the three computational models The thesis also suggests that the notion of effective computability is modelindependent C8215 Lecture 5 2000 3 Turing Machines A Turing machine s a stepwise computing device which consists of 1 an infinitely long tape that is divided into tape squares or tape cells 2 a head that scans is positioned at a particulartape square at each time step and 3 a finite control that maintains the current state C8215 Lecture 5 2000 4 Computab39 39 y Theory C8215Lecture52000 1 The Birth of Turing Machines At the end of the 19th century Gottlob Frege conjectured that mathematics could be built from fundamental logic In 1900 David Hilbert accepting this view asked whether there is a process whereby it could be determined in a nite number of operations whether a given polynomial has an integral root In 1931 Kurt Godel showed that every logical system general enough to deal with arithmetic contains statements that cannot be proven true or false What classes of mathematical problems lack effective solutions C8215Lecture52000 2 Computation of a Turing Machine In one step a Turing machine 1 Reads the symbol written on the tape square on which the head is located and according to the transition function 2 Makes one move It a updates its state b writes on the current tape square and c moves the head by one square either to the left or to the right where the head stays at the same position if it is at the left end of the tape and a left move is specified by 5 C8215 Lecture 5 2000 7 Computation of a Turing Machine cont d At the beginning 1 the tape contains the input on the leftmost squares 2 the rest ofthe tape is filled with blank symbols 3 the head is at the leftmost cell and 4 the state is 10 The Turing machine halts when it enters one of q these states it accepts and rejects respectively m and gm and in C8215 Lecture 5 2000 8 Turing Machines cont d Each combination of a state and a scanned tape symbol determines the next state the symbol written on the scanned square and the move L or R ofthe tape head a nite control C8215Lecture52000 5 Turing Machines cont d A Turing machine is a 7iupie QEI quRW where Q E F are finite sets F Q is a set of states N39 E is the input alphabet 5 F is the tape alphabet where E g F L1 and L1 is the special blank symbol 6 Q X I gt Q X I gtlt LR is the transition function 10 is the in al state qwcm is the accept state and v39Ln39Lo39rx39 gmjm is the reject state C8215Lecture52000 5 The Languages of Turing Machines A Turing machine M accepts rejects a string 1 if it eventually enters an accepting a rejecting state for input 11 A Turing machine M recognizes a language L if for every input 11 M on 1 accepts if and only if 1 e L A Turing machine M decides a language L if M recognizes L and halts on all inputs A language is Turingrecognizable or recursively enumerable if there is a Turing machine that recognizes it A language is Turingdecidable or simply decidable if there is a Turing machine that decides it C8215 Lecture 5 2000 11 Example A ll unxpeci ed meitiom39 go to a reject xt e C8215 Lecture 5 2000 12 Configurations A configuration of a Turing machine consists of the contents of its tape the head position and the state If the tape contents are 411 mm 11 the head is located on the Istth square and the state is g then we write 411 41mm am to denote the configuration The segment of blanks f g the tape is omitted but at least one symbol possibly L1 is required after the state Thus a configuration is a word in FquotQFF LJ E a b a b b 1 In the above the configuration is ababb 1211 C8215Lecture72000 9 Configurations cont d The action of a TM can be viewed as rewriting ofthe configuration A configuration 01 yi Ids 2 ifthe Turing machine can go from O1 to 2 in a single step wqub n ields nqjm i if 501211 4 grail 12b yields gym if 501211 4 Qjt L gt 0 and 0 W112 yields wicq if 501112 qjrR where 9 is 3 if 3 Llif 40 3 An accepting configuration A rejecting configuration is one in which the state is 1M L gm L Accepting configuration and rejecting configurations are hal ng configurations C8215Lecture52000 10 Proof cont d On input 11 4101 1 Convert v yHu jy j j 2 While M has not halted repeat a Make a sweeping scan on the tape to find the symbols scanned by the heads of M b Determine the next move of M and modify the ncoding accordingly Insert symbols if necessary 3 Accept or reject accordingly C8215 Lecture 5 2000 15 Equivalence Between NTMs and TMs Theorem Every nondeterministic Turing machine has an equivalent deterministic Turing machine Proof From an NTM N construct a threetape simulator D Let b be a constant such that each transition has at most 2 possible values Let Eb 12b Use a word in on Tape 3 to encode a nondeterministic path where for each i 2 0 if the ith symbol of the word isj this signifiesthat forthe ith move of N the jth element among the av 39 ble choices if any is selected The word is invali if too few choices are available C8215 Lecture 5 2000 15 Multitape TMs amp Nondeterministic TMs A multitape Turing machine is a Turing machine with additional tapes where each tape is accessible individually with the input on the first tape and with the others blank at the begi ing For a lattape Turing machine the transition function 5 is a mapping from Q X F to Q X F X LR A nondeterministic Turing machine is one in which the transition is mapping to the power set of Q X F X LR A nondeterministic Turing machine accepts an input if it enters an accepting state for some computation path C8215Lecture52000 13 Equivalence Between Single Tape TMs and Multitape TMs Theorem Every multitape Turing machine has an equivalent single tape Turing machine Proof From a lattape TM M build a single tape simulator For each u e F let 47 be a new symbol to signify that a head is located on the symbol Then S concatenates the contents of M s tapes with a new symbol as a delimiter The tape configuration of M in which the tape contents are m wim w and the head positions are l is encoded as 914 m4 39 H1 il 91 941971 w S memorizes M 39s state using its own state C8215Lecture52000 14

### 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

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

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

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

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### 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.