Lecture 18 (Enumerators), 11/6/17

Concepts, definitions (in italics):

·         Theorem: L is recognizable (decidable) by an NTM if and only if it is recognizable (decidable) by a regular TM [showed in last class]

·         Enumerating a set S or a language L

o   Examples: enumerating naturals; integers; pairs of naturals; (last time)

o   Examples: valid encodings of REs, DFAs, CFGs, TMs (given fixed Sigma)

·         Enumerating in order

·         TM enumerator: variant of a TM

·         TM-enumerable language

o   TM-enumerable also known as recursively enumerable.

·         Theorem: A language is TM-enumerable iff it is TM-recognizable;

·         Theorem: A language is TM-enumerable-in-order iff it is TM-decidable

o   Given a TM enumerator that enumerates some language L (in order), can create a TM recognizer that recognizes (decides) L

o   Given a TM recognizer (decider) for some language L, can create a TM enumerator that enumerates L (in order)

·         Church-Turing Thesis (CTT): Turing machines, lambda-calculus, and algorithms are equivalent

o   What is an algorithm?

·         CTT gives us a way to formalize the notion of an algorithm

o   A language is TM-decidable iff there exists an algorithm that determines, for any string, whether or not it is in the language.

·         Incorrect CTT: if something can be computed by some computer, it can be computed by some TM.

·         A language is decidable iff there exists a TM that decides it

o   Meaning, iff there an algorithm that determines, for any string, whether or not it is in the language.

·         TM inputs/outputs are can be anything that is encodable as a string.

o   Example: An algorithm for deciding if a given DFA accepts a given string is a decider for the language A-DFA

o   Example: An algorithm for deciding if a given RE  generates a given string is a decider for the language A-RE

·         L1 is reducible to L2 if the decider for L2 can be used as a subroutine to create a decider for L1

·         Theorem: The languages A-DFA, A-NFA, A-RE, A-CFG are decidable [we will prove for A-CFG next time]

Reading:

Skills:

Notes:

·         ADFA = {<D, w> : M is a DFA that accepts w}
ANFA= {(<N, w> : M is a NFA that accepts w}
ARE= {<R, w> : B is a regular expression that generates w}

·         ACFG= {(<G, w> : G is a CFG  that accepts w}
They are all decidable

1) If this input is not properly formatted we reject
2) Simulate D on w
3) If you end up in a FINAL state, accept; else reject

1) Syntax check, reject if fails
2) D = NFA_DFA_Converter (<N>)
3) return DFA_decider (<D>)

1) Syntax check, reject if fails
2) N = RE_NFA_converter (<R>)
3) Return A_NFA_decider (<N, w>)

·         Here is a link to a great paper about the history of the incorrect CTT:
Refuting the Strong Church-Turing Thesis: the Interactive Nature of Computing (PDF)
Minds and Machines, 18:1, pp.17-38, March 2008