Axiomatic Theory of Algorithms: Computability and Decidability in Algorithmic Classes

This article is a brief personal account of the past, present, and future of algorithmic randomness, emphasizing its role in inductive inference and artificial intelligence. It is written for a general audience interested in science and philosophy. Intuitively, randomness is a lack of order or predictability. If randomness is the opposite of determinism, then algorithmic randomness is the opposite of computability. Besides many other things, these concepts have been used to q...

This paper demonstrates the relativity of Computability and Nondeterministic; the nondeterministic is just Turing's undecidable Decision rather than the Nondeterministic Polynomial time. Based on analysis about TM, UM, DTM, NTM, Turing Reducible, beta-reduction, P-reducible, isomorph, tautology, semi-decidable, checking relation, the oracle and NP-completeness, etc., it reinterprets The Church-Turing Thesis that is equivalent of the Polynomial time and actual time; it redef...

Within the program of finding axiomatizations for various parts of computability logic, it was proved earlier that the logic of interactive Turing reduction is exactly the implicative fragment of Heyting's intuitionistic calculus. That sort of reduction permits unlimited reusage of the computational resource represented by the antecedent. An at least equally basic and natural sort of algorithmic reduction, however, is the one that does not allow such reusage. The present arti...

Computational and complexity theory are core components of the computer science curriculum, and in the vast majority of cases are taught using decision problems as the main paradigm. For experienced practitioners, decision problems are the best tool. But for undergraduates encountering the material for the first time, we present evidence that non-decision problems (such as optimization problems and search problems) are preferable. In addition, we describe technical definition...

The recently initiated approach called computability logic is a formal theory of interactive computation. See a comprehensive online source on the subject at http://www.cis.upenn.edu/~giorgi/cl.html . The present paper contains a soundness and completeness proof for the deductive system CL3 which axiomatizes the most basic first-order fragment of computability logic called the finite-depth, elementary-base fragment. Among the potential application areas for this result are th...

We propose a formalization of generic algorithms that includes analog algorithms. This is achieved by reformulating and extending the framework of abstract state machines to include continuous-time models of computation. We prove that every hybrid algorithm satisfying some reasonable postulates may be expressed precisely by a program in a simple and expressive language.

In this paper I discuss what, according to my long experience, every computer scientist should know from logic. We concentrate on issues of modeling, interpretability and levels of abstraction. We discuss what the minimal toolbox of logic tools should look like for a computer scientist who is involved in designing and analyzing reliable systems. We shall conclude that many classical topics dear to logicians are less important than usually presented, and that less-known ideas ...

In this paper we offer a formal definition of Artificial Intelligence and this directly gives us an algorithm for construction of this object. Really, this algorithm is useless due to the combinatory explosion. The main innovation in our definition is that it does not include the knowledge as a part of the intelligence. So according to our definition a newly born baby also is an Intellect. Here we differs with Turing's definition which suggests that an Intellect is a person...

There are growing uncertainties surrounding the classical model of computation established by G\"odel, Church, Kleene, Turing and others in the 1930s onwards. The mismatch between the Turing machine conception, and the experiences of those more practically engaged in computing, has parallels with the wider one between science and those working creatively or intuitively out in the 'real' world. The scientific outlook is more flexible and basic than some understand or want to a...

What is computable with limited resources? How can we verify the correctness of computations? How to measure computational power with precision? Despite the immense scientific and engineering progress in computing, we still have only partial answers to these questions. In order to make these problems more precise, we describe an abstract algebraic definition of classical computation, generalizing traditional models to semigroups. The mathematical abstraction also allows the i...