So I've been reading Alan Turing: The Enigma. I'm only about 1/3rd through, but really loving it so far, and thought of writing about it.
The part that interested me the most is the part where the development of the concept of the Universal Machine. Since I am unfamiliar with mathematic philosophy, I re-read the part many times and did a lot of background research. Below is a very rough explanation of the machine.
It all begin with the definition of Mathematics. Roughly speaking it splits into three stages.
Stage I. When mathematics became more than arithmetics, and numbers are treated as symbols and follows a set of rules.
Stage II. Is mathematics complete (ie, all the truth can be derived by following the rules), consistent (no contradiction) and decidable (can determine truth or false with standard steps) under the Formal System?
Stage III. The Universal Machine that aim the solve Stage II problem 3.
Gödel proved the first two problem as false, which is you will always find a statement you know is true but can not prove, and second, which is largely derived from the first, not all mathematical statement is consistent.
Math Stackexchange does a much better explanation than I do:
http://math.stackexchange.com/questions/453503/can-someone-explain-g%C3%B6dels-incompleteness-theorems-in-layman-terms
The more I study the more I understood that the Turing Machine is to solve a logical problem. Even though it is a "Machine", it only serve as a tool to visualize the concept to solve a fundamental problem in logic.
So how does the machine solve the problem of decidability?
First we imagine a machine that does everything a human can do when solving a problem. If we break down problem solving:
1. Read/Write symbols (ie numbers, operators etc..).
2. Execute steps based on certain rules, in the machine's case would be the "Configuration".
3. Conclude.
Therefore theoretically you can solve any problem a human can solve within the Mathematical system with the Machine, as long as you have the configuration. The Universal Machine, is a machine that is encrypted with all the configuration (which can also be a machine itself) of modern mathematics, therefore solving all the modern mathematical problem.
Turing called the results the machine able to churn out: computable numbers.
Turing proved that not all problems can be decided by giving a example of a paradoxical question: the halting problem.
First you imagine a machine that asks the question: does the machine halts?
And set up the configuration as below:
a. Yes: loop
b. No: halt
https://www.youtube.com/watch?v=macM_MtS_w4
If you really think deeply, you would see the configuration itself is a paradox can not be solved. Let's imagine if the input is:
1. Halt -> Yes, loop (Doesn't halt)
2. No -> Halt (but it is looping since the input is no halt)
Therefore creates a contradiction, and Turing determined that not all statements are decidable.
Ok. This is pretty much for part one. There's a lot of resource online for this question, Udacity and Mathematics Stackexchange has been very helpful. Go check it out!
The part that interested me the most is the part where the development of the concept of the Universal Machine. Since I am unfamiliar with mathematic philosophy, I re-read the part many times and did a lot of background research. Below is a very rough explanation of the machine.
It all begin with the definition of Mathematics. Roughly speaking it splits into three stages.
Stage I. When mathematics became more than arithmetics, and numbers are treated as symbols and follows a set of rules.
Stage II. Is mathematics complete (ie, all the truth can be derived by following the rules), consistent (no contradiction) and decidable (can determine truth or false with standard steps) under the Formal System?
Stage III. The Universal Machine that aim the solve Stage II problem 3.
Gödel proved the first two problem as false, which is you will always find a statement you know is true but can not prove, and second, which is largely derived from the first, not all mathematical statement is consistent.
Math Stackexchange does a much better explanation than I do:
http://math.stackexchange.com/questions/453503/can-someone-explain-g%C3%B6dels-incompleteness-theorems-in-layman-terms
The more I study the more I understood that the Turing Machine is to solve a logical problem. Even though it is a "Machine", it only serve as a tool to visualize the concept to solve a fundamental problem in logic.
So how does the machine solve the problem of decidability?
First we imagine a machine that does everything a human can do when solving a problem. If we break down problem solving:
1. Read/Write symbols (ie numbers, operators etc..).
2. Execute steps based on certain rules, in the machine's case would be the "Configuration".
3. Conclude.
Therefore theoretically you can solve any problem a human can solve within the Mathematical system with the Machine, as long as you have the configuration. The Universal Machine, is a machine that is encrypted with all the configuration (which can also be a machine itself) of modern mathematics, therefore solving all the modern mathematical problem.
Turing called the results the machine able to churn out: computable numbers.
Turing proved that not all problems can be decided by giving a example of a paradoxical question: the halting problem.
First you imagine a machine that asks the question: does the machine halts?
And set up the configuration as below:
a. Yes: loop
b. No: halt
https://www.youtube.com/watch?v=macM_MtS_w4
If you really think deeply, you would see the configuration itself is a paradox can not be solved. Let's imagine if the input is:
1. Halt -> Yes, loop (Doesn't halt)
2. No -> Halt (but it is looping since the input is no halt)
Therefore creates a contradiction, and Turing determined that not all statements are decidable.
Ok. This is pretty much for part one. There's a lot of resource online for this question, Udacity and Mathematics Stackexchange has been very helpful. Go check it out!
