Class Note for C SC 473 at UA
Popular in Course
Popular in Department
This 4 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Arizona taught by a professor in Fall. Since its upload, it has received 13 views.
Reviews for Class Note for C SC 473 at UA
Report this Material
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
C SC 473 Automata Grammars and Languages 1242007 Rice s Theorem cont Construct from input Mm a transformed program ltCltMwgt so that the following holds B ifws LM e PBtrue ClM39Wl lo ifwg LM e ma false Here is what the translator C constructs x V TIE ye t l CMwgt y Wquot Note if WE LM then LCltMwLMEB if we LME then LCMwgt So holds as desired With this reduction function we proceed to the reduction itself c SC on Autumn smut Laws Rice s Theorem Cont Reduction Suppose there is adecider MP for P N 2 MM 1 iC CMw M ye PL ltMWgtE LN ltgt ltCltMwgtgte LMP ltgt ltCltMwgtgte LP ltgt PLCltMwgt true ltgt LCltMwgt B ltgt we LM LN AW amp AW 3 LP Since the language ATM is undecidable so must L be undecidable c SC on Autumn smut Laws Rice s Theorem Cont Corollary Given a TM M the following properties of the language LM are all undecidable ls LM empty ls LM finite ls LM regular ls LM a CFL Is the stringfoo E LM Does LM have more than 3 members Does LM have fewer than 10 members c sconAmnmu swankMs 9 Lecture 08 3 C SC 473 Automata Grammars and Languages 1242007 Machine Dependent Problems Not all problems about TMrecognizable sets can be settled by Rice39s Theorem Rice39s Theorem only applies to properties of languages recggnized Properties of the TM itself might be decidable or undeciabIe the approach has to be ad hoc Ex Given a TM M does it have an even number of states Easilydecidable Ex Given TM Mq Is there any configuration with p q yielding a configuration with state 11 Decidable If there is a transition in B of form Bpa qpp p321 then yes else no We do not require any of these configurations to be reachable from the initial configuration C so on Autumn smut Laws Machine Dependent Problems Ex Undecidable MachineDependent Problem 111TM Predicate Given TM Mwith 1quot01blank does it ever print 3 consequtive139s on its tape for any input Reduction ETTM Sm 111TM reduction func in 2 stages M ltMgt Cl CZ ltM gt M uses 01 forO and 10for 1 making changes in the rules accordingly When M has a O in cellj then M has a0 in cell 2j and a 1 in cell 2j1 nevera 111 on tape C2 modi es M so that if M accepts M prints 111 and halts in the accept state M prints 111 cgt M accepts a cgt M accepts a C so on Autumn smut Laws Lecture 08 4
Are you sure you want to buy this material for
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'