On automatic problem solving and automatic programming: the $-calculus approach

What is it about?

This paper is on problem solving. If problem solving was everything what humans were doing in their life, then the paper would be on everything. However, it is obvious that problem solving although dominating our activities and very important does not cover all human activities. Thus the paper for sure is not on the theory of everything (an unachievable goal), but at most on its approximation. Note also that economy, evolutionary computing, mathematics and Turing machines (TMs), although very general and powerful also fail as theory of everything. Problems can be either solvable or unsolvable (called also undecidable) using a specific model/ theory. In computer science, Turing machines form such dominating and most popular model for problem solving. Some problems are Turing machine solvable and some not. In particular, our paper intends to provide a new approach to deal with Turing machine undecidable problems. The typical belief is that proving that a specific problem is TM-undecidable stops any attempt to solve that problem and that is the end of the story. On the other hand, we are convinced that this is only the beginning. First of all, we may decide special instances (or perhaps even almost all instances) of the undeciable problem. For example, if we have the probability distribution of input instances, perhaps randomized techniques may help to estimate which inputs are decidable. Secondly, we can approximate the solutions and we may decide the specific instances either in a finite number of steps or asymptotically in the infinity. There are other approaches possible to deal with undecidability too (e.g., the infinity, evolution and interaction principles), and all above looks like an excellent and exiting new venue for many years of fruitful research to come.

Featured Image

Photo by Markus Spiske on Unsplash

Photo by Markus Spiske on Unsplash

Why is it important?

Turing Machines and recursive algorithms are two fundamental concepts of computer science and problem solving. Turing Machines describe the limits of problem solving using conventional recursive algorithms, and laid the foundation of current computer science in the 1960s. Turing Machines can be considered as an attempt to create the theory of everything for computer science, whereas similar attempts of complete theories for physics (by Newton, Laplace, Einstein, Hawking), mathematics (by Hilbert, Godel, Church, Turing) or philosophy (by Aristotle, Plato, Hegel) have failed. If Turing machines were truly complete, computer science with its Turing machine model would be an exception from other sciences, and computer science together with its Turing machine model would be complete. If so, by reduction techniques, we could prove also completeness of mathematics (decision problem in mathematics - disproved by Godel, Church and Turing), and completeness of physics, philosophy, medicine, economy and so on.

Perspectives