### 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(36)

### View Full Document

## 14

## 0

## Popular in Course

## Popular in Department

This 14 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(36)

### 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 Recall From Last Time Lecture 7 Th 62 The busy beaver function 0n is eventually larger than any total recursive function Th 63 There is a Universal Turing Machine U such that UPnam Mum Thm 64 Unsolvability 0f Halting Problem Let HALT Pn m 1 TM eventually halts Then HALT is re but not recursive Listing of all re sets W0 W1 W2 W in 1 Mil 1 Cor 66 Let K in Mltngt1 in mam 1 n I n E Wn Then K E re Recursive Notation Mna means that TM Mn converges on in put 33 ie Mnai gt MnaEN gt Fundamental Th of re Sets Let S g N TFAE 1 S is the domain of a partial recursive function ie 3W5 d0mMn39 93 EN 1 Mn93i 2 S Z or S is the range of a total recursive function ie S Z or S rangeMn MAN for some total recursive function 3 S is the range of a partial recursive function ie S MAN for somen E N 4 S is re ie S W for some n E N Proof Please learn this proof 1 gt 2 Assume 1 S 2 I case 1 S Z Thus 5 satis es 2 case 2 5 Z let a0 6 S From Mn compute MT which on input z does the follow ing 1 a Lz 31 Rz ie z Pay 2 run for y steps 3 if it halts then returna 4 else returna0 Claim 5 MAN I a E N MTltNgt g s MAN 2 5 Suppose a E 5 Thus converges in some number y of steps Therefore MTP1 13 Noncomputable step in construction no way to tell if we are in case 1 or case 2 2 gt 3 Assume 2 HS 2 thhen S M0N where M0 is a Turing machine that halts on no inputs Otherwise S MAN ie S is the range of the partial recursive function Note Even though is total it is still considered a partial recursive function However of course is not strictly partial 3 gt 4 Assume 3 S From Mn construct Md which on input a does the fol lowing l fori ltooo 2 run MAO Mn1 for 239 steps each 3 if any of these output 13 then returnl above construction called dovetailing Claim Md p5 Ifa E S then a E rangeMn MHU 2 computation takes k steps for some 339 k Thus at round 239 maxj k Mda will halt and output 177 If a e S then Mda will never halt ThusS Wd 2 13 I Mda l 4 gt 1 Assume 4 and thus 5 W S 2 i Z 1 From Mn construct Md which on input a does the fol lowing 1 run 2 if 1 then return1 3 else run forever 5 93 I Md93i ThusS domMd 2 I Mda Q CMPSCI 601 Reductions Lecture 7 De nition 71 We say that S is reducible to T S g T iff 3 total recursive f N gt N VwEN 1065 ltgt gamer A Note Later we require f E FDSPACElog 14017 in Mn017 Claim K g A047 Proof De ne f as follows erase input if 1 then write 17 Mfm write n Mn else 100p Tl E K gt 2 gt Z gt E Aggy Q Fundamental Th of Reductions If S g T then 1 lfT is re then S is re 2 lfT is core then S is core 3 If T is Recursive then S is Recursive Moral Suppose S g T Then lfT is easy then so is S HE is hard then so is T Proof Let f S g T ie E S gt fa E T 1 Suppose T W 2 I 1 From M compute the TM Mir which on input a does the following a compute f b run MAM Miquot f M w E 5 ltgt x 6 T ltgt Mzf93 1 ltgt Maw 1 Therefore 5 Wiz and S is re as desired 8 f S lt T 16 E S gt fa E T 2N0teS T gt T T E cone T E re g E re S E core 3 T E Recursive gt T E re T E cone gt S E re S E core gt S E Recursive De nition 72 Let C lt N C is recomplete iff 1 C E ne and 2 VA 6 re A g C Intuition C is a hardest re set In the g ordering it is above all other re sets Q 10 Theorem 73 K is 716 complete Proof Let A E re ie A W6 for some 239 Wanted Vnn E A gt f E K De ne the recursive function f which on input n com putes the following TM M Erase input Write n Mi n E A gt 1 gt V23Mfna 1 ltgtMfnltfltngtgt1 ltgt MM 11 Proposition 74 Suppose that C is icecomplete and the following hold I S E re and 2 C 3 S then S is 1 16 complete Proof Show VA 6 reA g 5 Know VA 6 reA g C Follows by transitivity of g A g C 3 S Q Corollary 75 A047 is icecomplete Every icecomplete set is 1 16 and hot recursive 12 HALT Pn m 1 TM eventually halts Proposition 76 HALT is Icecomplete Proof We have already seen that HALT is re It thus suf ces to show that K g HALT We want to build a total recursive f such that for all 10 E N w E K gt fw E HALT 1 gt halts That is we want 1 gt MAT halts where fw P r Given 10 let M aw Erase input Write 111 M w igl e igellgg Letting f PE39w 0 we have that 1 gt Mgw0 halts gt fw E HALTQ l3 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 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

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

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

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