CSCI 161 Chapter 5: Reducability
4 Dec 2020
School
Department
Course
Professor
Document Summary
Undecidable problems from language theory e. a. halting problem : halt ,- determine whether tm halts ( accent i reject) on a given input . = elm , w ) / m is a tm & m hulls on inpot w} I or is atm d l cmj = 03. Regular tin given tm has an equivalent fa ! recognize a res. = {( m) / m is a tm a lcm ) is. Testing the equivalence of 2 tm is undecidable. Eqtm = {( mi , ma) / mi & mz aretms & lcm d=lcm)} Alba = determine whether an l ba accepts its input . Ausa = {44 : / m is an lba that accepts string w } Elba = elm> l m is an lba where lcm ) =d } All ={(g) ig is a cfg & lcd = 8*3. Mapping reducibility (cid:15482) computable function converts instances of problem a to instances of problem b .
