Why do I have to build data structures and what are they for? Data structures are specific examples of mechanical, automated problem solving.
Computers in 1880 were men and more often women who would work out formulas with pen and paper for an hourly rate. Calculations were needed for phsyics and chemistry research, calculus, other mathematics, and finances. This lead to an academic discipline that involved philosophy about the nature of mathematics and what kinds of knowledge could be formally proven.
Alonzo Church, Alan Turning, Stephen Kleene, Kurt Godel, David Hilbert, and others worked to formalize these ideas into mathematical proofs leading, eventually, to the Turing Machine and the proofs that accompanied it.
It was stated above that 'a function is effectively calculable if its values can be found by some purely mechanical process'. We may take this statement literally, understanding by a purely mechanical process one which could be carried out by a machine. It is possible to give a mathematical description, in a certain normal form, of the structures of these machines. The development of these ideas leads to the author's definition of a computable function, and to an identification of computability with effective calculability. It is not difficult, though somewhat laborious, to prove that these three definitions [the 3rd is the λ-calculus] are equivalent.
— Turing (1939) in The Undecidable, p. 160
Something is numerically computable by a human iff it is computable by a Turing machine, and that all forms of iterative deterministic computation are equivalent.
Suggest regular grammars and context free grammars. Become familiar with the notation of state machines and be able to describe the simple function of any machine with a state machine.
Regular Expression These are of special importance in Computer Science!
Occupies a space of computational complexity between context free grammars and Turing Machines.
Chomsky invented CFGs in the context of natural language. They haven't proven to be extremely useful in that context, but have become the standard for all programming languages.
Backus Naur Form This is of special importance in Computer Science!
programming languages These are obviously of special importance. :)
Halting Problem This is of special importance in Computer Science!
One of the first decision problems and the foundation of Computer Science. Turing Machine was invented in order to provide a solution for this problem - that it is undecidable.
The question is: Can a program be written f that will for every other program g say whether or not g will finish? Turing proves using complicated mathematics, and by inventing a Turing Machine in order to support his proof, that this machine f cannot be invented.
The takeaway from this proof and observation is that it is not possible to build a computer program that can solve any problem - some problems are undeciable, that is, unsolveable.
Turing Machines These are of special importance in Computer Science!
Visual example of a Turing Machine as formula
Gödel's Incompleteness Theorem
Draw a state machine for a stop light Mathematically describe a state machine for a stop light using the rules of Regular Languages Create a new subset of the Javascript language using Backus-Naur Form Write via state machine notation a Turing machine that can identify the string: 'aaabbb' Write a Turing Machine in Javascript