Discrete Mathematics
This is a preserved file from cs2102 Fall 2016. An updated version may exist at https://uvacs2102.github.io/

Class 22: On Computable Numbers


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}, q0 \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.

#