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

## 17

## 0

## Popular in Course

## Popular in ComputerScienence

This 7 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 17 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

18 Turing Machines 1 Turing Machines 2 Nondeterministic Turing Machines 415 181 Turing Machines o Introduced by Alan Turing o Abstract machine with many features of computer o Designed before the stored program computer o No memory limit An infinite tape and a tape reader that reads one symbol at a time Turing Machine 2 0 1 2 3 4 6 A quintuple M QEF757 10 o A finite set of states Q o A finite set F the tape alphabet which includes blank B o A subset E g F7 B called the input alphabet o A partial transition function 6 Q x F a Q x F x LR o A start state qO E Q 1811 Turing Maf hinf G39 Initial 0 1 2 Computation begins with o An input string 3 c1c7L in 2 on the tape from position 1 to n o The remaining tape blank filled with B o Initial state go 418 1812 Turing Machines Transition x l E o Machine in state q reading tape symbol 1 E F 501w Q Vyidl Y o Transitions have three parts Change the state to q Write symbol y on square scanned by tape head Move head left or right depending on direction cl 419 1813 Turing Machines Final l E o Machine halts if in state q reading tape symbol 1 E F there is no 6qz q ycl o Remember 6 is a partial function o Output is the result remaining on the tape o Machine halts abnormally if the head moves offthe left end of the tape 1814 Turing Machines Example Change all a39s to 2395 and vice versa qO quByR 42737L qubyR quayR qZVaVL qZVbVL Represented as a state machine abR baR aaL bbL 421 1815 Turing Machines39 Traces o A configuration uqivB represents the tape uvBBB 2 includes rightmost non blank shows tape head over first symbol in v shows machine state q o notation uqu k mqij indicates a transition from configuration quB to ijyB o quB H mqij means result of any finite number of steps 422 1816 Turing Machines Example Trace qoBabaB F Bq1abaB F BbqlbaB abR F BbaqlaB F BbabqlB F Bbaqsz F BquabB F qubabB F qubabB 1817 Turing Machines Another Example Machine to add 1 to a binary number UUR 11R lUL Q Q gt BBR ql BBL 12 0112 qoBOOIB qoBllB b Bq1001B b BqlllB b 80111018 b qullB b B00q1lB b B11q1B b BOOlqlB b qung b 30011ng b BqQIOB b 30112008 b quOOB F BOquOB P 1113003 424 1818 Turing Machines as Acceptors 0 1 6 A sextuple M QEF757 107F o F is the set of final states o If M halts in a state q E F then the input is accepted o If M halts in a state q g F the input is rejected o LM is the set of strings accepted by M 425 Turing Machines as Acceptors 2 0012 UUL 11R 11L BBRUBRBBL UBL lBRBBL A machine that accepts a string which is an even length palindrome of 039s and 139s eg 0001100001001000 E LM Exercise Modify the even length palendrome machine to accept odd length palindromes too eg 101 001 UUL 11R 11L UBRBBL UBL lBR 1313 00 R BBR 427 1819 Turing Machines in Prolog 0 given deltaltState SymNewState NewSymLR o maybe given acceptingltStategt for accepting states o We can write a Turing machine simulator in Prolog o So Prolog can do anything a Turing machine can deltaq0 7B7 ql 713 right deltaq1 7B7 qz 7B7 left deltaq1 a ql 1 right deltaq1 b ql a right deltaq2 a 12 a left deltaq2 b 12 1 left initia1q0 Main Code runInput Output State initia1State0 tapeilistipositionTape0 Input 0 runState0 TapeO State Tape tapeilistipositionqape Output recognize nput runInput 7 State acceptingState State Transition runState0 Tape0 State Tape stepState0 Tape0 State1 Tapel a runState1 Tape1 State Tape State State0 Tape Tape0 stepState0 Tape0 State Tape replaceitapeisy39mbolTape0 Sy39mO Tape1 Syml deltaState0 Sy39mO State Sy39ml Direction movetapeDirection Tape1 Tape l39 4quot theTape 1isttapepositionList tape Left Right Pos 1engthLeft Pos reverse Left Left1 appendLeft1 Right List replaceitapeisy39mbol tape Left0Right0 Sy39mO tape Left0Right Sy39m replaceinextiofiinfiniteitapeRight0 Sy39mO Right Sy39m moveitape left tape Lsy39m I Left Right tape Left Lsy39m I Right moveitape right tape Left Right tape Rsy39m ILeft Right1 replaceinextiofinfiniteitapeRight Rsym IRightl Rsym replaceinextiofinfiniteitape SymOIRest Sy39mO Sy39mIRest Sy39m replaceinextiofinfiniteitape 7B7 Sym Sym 431 182 Nondeterministic Turing Machines o 6 maps to a subset of Q x F x LR rather than just one or zero o Computation chooses which one to take o A non deterministic Turing machine M accepts input 3 if some possible computation accepts 3 Important result Any language accepted by a non deterministic Turing machine can be accepted by a deterministic Turing machine Example ch ch a aaL A machine which accepts strings of as b s and Cs where there is a 8 followed by or preceded by ab Example 2 qoBacabB 1 qoBacabB 1 qoBacabB 2 F Bq1acabB 1 F BqlacabB 1 F Bq1acabB 2 F Baq1cabB 1 F BaqlcabB 1 F Baq1cabB 3 F BacqlabB 1 F BacqzabB 2 F quacabB F Bacaql b3 1 F Bacaq4bB 1 F Bacabq1B F Basalqu First and third do not accept but second does That39s good enough the machine accepts

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

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