cs2102: Discrete Math (Fall 2016)

Submitting Problem Set Omega (Sun, 27 Nov 2016)

The form for submitting Problem Set Omega is here:

Class 23: Universal Machines (Sat, 19 Nov 2016)

### Schedule

**Problem Set 9** is tomorrow, **Wednesday, 23 November** at **6:29pm**.

**Problem Set Omega** is now posted and due on **Sunday,
4 December** or **Tuesday, 6 December** (see problem set for
details). It is not like the others, and counts as a “bonus”
optional assignment.

## Turing Machine

$$
TM = (S, T \subseteq S \times \Gamma \rightarrow S \times \Gamma \times \text{\em dir}, q*0 \in S, q*{Accept} \subseteq S)
$$

$S$ is a finite set (the “in-the-head” processing states)

$\Gamma$ is a finite set (symbols that can be writte on the tape)

$\text{\em dir} = { \text{\bf Left}, \text{\bf Right}, \text{\bf Halt} }$ is the direction to move on the tape.

An *execution* of a Turing Machine, $TM = (S, T \subseteq S \times \Gamma \rightarrow S \times \Gamma \times \text{\em dir}, q*0 \in S, q*{Accept} \subseteq S)$, is a (possibly infinite) sequence of **configurations**, $(x_0, x_1, \ldots)$ where $x_i \in \text{\em Tsil} \times S \times \text{\em List}$ (elements of the lists are in the finite set of symbols, $\Gamma$), such that:

```
- $x_0 = (\text{\bf null}, q_0, \text{\bf input})$
- and all transitions follow the rules (need to be specified in detail).
```

## Machines and Languages

A **language** is a (possibly infinite) set of *finite* strings.

$\Sigma$ = alphabet, a finite set of symbols

$L \subseteq \Sigma^{*}$

$$L_{XOR} = { x_0x_1\ldots x_n + y_0y_1\ldots y_n = z_0z_1\ldots z_n \$ | x_i \in {0, 1}, y_i \in {0, 1}, z_i = x_i \oplus y_i }$$

## Turing Machine Computation

A Turing Machine, $M = (S, T \subseteq S \times \Gamma \rightarrow S \times \Gamma \times \text{\em dir}, q*0 \in S, q*{Accept} \subseteq S)$, **accepts** a string *x*, if there is an execution of *M* that starts in configuration $(\text{\bf null}, q_0, x)$, and terminates in a configuration, $(l, q_f, r)$, where $q*f \in q*{Accept}$.

A Turing Machine, $M = (S, T \subseteq S \times \Gamma \rightarrow S \times \Gamma \times \text{\em dir}, q*0 \in S, q*{Accept} \subseteq S)$, **recognizes** a language $L$, if for all strings $s \in L$, $M$ accepts $s$, and there is no string $t \notin L$ such that $M$ accepts $t$.

```
TuringMachine = namedtuple('TuringMachine', ['rules', 'q_0', 'q_accepting'])
def simulate(tm, starttape):
tape = starttape
headpos = 0
currentstate = tm.q_0
while True:
readsym = tape[headpos]
if (currentstate, readsym) in tm.rules:
(nextstate, writesym, dir) = tm.rules[(currentstate, readsym)]
tape[headpos] = writesym
currentstate = nextstate
else:
return currentstate in tm.q_accepting # no rule, halt
if dir == 'L':
headpos = max(headpos - 1, 0)
elif dir == 'R':
headpos += 1
if len(tape) <= headpos: tape.append('_') # blank
else: # assert dir == 'Halt'
return currentstate in tm.q_accepting
xorm = TuringMachine(
rules = { ('S', '0'): ('R0', '-', 'R'), ('S', '1'): ('R1', '-', 'R'),
('S', '+'): ('C', '+', 'R'),
('R0', '0'): ('R0', '0', 'R'), ('R0', '1'): ('R0', '1', 'R'),
('R1', '0'): ('R1', '0', 'R'), ('R1', '1'): ('R1', '1', 'R'),
('R0', '+'): ('X0', '+', 'R'), ('R1', '+'): ('X1', '+', 'R'),
('X0', 'X'): ('X0', 'X', 'R'), ('X1', 'X'): ('X1', 'X', 'R'),
('X0', '0'): ('Y0', 'X', 'R'), ('X0', '1'): ('Y1', 'X', 'R'),
('X1', '0'): ('Y1', 'X', 'R'), ('X1', '1'): ('Y0', 'X', 'R'),
('Y0', '0'): ('Y0', '0', 'R'), ('Y0', '1'): ('Y0', '1', 'R'),
('Y1', '0'): ('Y1', '0', 'R'), ('Y1', '1'): ('Y1', '1', 'R'),
('Y0', '='): ('Z0', '=', 'R'), ('Y1', '='): ('Z1', '=', 'R'),
('Z0', 'X'): ('Z0', 'X', 'R'), ('Z1', 'X'): ('Z1', 'X', 'R'),
('Z0', '0'): ('B', 'X', 'L'), ('Z1', '1'): ('B', 'X', 'L'),
('B', '0'): ('B', '0', 'L'), ('B', '1'): ('B', '1', 'L'),
('B', '+'): ('B', '+', 'L'), ('B', 'X'): ('B', 'X', 'L'),
('B', '='): ('B', '=', 'L'), ('B', '-'): ('S', '-', 'R'),
('C', 'X'): ('C', 'X', 'R'), ('C', '='): ('C', '=', 'R'),
('C', '$'): ('Accept', '$', 'Halt') },
q_0 = 'S', q_accepting = { 'Accept' })
simulate(xorm, list("00+10=10$"))
```

Exam 2 Solutions (Sat, 19 Nov 2016)

The solutions to Exam 2 are here: Exam 2 Solutions. You should, of course, expect to see questions like these again on the final.

Class 22: On Computable Numbers (Thu, 17 Nov 2016)

### Schedule

**Problem Set 9** is now due on **Wednesday, 23 November**.

**Problem Set Omega** is now posted and due on **Sunday,
4 December** or **Tuesday, 6 December** (see problem set for
details). It is not like the others, and counts as a “bonus”
optional assignment.

# Links

Fernando Gouvea, *Was Cantor Surprised?*. American Mathematical Monthly, March 2011.

A. M. Turing, *On Computable Numbers, with an Application to the Entscheidungsproblem*, 1936.

# Cantor’s Continuum “Hypothesis”

Aleph-naught: $\aleph_0 = |\mathbb{N}|$ is the *smallest infinite
cardinal number*.

Recall: $\omega$ is the *smallest infinite ordinal*. The first ordinal after
$0, 1, 2, \cdots$.

$$2^{\aleph_0} = |pow(\mathbb{N})| = | [0, 1] | = | \mathbb{R} | = | {0, 1}^{\omega} | > |\mathbb{N} $$

What does it mean to say it is proven to not be possible to settle the question of whether $\aleph_1 = 2^{\aleph_0}$ with the ZFC axioms?

#

# On Computable Numbers

The “computable” numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means.(Alan Turing,On Computable Numbers, with an Application to the Entscheidungsproblem, 1936.)

Is $\tau$ computable (by Turing’s definition)? ($\tau = \frac{\text{Circumference of circle}}{\text{radius of circle}}$)

What are the problems with using the State Machine to model computation: $$M = (S, G \subseteq S \times S, q_0 \in S)$$

#

What was Turing attempting to model in defining what we know call a Turing Machine?

#

$$
TM = (S, T \subseteq S \times \Gamma \rightarrow S \times \Gamma \times \text{\em dir}, q*0 \in S, q*{Accept} \subseteq S)
$$

$S$ is a finite set (the “in-the-head” processing states)

$\Gamma$ is a finite set (symbols that can be writte on the tape)

$\text{\em dir} = { \text{\bf Left}, \text{\bf Right}, \text{\bf Halt} }$ is the direction to move on the tape.

##

What is the cardinality of the set of all Turing Machines?

#

Prove that there are numbers that cannot be output by any Turing Machine.

#

Problem Set Omega (Wed, 16 Nov 2016)

**Problem Set ω** is now posted and due Dec 4 or the last day of class (see the problem set for details). It is a “bonus” problem set, and not like the others.

Class 21: Infinite Infinites, Exam 2 (Tue, 15 Nov 2016)

### Schedule

**Problem Set 9** is now due on **Wednesday, 23 November**.

# Infinite Sets Recap

**Definition.** A set $C$ is *countable* if and only if there exists a
surjective function from $\mathbb{N}$ to $C$. (That is, $\le 1$ arrow
out from $\mathbb{N}$, $ge 1$ arrow in to $C$.)

**Definition.** A set $C$ is *countably infinite* if and only if there
exists a bijection between $C$ and $\mathbb{N}$.

# Cantor’s Theorem

For **all** sets, $S$, $| pow(S) | > | S |$.

What does this mean for $| \mathbb{N} |$?

#

What is a *real number*?

#

Show there is a bijection between $[0, 1)$ and $pow(\mathbb{N})$.

# #

Class 20: Elections, Review (Tue, 8 Nov 2016)

### Schedule

**Exam 2** will be in class on **Thursday, 10 November**. See Class 18 notes for details.

# Links

Cabinet Battle #1, Cabinet Battle #2, Cabinet Battle #3

Michael J. Caulfield, *Apportioning Representatives in the United
States
Congress*,
Mathematical Association of America, 2010.

*A Mathematical Adventure through the Census, Reapportionment, and
Redistricting*.

2010 Apportiment Results, US Census. (Includes priority values.)

Problem Set 8 Solutions and Comments (Sat, 5 Nov 2016)

The Problem Set 8 solutions are now posted: [PDF]. Please review these to prepare for Exam 2, and let me know if you have any questions or parts you want to go over in class Tuesday.

Problem Set 7 Solutions and Comments (Fri, 4 Nov 2016)

The Problem Set 7 solutions are now posted: [PDF].

Class 19: Uncountable Sets (Thu, 3 Nov 2016)

### Schedule

**Problem Set 8** is due **Friday (4 November) at 6:29pm**.

Friday, 4 November at 11am (Rotunda Dome Room): **Steve Huffman** (BSCS
2005, co-founder and CEO of Reddit), *Computer Science Distinguished
Alumni Speaker*.

**Exam 2** will be in class on **Thursday, 10 November**. See Class 18 notes for details.

## Countable and Uncountable Sets

**Definition.** A set $S$ is *countably infinite* if and only if there
exists a bijection between $S$ and $\mathbb{N}$.

**Definition.** A set $S$ is *uncountable*, if there exists no bijection
between $S$ and $\mathbb{N}$.

The **power set** of $A$ ($\textrm{pow}(A)$)is the set of all subsets of $A$:
$$
B \in \textrm{pow}(A) \iff B \subseteq A.
$$

For all **finite** sets $S$, $|pow(S)| = 2^{|S|}$.

# #

For **all** sets $S$, $|pow(S)| > |S|$.

#

Prove $pow(\mathbb{N})$ is uncountable.

#

$\text{bitstrings} = \forall n \in \mathbb{N} . {0, 1}^n$.

#

## Ordinal and Cardinal Numbers

$\omega$ is the *smallest infinite ordinal*. The first ordinal after
$0, 1, 2, \cdots$.

What is the difference between an *ordinal* and *cardinal* number?

##

What should $2\omega$ mean?

##

Is $\text{InfiniteBitStrings} = {0, 1}^\omega$ countable?

#

Prove the number of real numbers in the interval $[0, 1]$ is uncountable.

# # #

What set is bigger than $\mathbb{R}$?

#

Aleph-naught: $\aleph_0 = |\mathbb{N}|$ is the *smallest infinite
cardinal number*.

How is $\omega$ different from $\aleph_0$?

##

$$2^{\aleph_0} = |pow(\mathbb{N})| = | [0, 1] | = | \mathbb{R} | = | \text{InfiniteBitStrings} | $$

What is necessary to conclude that it is not possible to settle the question of whether $\aleph_1 = 2^{\aleph_0}$ with the ZFC axioms?