Week1_lecture2_2020115002.md

Week 1, Lecture 2

Countable Sets

An infinite set is countable if there is a bijection f : N -> S from the natural numbers to S.

Theorem:

The set of finite length bit strings {0,1}* is countable.

Uncountable Sets

A set is uncountable if it is not countable.

Theorem:

The power set of bit strings P({0,1}*) is uncountable.

Proof:

Any subset T in P ({0,1}) can be viewed as a function f:{0,1} -> {0,1}. This is done by making the function take the value 1 for elements in the set, and the value 0 for elements not in the set.

Suppose that P ({0,1}) were countable. Thus it would be possible to find a bijection from N to P({0,1}) Hence, we can list all binary languages as a sequence L1 , L2 , L3 , L4 , L5 , L6 , L7, ... supposedly containing every language of bit strings.

Cantor’s Diabolical Diagonal:

Cantor’s diabolical diagonalization argument creates a language L that’s not on the list. This would prove that P({0,1}*) is not countable.

L is created as follows:

The j^th column of L is the opposite of the j^th column of the j^th row L_i. In other words, L is the anti-diagonal of the table. This guarantees that L disagrees with every listed language (L_i differs in the i^th column)

Connecting to computing

Theorem:

There are computational problems that computers cannot solve!

Proof:

We show that there are many more computational problems than computer programs.

• Every computer program can be encoded in binary by some string.

• Consequently the cardinality of the set of programs is no greater than that of {0,1}*

• Since {0,1}* is countable, set of all programs is countable.

• Problems are (membership queries) in Languages.

• Hence, the set of all problems has the same cardinality as P({0,1}*)

• Since P({0,1}*) is uncountable, set of all problems is uncountable.

Turing Machine

• TM is a 7-tuple (Q, Σ, Γ, δ, q₀, q_accept, q_reject)
  • Q is the finite set of states.
  • Σ is the finite input alphabet set, not containing blank.
  • Γ is the finite tape alphabet, with blank.
  • δ : (Q x Γ) to (Q X Γ x {L,R}) is the transition function.
  • q₀ is the start state.
  • q_accept is the accept state.
  • q_reject is the reject state.