**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:**

- Chapter 3.2 to end; chapter 3.3; chapter 4.1 through
theorem 4.3

**Skills:**

- Know new definitions, understand new concepts.
- Understand why enumerating in order is different from
general enumeration.
- Understand the proofs of the three theorems above

**Notes:**

·
**A****DFA** = {<D, w> : M is a DFA that accepts w}

**A****NFA**= {(<N, w> : M is
a NFA that accepts w}

**A****RE**= {<R, w> : B is a
regular expression that generates w}

·
**A****CFG**=
{(<G, w> : G is a CFG that
accepts w}

They are all *decidable*

**A****DFA**-decider would do the following on input <BD,w>:

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*

**A****NFA**-decider would do the following on input <N,w>

1)
Syntax check, reject if fails

2) D = NFA_DFA_Converter (<N>)

3) return DFA_decider (<D>)

**A****RE**-decider would do the following on input <R,w>

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