CS191 14 03 25
Zhu, Justin

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.