Proof in Alonzo Church's and Alan Turing's Mathematical Logic

Undecidability of First Order Logic

e-Book PDF

Institution: | University of Calabar |
---|---|

Advisor(s): | Prof. A. F Uduigwomen & Prof. C. O. Ijiomah |

Degree: | Ph.D in Philosophy |

Year: | 2012 |

Volume: | 178 pages |

ISBN-10: | 1612339514 |

ISBN-13: | 9781612339511 |

When in 1900 David Hilbert produced a list of 23 mathematical problems and expressed optimism in the power of the human mind to proffer positive solutions to them, little did he know that it would take much of the century for solutions to be found for some of the problems. The problems numbered 1, 2, and 10 which concern mathematical logic and which gave birth to what is called the entscheidungsproblem or the decision problem were eventually solved though in the negative by Alonzo Church and Alan Turing in their famous Church-Turing thesis. Given any fixed machine M and input n, there are gamma (a set of formulas) and D (a single formula) such that M halts on input n is identical to (gamma) (superset) D. So, if there were an effective means of deciding in first-order-logic in general whether (gamma) (superset) D, we would have a way to solve the halting problem. But we don't! The later Turing and Gumanski's attempts are criticized as inadequate or doubtful. So the decision problem is still unsolved. This Church-Turing proof is a negative solution. Not only has this research shown that a positive solution is possible but it has gone ahead and constructed what is called a General Theory of Effectively Provable Function (GEP) in line with the objectives of this research. Also, the dissertation developed a new axiom of decidability which in fortifying the ZF would make most logical and mathematical problems involving syntax and semantics to be effectively solvable, this makes the research significant. In proffering this positive solution this work finds its justification, but the work did not devise a solution that would end this line of research as Church-Turing thesis had almost done, but one that leads to further interesting inquiries in the area. The model computation theorem we developed for instance, has refocused the issue at stake. It is no longer whether there is a positive solution to the decision problem, for the P-machine has provided it; but whether the P-machine exists in practice as in principle! This becomes a new research interest and insight our positive solution has created and we leave that to other scholars, critics and technologist to sort out. This research adopts the descriptive, analytic, speculative and the prescriptive methods in the course of the investigation.

Jonathan Okeke Chimakonam holds a B.A (Hons) EBSU, M.A and Ph.D (CAL) degrees in philosophy and specializes in mathematical logic, philosophy of science, African philosophy and philosophy of mathematics. He is a consultant on African studies and thought system specifically, on African psycho-logics, psychographics and psychodynamics. He has years of active experience on research on African culture, people, logic and science. He is a member of many research organizations including International Research and Development Institute and the New York Academy of Sciences Dr. Jonathan teaches philosophy and logic, as well as history and philosophy of science at the University of Calabar, Nigeria.