Outputs from Computation Theory Lectures
From the Automata Theory before we moved to Computability Theory and Computational Complexity Theory, we had gone through several Formal Languages, Formal Grammars and Abstract Machines. For the lecture of COS487/MAT407 in Princeton, Formal System was the next topic for students’ discussion; but as long as I’m writing these posts in a line for everyone has the same amateur knowledge basis like me, I’d like to put the First-Order-Logic a bit off, and continue to explaining the Computability Theory in advance.
Speaking of those Abstract Machines, we can see the limitations each one of them easily: Due to the absence of storage, a Finite State Machine (FSM) can’t deal with those problems with ‘counting infinitely’ (eg., determine if a string ‘balanced’ with a and b, or \(L = \{a^n b^n | n ≥ 0 \}\)); a Pushdown Automaton (PDA) has infinite storage, but that storage is still a stack. That means a PDA must consume the input characters ‘in the order’ in which they are received, and cannot access them again, except by placing them on the stack. Therefore, a PDA can’t determine if a string satisfies such rules like ‘a string has the same amount of particular symbols in total’ (eg. “aacbcbdd”); besides, it only works on Context-Free…
Until we got A Turing machine – it has unlimited storage can be visited so efficiently under any order, any loop, any condition and any sub-function. Life is great ;D
Until, we reached the boundary of it. We added more features to those Turing machines but didn’t expand any additional abilities to them, by proving that those features can be replaced by another (bunch of) designed Turing Machines, if those features are applicable. Then where is that limitation of a Turing Machine? Is there an impossible program?
Those ‘General Systems’ such as Turing Machines are dealing with algorithms, not to mention computers. Then, to answer those questions, we have to see the features of an Algorithm. If we know the algorithms’ features and abilities, we might figure out what those limitations are.
In a total rudimentary way to explain, an algorithm is a set of instructions, each instruction takes an/ε input(s) and got an output of it/them. But there are 4 rules applied:
- The number of instructions are finite;
- The instructions can’t be complex;
- The whole process with instructions can be done in finite length of time, if those instructions are followed/used correctly;
- The result out of those sets of instructions must be ‘correct’ if those instructions are followed/used correctly.
Based on the 4 rules above, we can turn numerous algorithms into programming codes. But is it possible to convert each and every algorithm into a set of instructions for general systems’ execution? People (especially people writing codes) may just answer ‘yes’, following their instincts. Yet under the realm of Computational Architecture, the direct, abstractive idea of an algorithm is totally unequal to its logical, concrete implementation.
So again, can we design an algorithm with such unbelievable complexity and unmeasurable scale that no machine can grasp its stem?
Since 1930s, computer scientists have been working on creating an algorithm which could not be ‘solved’ by an abstract machine – every attempt of creating an model of computation returns a system, and those systems were all proved to have the equivalent capacity of a Turing machine, whereas there’s still no mathematical / logical proof for that general question. In fact, from the place I put up the 4 rules for algorithm, we are not be able to talk about the whole question on the level of logic or mathematics any more. But at least, along the way of exploration, we are confident to accept the hypothesis below:
“Every algorithm has the features as I mentioned in this post, can be executed by an abstract machine, or specifically, a Turing machine.” or let’s say, “a function on the natural numbers can be calculated by an effective method if and only if it is computable by a Turing machine.”
And here we reached the first stop of the Computability Theory: Church-Turing Thesis,
“We shall use the expression ‘computable function’ to mean a function calculable by a machine, and let ‘effectively calculable’ refer to the intuitive idea without particular identification with any one of these definitions.”
Turing, Alan (1938). Systems of Logic based on Ordinals (PhD thesis). Princeton University. doi: 10.1112/plms/s2-45.1.161.
or in Gandy’s(1980:123) words, every effectively calculable function is a computable function.
Despite of the form of Church-Turing Thesis is a ‘thesis’, a literature statement than a logical, formal expression, the Church-Turing Thesis came out from solid formalisms: the λ-calculus, besides recursion, and the Turing machine. Those are the topics up next, which requires we write something to show the power of those 3.
We’ll begin from the λ-calculus.