foundations of computer Science
Introduction. I believe that
• for pedagogical purposes, it is worthwhile to define a machine equivalent to Turing machine, that is more intuitively understood by students,
• if three more derivation rules are added to Elementary Arithmetic of Goedel, his Incompleteness Theorems can be proved without using any metalanguage,
• adding two more axioms to Zermelo-Fraenkel set theory, will
allow us to derive Continuum Hypothesis and split the unit interval into infinitesimals.
NuMachine and NuAlgebra: mechanical foundations of computer science. A great achievement of the twentieth century is the concept of a Turing machine which gave us a clear idea what we mean by computation. Turing described a well-defined machine and said that whatever that machine can do is what we should take as the definition of computation. Computer scientists constructed models of Turing machines, with the confident knowledge that it will not be possible to excel their machines for all times to come.
The NuMachine and NuAlgebra I am suggesting here is an alternative to Turing machine, and is more intuitive in its working. The NuMachine follows the Peano postulates closely and for that reason it is easy to recognize the motivations for its movements.
For details, click
Sentient Arithmetic and Goedel’s Theorems: logical foundations of computer science. Investigating the mechanical and logical foundations of computer science, by and large, amounts to the same thing as looking into the foundations of mathematics. Since set theory forms the basis for all mathematics, it is clear that computer science forms a part of set theory.
A theory we understand very well is the Elementary Arithmetic
(EA) of Goedel, even though it is only a fragment of the full-fledged set theory. Goedel has proved that there are formulas in Elementary Arithmetic, which will introduce contradictions, irrespective of whether we assume the formula itself or its negation. His proof is in metalanguage. Sentient Arithmetic (SA) that I propose here adds three more derivation rules to EA and shows that the proof for incompleteness of SA can be given in SA itself without using any metalanguage.
For details click
Two Axioms to extend Zermelo-Fraenkel Theory: foundations of mathematics. As Hilbert says, “The infinite! No other question has ever moved so profoundly, the spirit of man”. The trouble with humans is that they are not comfortable with any thing which does not have an end. Attempting to get out of this dilemma, mathematicians have invented set theory, with a multiplicity of infinities of increasing complexity. Intuitive Set Theory (IST) proposed here attempts to explain a set theory in which we can have a reasonable visualization of our infinite universe. Intuitive Set Theory is defined as the theory we get when Axiom of Combinatorial Sets (ACS) and Axiom of Infinitesimals (AI) are added to Zermelo-Fraenkel theory. ACS makes the Continuum Hypothesis true, and AI splits the unit interval into infinitesimals. Skolem Paradox does not arise in IST, and also there are no sets which are not Lebesgue measurable.
For details click
Conclusion. Our discussion about the foundations of mathematics leads us to some remarkable conclusions about any significant theory which satisfies all the axioms of ZF theory. An important one is that, we can always divide the statements of any significant theory into four mutually exclusive categories: theorems, falsehoods, introversions, and profundities. Without getting into details, we will merely state that the statement of consistency
of ZF theory is an introversion and the continuum hypothesis is a profundity.
Finally, I should mention that some have made an implied criticism that the Axiom of Combinatorial Sets that I have defined is merely another version of the continuum hypothesis. But then, I take consolation from the fact that Bertrand Russell has once said that the whole of mathematical logic is nothing but a study of tautologies. I would only remind the critics that the combinatorial set is a subset of the power set and that my definition of the infinitesimal makes heavy use of the concept of combinatorial sets.
Foundations of Computer Science
Thursday, April 19, 2007
