#
CS191 14 03 25
Tue, Mar 19, 2019

# Godel 1956

In 1956, Godel wrote a letter to von Neumann. The news came unexpected in that von Neumann experienced illness. Even von Neumann gets sick sometimes.

A mathematical problem that was considered by Godel was that a Turing machine with formula F in first order predicate logic and natural number n allows one to decide if there is a proof of F of length n where n is the length and number of symbols.

We let $\Psi(F, n)$ be the number of of steps the machine requires and $\psi(n) \geq k \cdot n$.

The very construct of a mathematician concerning Yes-or-No questions could be completely replaced by a machine. We just need to choose the natural numbers n so that we can reduce N to $\log N$

This is reminding me more closely the notation of big O notation to measure computational complexity.

Another interesting point is Godel’s point about a brilliant young mathematician named Richard Friedberg. Friedberg seems to want to study medicine rather than mathematics. Seems really similar to my own dilemma right now, since I want to know how to program but to also study medicine.

# Hartmanis, Stearns 1963

Here, we see the very beginning of the complexity analysis. Individuals are taking the computation of sequences by mechanical procedures. There is an interesting classifying scheme that puts a rich structure on computable sequences and how we should compute these sequences.

At the time, computational complexity is defined as a sequence measured by how fast a multi-tape Turing machine can print out the terms of a sequence.

The hierarchy of complexity classes is assured and control unit existed for the machine to perform its next operation as determined by tapes and control state.

$S_T$ can be seen as the set of all computable binary sequences. It is recursively enumerable.

A model can tolerate large deviations without changing complexity classes. The same techniques can be applied to other changes in the model. We also consider multitape Turing machines that have a fixed number of special tape symbols.

A 2-D tape is an unbounded plane subdivided into squares by equidistant sets of vertical and horizontal lines. This definition extends to higher-dimensional tapes.

The Turing machine has appeared to captivate the minds of a generation of computer scientists.