### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Class Note for CMPSCI 601 at UMass(39)

### View Full Document

## 14

## 0

## Popular in Course

## Popular in Department

This 12 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 14 views.

## Similar to Course at UMass

## Popular in Subject

## Reviews for Class Note for CMPSCI 601 at UMass(39)

### 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: 02/06/15

CMPSCI 601 Turing Machines Lecture 4 M QE6s Q nite set of states 8 E Q E nite set of symbols D U E E 6 Q X E gt QUh XX X e gt S EIIOIUUn CMPSCI 601 Example TM Lecture 4 mVRttm S q go 11 O 80 gt q0U gt 1 81 gt q1U gt H 114 80lt 81lt D sD gt hD comment nd U memorize change change amperase UtoO Utol 8 El 101d M 8 D i101 u u 8 D 1 i 01 u u 8 D 1 1 Q 1 u u 8 D110 i u u S D1101 u u q D110 l u u ql D110 14 u u 8 D110 14 1 1J mVRttm S q go 11 O 80 gt qoU gt 1 81 gt q1U gt H 114 80lt 81lt D sD gt hD S E 01 U 14 Q1 D110 U U U s D110 141m q gt1 1 U 1 1J qo Dl 1U U 1U 8 D11 U 0114 q E J 10114 h E U 101 CMPSCI 601 TM History Lecture 4 Hilbert s Program 1901 Give a complete axiomization of all of mathematics Such a complete axiomization would have provided a mechanical procedure to churn out exactly all true state ments in mathematics This led to active interest in 1930 s in the question What is a mechanical procedure Church Lambda calculus Godel Recursive function Kleene Formal system Markov Markov algorithm Post Post machine Turing Turing machine Fact The above models are all de ne exactly the same class of computable functions ChurchTuring Thesis The intuitive idea of effectively computable is captured by the precise de nition of com putable in any of the above models 4 CMPSCI 601 TM Philosophy Lecture 4 Why is a Turing machine as powerful as any other com putational model Intuitive answer Imagine any computational device It has 0 Finitely many states 0 Ability to scan limited amount per step one page at a time 0 Ability to print limited amount per step one page at a time 0 Next state determined by current state and page cur rently being read but what about randomization Note Without the potentially in nite supply of tape cells paper extra disks extra tapes etc we have just a poten tially huge nite state machine The PC on your desk with 20 GB of hard disk is a nite state machine with over 21607000900900 states This is better modeled as a TM with a bounded number of states and an in nite tape actually meaning a nite memory that expands whenever necessary 5 CMPSCI 601 TM Functions Lecture 4 y if M on input Mud eventually E halts with output Dle otherwise 20 E E gt U Usually 20 0 1 De nition 41 Let f 26 gt 26 be a total or partial function We say that f is recursive iff El TM M f M ie W E 26 fw MW 4 Remark 42 There is an easy to compute 1 and onto map between 0 l and N Thus we can think of the contents of a TM tape as a natural number and talk about f N gt N being recursive We may visit this issue in H W2 Partial function f N gt N is a total function f D gt N where D g N A partial function that is not total is called strictly partial If n E N D f 2 CMPSCI601 Recursive re sets Lecture4 De nition 43 Let S g 25 or S g N S is a recursive set iff the function X3 is a total recursive function 1 lf S ES W 0 otherwise 5 is a recursively enumerable set S is re iff the func tion p3 is a partial recursive function 1 lf S ES mm 2 otherwise Proposition 44 If S is recursive then S is re Proof Suppose S is recursive and let M be the TM com puting X3 Build M simulating M but diverging if M 0 Thus M computes p3 Q CMPSCI 601 Some Recursive Functions Lecture 4 Proposition 45 T he following functions are recursive They are all total except for peven n1 ngtltm nm 2 nm 1 ifniseveh Xevenm 0 otherwise 1 ifn is even 01 otherwise Proof Exercise please convince yourself that you can build TMs to compute all of these functions Q CMPSCI601 Recursive 2 re 0 core Lecture4 If C is any class of sets de ne coC to be the class of sets Whose complements are in C coC 51366 Theorem 46 S is recursive l39 S and g are both 1 16 Thus Recursive re core Proof If S E Recursive then X3 is a recursive function Thus so is X a l X3a Thus 5 and g are both recursive and thus both re 10 Suppose S E re cone mMW mMW De ne T MIIM on input 1 form 2 1tooo 2 run for n steps 3 if 1 in n steps then return1 4 run M a for n steps 5 if M 1 in n steps then return0 Thus 2 X3 and thus 5 E Recursive 11 mm Arlthmetlc H1erarchy W c0re Recursive 139 e re complete Primitive Recursive EXPTIME PSPACE c0NP PolynomialTime Hierarchy complete c0NP NP NP 1 c0NP NP complete quottruly feasiblequot NC NC2 logCFL SAC NSPACE log n 3 DSPACE log n Regular LogarithmicTime Hierarchy 12

### 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 used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

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

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