Derive a characteristic function for L(M).

Onion diagram slide 1

• We've reached the outer two rings of the language hierarchy

† What it means to decide a language-- deciding means yes or no, a string is definitely in the language or definitely not TMs can decide aⁿbⁿcⁿ but a PDA cannot -- aⁿbⁿcⁿ ∉ CFLs accepts w if w ∈ L rejects w if w ∉ L

† What it means to semidecide a language accepts w if w ∈ L if w ∉ L, it may reject w, or it may loop forever

• Sample language hierarchy questions that could easily appear on an exam:

T If L contains a finite number of elements then it must be semidecidable. What is the inner-most layer of the the onion diagram that L belong to? key concept: the subset relationship of the onion diagram layers F L ∈ SD → L ∈ D D is a proper subset of SD, so there must be at least one L in SD that is not in D

T = { J : J is Java source code that declares all variables before using them} L ∈ D It's equivalent to saying that L ∈ D, L= { wcw : where w is some word}

F L = { <J,w> : J is Java source code that compiles into code that halts on string w} L ∈ D — stay tuned for next time, it's semi-decidable. You can tell if <J,w> ∈ L -- compile J, run it, supply w as input, and see if it halts. If you run it, and wait a long time and nothing happens, does that the program never halt? It could just be taking a long time. So you can't tell the diffence between <J,w> ∉ L, and the program just taking a long time

T = { <J> : J is Java source code that compiles into code that outputs "a"} L ∈ SD L ∉ D

program 1 ∈ L: System.out.println("a"); - this one line program is in L

program 2 ∉ L: System.exit(1); //not in J

program 3 may or not be in L: while(true) { continue; }

program 4 may or not be in L: int j while(j < 2,400,00) { System.out.println(math.factorial(j++)); }

TMs raw lecture notes Page 1

System.out.println("a");

F L = { <J> : J is Java source code that compiles into code that only outputs "a" one time} L ∈ SD

program 1 ∈ L: System.out.println("a"); - this one line program is in L

program 2 ∈ L: System.out.println("aa"); - this one line program is not in L

program 3 L : System.out.println("a"); while(true) { continue; }

program 4: System.out.println("a"); int j while(j < 2,400,00) { System.out.println(math.factorial(j++)); } System.out.println("a");

If you were running these programs, you would not necessarily be able to tell the difference between 3, which is in the language, and 4, which is not. So you would only function as a semi-decider.

So not only could you not decide if J ∉ L, you couldn't even decide if J ∈ L.

In these thought experiments, you who run the programs, play the role of deciding of semideciding (hopefully) TM.

Recall the lab we did on the first day of course.

You can consider J in the last 4 examples to be equivalent to a TM, a formalism for expressing an algorithm. (A much more expressive formalism!)

• TMs are a conceptual device used to explore the question of what can be computed. Since all problems can be translated into language recognition problems, "what is computable" is equivalent to a decidable language.

† Gödel’s Incompleteness Theorem — there will always be true statements that can not be proven from a set of axioms (incompleteness), or the axioms cannot be proven to never entail both P and ¬P (inconsistency). (see Peano axioms on slide 10)

† The Entscheidungsproblem ("Decision problem"). In 520, we call it deciding a language, equivalent to deciding if a 1st order (including the ∀ and ∃ quanifiers) can be proven from a set of axioms.

TMs raw lecture notes Page 2

† The mathematician Alan Turing developed his machines as a mechanical way of computing any computable function.

• Formal definition of TM

A Turing machine M is a sixtuple (K, Σ, Γ, δ, S, H):

• K is a finite set of states; • Σ is the input alphabet, which does not contain ☐ • Γ is the tape alphabet, which contains ☐. Σ ⊂ Γ • S ∈ K is the initial state; • H ⊆ K is the set of halting states; • δ is the transition function

( (K - H) × Γ) → (K × Γ × {→, ←} )

non-halting × tape state × tape × action state char char (R or L)

Because δ is function, this is a deterministic TM — but nondeterministic TMs accept the same set of languages as deterministic TMs (like FSMs, and unlike PDA). Also, multi-tape TMs accept the same set of language as single-tape TMs.

Are we done? Is there anything beyond the outer ring? (see slides 6 and 7). Would another ring representing languages s semidecided by quantum computers

The Church-Turing thesis: There is nothing beyond the outer ring. All formalisms powerful enough to describe everything we think of as a computational algorithm are equivalent. All such formalisms allow unrestricted access to unlimited memory.

Most computer scientists accept the CTT, but there are dissenters. (See "The Church- Turing Thesis: Logical Limit or Breachable Barrier?)

Example TM langauge recognizers in slides 33 & 34, 23 for an advanced one.

Example TM to compute a function (see slide 24)

Fun TM Facts 1. The input tape is infinite in both directions.

2. δ must be defined for all possible (state, input) pairs unless the state is a halting state. But unlike DFSM diagrams, which show transitions from every state for every symbol in ∑, transitions on a symbol in Γ that could not occur from a particular state may be omitted.

TMs raw lecture notes Page 3

3. TM's can completely ignore their input, and do not necessarily halt (unlike FSM's and PDAs). For example, a TM could simply replace a ☐ with an a, and move one square to the left or right, ad infinitum. Remember, to halt a TM must enter a halting state, but there is no requirement that they do so.

4. The contents of the tape when a TM halts could be considered as the output of a function.

5. By convention, a TM starts with it's R/W head on the ☐ the left of the input. But we could use other conventions if convenient.

6. At every step, a TM writes a symbol from Γ on the tape, and moves one square to the left or right.

7. At any stage in a computation, a tape can contain only a finite number on non-☐ symbols.

8. ☐ ∉ ∑, but is always ∈ Γ, and can be read and written just like any other symbol in the tape alphabet.

Definition of active tape (see slide 16)

• Universal Turing Machines (UTMs). Think of them as being like general purpose computer. A UTM can emulate any other TM, just like a stored program computer can run any program that compiles into its machine language. 


TMs raw lecture notes Page 4

In: ℇ, a, ab, ba Out: b, baab ☐☐☐☐ℇ☐☐☐☐ for ℇ ∈ L(M), then M must end up in the "y" state when processing ℇ. ^ ☐☐☐☐b$$b☐☐☐☐ ^ L(M) { w : #a(w() % 2 = 1 and w cannot start with a b} --------------------------------------------- | | v a a | >Ra,☐ --------------> $L☐Ra,☐ ---------------->$L☐ | | | |☐ | | | v |☐ y | v ∑ = {a,b} L☐ Γ = {a,b,☐,$} | H = {y,n} | L(M) = {w : w = } | | v b R -------------------> n | |☐,$ | v y

TMs raw lecture notes Page 5