Axiomatic Theory of Algorithms: Computability and Decidability in Algorithmic Classes

Theoretical computer science discusses foundational issues about computations. It asks and answers questions such as "What is a computation?", "What is computable?", "What is efficiently computable?","What is information?", "What is random?", "What is an algorithm?", etc. We will present many of the major themes and theorems with the basic language of category theory. Surprisingly, many interesting theorems and concepts of theoretical computer science are easy consequences of...

We need much better understanding of information processing and computation as its primary form. Future progress of new computational devices capable of dealing with problems of big data, internet of things, semantic web, cognitive robotics and neuroinformatics depends on the adequate models of computation. In this article we first present the current state of the art through systematization of existing models and mechanisms, and outline basic structural framework of computat...

We introduce an axiomatization for the notion of computation. Based on the idea of Brouwer choice sequences, we construct a model, denoted by $E$, which satisfies our axioms and $E \models \mathrm{ P \neq NP}$. In other words, regarding "effective computability" in Brouwer intuitionism viewpoint, we show $\mathrm{ P \neq NP}$.

This book explores an alternative to the current dominant paradigm where a discrete computer model is constructed as an attempt to approximate some continuum theory. We focus on a class of discrete computer models that are based on simple deterministic rules and finite state arithmetic. Such models are highly compatible with the operational parameters of the real world computer on which they are executed and hence their validation can be associated with the allowable computat...

Currently it is widely accepted that the language of science is mathematics. This book explores an alternative idea where the future of science is based on the language of algorithms and programs. How such a language can actually be implemented in the sciences is outlined in some detail. We start by constructing a simple formal system where statements are represented as programs and inference is based on computability as opposed to the classical notion of truth value assignme...

This article is a semitutorial-style survey of computability logic. An extended online version of it is maintained at http://www.csc.villanova.edu/~japaridz/CL/ .

The essay consists of three parts. In the first part, it is explained how theory of algorithms and computations evaluates the contemporary situation with computers and global networks. In the second part, it is demonstrated what new perspectives this theory opens through its new direction that is called theory of super-recursive algorithms. These algorithms have much higher computing power than conventional algorithmic schemes. In the third part, we explicate how realization ...

Theoretical computer science (TCS) is a subdiscipline of computer science that studies the mathematical foundations of computational and algorithmic processes and interactions. Work in this field is often recognized by its emphasis on mathematical technique and rigor. At the heart of the field are questions surrounding the nature of computation: What does it mean to compute? What is computable? And how efficiently? Every ten years or so the TCS community attends visioning w...

I am most honoured to have the privilege to present the Foreword to this fascinating and wonderfully varied collection of contributions, concerning the nature of computation and of its deep connection with the operation of those basic laws, known or yet unknown, governing the universe in which we live. Fundamentally deep questions are indeed being grappled with here, and the fact that we find so many different viewpoints is something to be expected, since, in truth, we know l...

The article contains an outline of a possible new direction for Computability Logic (see www.csc.villanova.edu/~japaridz/CL/ ), focused on computability without infinite memory or other impossible-to-possess computational resources. The new approach would see such resources as external rather than internal to computing devices. They could or should be accounted for explicitly in the antecedents of logical formulas expressing computational problems.