Training Log Archive: barbIn the 1 days ending Mar 26, 2012:
| ||||||||||||||||||||||||||||||||||||||||
| « | » |
| » now | ||||
| |||||||
| Mo |
Monday Mar 26, 2012 #
Bicycling 24:00 [1]
OK, we'll start with what it means to compute something.
A computer implements a set of rules that read and write memory.
A formal definition of computation was invented by Turing, whose theoretical machine could read and write symbols on an infinitely long tape according to a finite set of rules. Church’s thesis states that every algorithm can be computed by a Turing machine. An algorithm is a clear, unambiguous description of operations on some input data.
(Note: a Turing machine is DIFFERENT than the Turing test, which is about whether you can tell that the entity answering your questions is a machine or a human...)
Anything you can compute, no matter how complicated, can be computed by a Turing machine. In a way that is surprising, because a Turing machine is very very simple. In fact, Turing's machine is perfectly happy being able to only write 0's and 1's on that long tape. The machine also has state - this is like a little notepad where you get to write down a single number. And the state is finite: the machine's state can only be one of a finite number of possible states. So each rule is something like this: "Read the symbol written at my current location on the tape. If that symbol is 0, and my current state is 23, then write the symbol 1, change state to 13, and move to the left along the tape." Each rule has 5 things: input symbol, input state, output symbol, output state, and movement. So simple. Yet all computations can be mapped onto this simple machine - though sometimes it can take a very very very long time to run a computation on this simple machine!
Any model of computation (system of rules operating on data) that can simulate a Turing machine must also be computationally universal. An example is Conway's Game of Life.
A computer implements a set of rules that read and write memory.
A formal definition of computation was invented by Turing, whose theoretical machine could read and write symbols on an infinitely long tape according to a finite set of rules. Church’s thesis states that every algorithm can be computed by a Turing machine. An algorithm is a clear, unambiguous description of operations on some input data.
(Note: a Turing machine is DIFFERENT than the Turing test, which is about whether you can tell that the entity answering your questions is a machine or a human...)
Anything you can compute, no matter how complicated, can be computed by a Turing machine. In a way that is surprising, because a Turing machine is very very simple. In fact, Turing's machine is perfectly happy being able to only write 0's and 1's on that long tape. The machine also has state - this is like a little notepad where you get to write down a single number. And the state is finite: the machine's state can only be one of a finite number of possible states. So each rule is something like this: "Read the symbol written at my current location on the tape. If that symbol is 0, and my current state is 23, then write the symbol 1, change state to 13, and move to the left along the tape." Each rule has 5 things: input symbol, input state, output symbol, output state, and movement. So simple. Yet all computations can be mapped onto this simple machine - though sometimes it can take a very very very long time to run a computation on this simple machine!
Any model of computation (system of rules operating on data) that can simulate a Turing machine must also be computationally universal. An example is Conway's Game of Life.