Computational Theory of the Mind - the human brain is a computer in general.

Binary

Math is represented with symbols and location:

• Symbols have actual values associate it.
• Columns in a string of symbols have values. The number represented in a given column is column times symbol.

So, the total value in any column = column value * symbol in it.

Turing Machines

Hilbert wanted to axiomatize all of mathematics. Math should be treated as a formal system (alphabet, or set of meaningless symbols, which can be manipulated according to a fixed set of rules, like chess, euclidean geometry). Three things needed for a formal system:

• consistency (no contradictions can be proven within a system)
• completeness (a proof was required that all true mathematical statements which existed within the system can be proven within the system)
• decidability (there should be an effective procedure for deciding the truth or falsity of any mathematical statement)

Alan Turning (imitation game, turing award). He wanted to explore decidability- does there exist an effective procedure for deciding truth in a mathetical system.

• Today this idea is called an "algorithm."
• He wanted to figure out what kind of minimal parts do we need to build a minimal computer. They we would identify the kinds of parts in terms of function.

The turing test: is a machine capable of thinking like a human.

A computer

1. reads instructions
2. read and write symbols on paper
3. erase and replace symbol
4. when computation is done, it stops.

He devised the idea of internal states, which tell the machine what to do.

Any internal state table can be encoded. A programmable computer can perform tasks based on what it is programmed.

• this became a turing machine, the blueprint for modern day computers.
• An effective procedure is anything that can be computed by a turing machine in a finite time.
• You can turn it into a flow chart.

Computer science is the study of what computers can and cant do, complexity of algorithm, and nature of computation.

Church-Turing Thesis: anything that can be computed can, in principle, be done so by a turing machine. If a turing machine can't compute it, its not computable.