Axiomatic Theory of Algorithms: Computability and Decidability in Algorithmic Classes

Computational problems are classified into computable and uncomputable problems.If there exists an effective procedure (algorithm) to compute a problem then the problem is computable otherwise it is uncomputable.Turing machines can execute any algorithm therefore every computable problem is Turing computable.There are some variants of Turing machine that appear computationally more powerful but all these variants have been proven equally powerful.The main objective of this wo...

This article describes a Turing machine which can solve for $\beta^{'}$ which is RE-complete. RE-complete problems are proven to be undecidable by Turing's accepted proof on the Entscheidungsproblem. Thus, constructing a machine which decides over $\beta^{'}$ implies inconsistency in ZFC. We then discover that unrestricted use of the axiom of substitution can lead to hidden assumptions in a certain class of proofs by contradiction. These hidden assumptions create an implied a...

There is a cognitive limit in Human Mind. This cognitive limit has played a decisive role in almost all fields including computer sciences. The cognitive limit replicated in computer sciences is responsible for inherent Computational Complexity. The complexity starts decreasing if certain conditions are met, even sometime it does not appears at all. Very simple Mechanical computing systems are designed and implemented to demonstrate this idea and it is further supported by El...

The article gives a survey of mathematical proofs that rely on computer calculations and formal proofs.

The aim of the workshop series Developments in Computational Models (DCM) is to bring together researchers who are currently developing new computational models or new features for traditional computational models, in order to foster their interaction, to provide a forum for presenting new ideas and work in progress, and to enable newcomers to learn about current activities in this area. The eighth workshop in the series, DCM 2012, was part of the celebrations of the Turing C...

This volume contains the proceedings of the 7th International Workshop on Developments in Computational Models (DCM 2011) which was held on Sunday July 3, 2011, in Zurich, Switzerland, as a satelite workshop of ICALP 2011. Recently several new models of computation have emerged, for instance for bio-computing and quantum-computing, and in addition traditional models of computation have been adapted to accommodate new demands or capabilities of computer systems. The aim of D...

The article retraces major events and milestones in the mutual influences between mathematical logic and computer science since the 1950s.

We describe the Turing Machine, list some of its many influences on the theory of computation and complexity of computations, and illustrate its importance.

In this survey, we explore Andrei Nikolayevich Kolmogorov's seminal work in just one of his many facets: its influence Computer Science especially his viewpoint of what herein we call 'Algorithmic Theory of Informatics.' Can a computer file 'reduce' its 'size' if we add to it new symbols? Do equations of state like second Newton law in Physics exist in Computer Science? Can Leibniz' principle of identification by indistinguishability be formalized? In the computer, there ...

The present paper introduces a novel notion of `(effective) computability', called viability, of strategies in game semantics in an intrinsic (i.e., without recourse to the standard Church-Turing computability), non-inductive and non-axiomatic manner, and shows, as a main technical achievement, that viable strategies are Turing complete. Consequently, we have given a mathematical foundation of computation in the same sense as Turing machines but beyond computation on natural ...