[PDF] CS 373: Theory of Computation L is said to be

View - Download CS 373: Theory of Computation

Previous PDF

Next PDF

CS 373: Theory of Computation

Gul Agha Mahesh Viswanathan

Fall 20101

1 High-Level Descriptions of Computation

High-Level Descriptions of Computation

Instead of giving a Turing Machine, we shall often describe a program as code in some programming language (or often \pseudo-code") {Possibly using high level data structures and subroutines Inputs and outputs are complex objects, encoded as strings

Examples of objects:

{Matrices, graphs, geometric shapes, images, videos,::: {DFAs, NFAs, Turing Machines, Algorithms, other machines:::High-Level Descriptions of Computation

Encoding Complex Objects

\Everything" nite can be encoded as a (nite) string of symbols from a nite alphabet (e.g.

ASCII)

{Can in turn be encoded in binary (as modern day computers do). No specialtsymbol: use self-terminating representations

Example: encoding a \graph."

(1,2,3,4)((1,2)(2,3)(3,1)(1,4)) encodes the graph12 34

High-Level Descriptions of Computation

We have already seen several algorithms, for problems involving complex objects like DFAs,

NFAs, regular expressions, and Turing Machines

{For example, convert a NFA to DFA; Given a NFANand a wordw, decide ifw2L(N); All these inputs can be encoded as strings and all these algorithms can be implemented as

Turing Machines

Some of these algorithms are for decision problems, while others are for computing more general functions

All these algorithms terminate on all inputs

2

High-Level Descriptions of Computation

Examples: Problems regarding Computation

Some more decision problems that have algorithms that always halt (sketched in the textbook) On inputhB;wiwhereBis a DFA andwis a string, decide ifBacceptsw. Algorithm: simulateBonwand accept i simulatedBaccepts On inputhBiwhereBis a DFA, decide ifL(B) =;. Algorithm: Use a xed point algorithm to nd all reachable states. See if any nal state is reachable. Code is just data: A TM can take \the code of a program" (DFA, NFA or TM) as part of its input and analyze or even execute this code Universal Turing Machine(a simple \Operating System"): Takes a TMMand a stringwand simulates the execution ofMonw2 Deciding vs. Recognizing

Decidable and Recognizable Languages

Recall: Denition

A Turing machineMis said torecognizea languageLifL=L(M). A Turing machineMis said todecidea languageLifL=L(M) andMhalts on every input. Lis said to beTuring-recognizable(or simply recognizable) if there exists a TMMwhich recognizesL.Lis said to beTuring-decidable(or simply decidable) if there exists a TMMwhich decidesL. Every nite language is decidable: For example, by a TM that has all the strings in the language \hard-coded" into it We just saw some example algorithms all of which terminate in a nite number of steps, and

output yes or no (accept or reject). i.e., They decide the corresponding languages.2.1 An Undecidable but Recognizable Language

Decidable and Recognizable Languages

Butnot all languages are decidable! In the next class we will see an example: {Atm=fhM;wi jMis a TM andMacceptswgis undecidable

HoweverAtmisTuring-recognizable!

Proposition 1.There are languages which are recognizable, but not decidable 3

RecognizingAtm

ProgramUforrecognizingAtm:

On inputhM;wi

simulateMonw if simulatedMacceptsw, then accept else reject (by moving toqrej)

U(the Universal TM) acceptshM;wiiMacceptsw. i.e.,

L(U) =Atm

ButUdoes notdecideAtm: IfMrejectswby not halting,UrejectshM;wiby not halting. Indeed (as we shall see) no TM decidesAtm.2.2 Complementation

Deciding vs. Recognizing

Proposition 2.IfLandLare recognizable, thenLis decidable

Proof.ProgramPfordecidingL, given programsPLandPL

for recognizingLandL:

On inputx, simulatePLandPL

on inputx. Whetherx2Lorx62L, one ofPLandPL will halt in nite number of steps. Which one to simulate rst? Either could go on forever.

On inputx, simulatein parallelPLandPL

on inputxuntil eitherPLorPL accepts

IfPLaccepts, acceptxand halt. IfPL

accepts, rejectxand halt.Deciding vs. Recognizing

Proof (contd).In more detail,Pworks as follows:

On input x

fori= 1;2;3;::: simulatePLon inputxforisteps simulatePL on inputxforisteps if either simulation accepts, break ifPLaccepted, acceptx(and halt) ifPL accepted, rejectx(and halt) 4 (Alternately, maintain congurations ofPLandPL , and in each iteration of the loop advance both their simulations by one step.)Deciding vs. Recognizing

So far:

Atmis undecidable (next lecture)

But it is recognizable

Is every language recognizable?No!

Proposition 3.A

tmis unrecognizable

Proof.IfA

tmis recognizable, sinceAtmis recognizable, the two languages will be decidable too!Note: Decidable languages are closed under complementation, but recognizable languages are

not.3 Recursive Enumeration

3.1 Enumerators

Enumeratorswrite only output taperead/write work taperead/write work tape nite-state controlAn enumerator is multi-tape Turing Machine, with a specialoutput tapewhich iswrite-only {Write-only means (a) symbol on output tape does not aect transitions, and (b) tape head only moves right. Intially all tapes blank (no input). During computation the machine adds symbols to the

output tape. Output considered to be alist of words(separated by special symbol #)Recursively Enumerable Languages

5 Denition 4.An enumeratorMis said toenumeratea stringwif and only if at some pointM writes a wordwon the output tape.E(M) =fwjMenumerateswg Note Mneed not enumerate strings in order. It is also possible thatMlists some strings many times!

Denition 5.Lisrecursively enumerable (r.e.)i there is an enumeratorMsuch thatL=E(M).3.2 Equivalence of Enumerating and Recognizing a Language

Recursively Enumerable Languages and TMs

Theorem 6.Lis recursively enumerable if and only ifLis Turing-recognizable. Note Hence, when we say a languageLis recursively enumerable (r.e.) then there is a TM that acceptsL, and there is an enumerator that enumeratesL.Recognizers From Enumerators Proof.SupposeLis enumerated byN. Need to constructMsuch thatL(M) =E(N).Mis the following TM

On inputw

RunN. Every timeNwrites a word `x'

comparexwithw.

Ifx=wthen accept and halt

else continue simulatingN Clearly, ifw2L,Macceptsw, and ifw62LthenMnever halts.Enumerators From Recognizers?

Parallel simulation?

Proof (contd).LetMbe such thatL=L(M). Need to constructNsuch thatE(N) =L(M).N is the following enumerator forw=;0;1;00;01;10;11;000;:::do simulateMonw ifMacceptswthen write the word `w' on output tape 6 DoesNenumerateL?No!!Mmay not halt on a stringw62L, in which caseNwill not output any more strings! Must simulateMon all inputs in parallel. But innitely many parallel executions. Will never reach step two in any execution!Enumerators From Recognizers

Dovetailing

Proof (contd).LetMbe such thatL=L(M). Need to constructNsuch thatE(N) =L(M).N is the following enumerator fori= 1;2;3:::do letw1;w2;:::wibe the firstistrings (in lexicographic order) simulateMonw1foristeps, then onw2fori steps and ...simulateMonwiforisteps ifMacceptswjwithinisteps then writewj (with separator) on output tape Observe thatw2L(M) iNwill enumeratesw.Nwill enumerate strings many times!7quotesdbs_dbs17.pdfusesText_23

[PDF] prove that any two open intervals (a

[PDF] prove that if both l1 and l2 are regular languages then so is l1 l2

[PDF] prove that if f is a continuous function on an interval

[PDF] prove that if f is bijective then f inverse is bijective

[PDF] prove that if lim sn and lim tn exist

[PDF] prove that if t ? l(v satisfies t 2 t then v = null t ? range t)

[PDF] prove that lr is context free for every context free language l

[PDF] prove that range(t + s) ? range(t) + range(s).

[PDF] prove that the class of non regular languages is not closed under concatenation.

[PDF] prove that the interval (0

[PDF] prove the inverse of a bijective function is bijective

[PDF] proverbe créole martiniquais traduction

[PDF] provided that logic

[PDF] providing health equity

[PDF] proview caqh sign in