Information And Complexity

Mark Burgin, Cristian S Calude

• Publisher: WSPC
• Year: 2016
• ISBN:
  9789813109049
• Topic: Computer Science
• Subtopic: Computer Science General
• Index: Computer Science

-->

The book is a collection of papers of experts in the fields of information and complexity. Information is a basic structure of the world, while complexity is a fundamental property of systems and processes. There are intrinsic relations between information and complexity.

The research in information theory, the theory of complexity and their interrelations is very active. The book will expand knowledge on information, complexity and their relations representing the most recent and advanced studies and achievements in this area.

The goal of the book is to present the topic from different perspectives — mathematical, informational, philosophical, methodological, etc.

--> Editor Mark Burgin, Editor Cristian S Calude 0Information, Complexity, Measure, Computation, Automaton, Information Theory, Science

• The book represents the most recent achievements in information theory, computer science and the theory of complexity
• The book represents advanced ideas and approaches in information theory, computer science and the theory of complexity
• The book is written by the leading experts in information theory, computer science and the theory of complexity

PART I

Classical Information
and Complexity

Chapter 1

The “Paradox” of Computability and a Recursive Relative Version of the Busy Beaver Function

Felipe S. Abrahão^*

Federal University of Rio de Janeiro, Brazil

Abstract

In this article, we will show that uncomputability is a relative property not only of oracle Turing machines, but also of subrecursive classes. We will define the concept of a Turing submachine, and a recursive relative version for the Busy Beaver function which we will call Busy Beaver Plus function. Therefore, we will prove that the computable Busy Beaver Plus function defined on any Turing submachine is not computable by any program running on this submachine. We will thereby demonstrate the existence of a “paradox” of computability a la Skolem: a function is computable when “seen from the outside” the subsystem, but uncomputable when “seen from within” the same subsystem. Finally, we will raise the possibility of defining universal submachines, and a hierarchy of negative Turing degrees.

1.1.Introduction

In first place, we must briefly introduce the ideas behind the definitions, concepts and theorems exposed in the present article. It is true that, following an interdisciplinary course of study, this work focuses on manifold inspirations coming from several different fields of knowledge. However, for present purposes it is essential to mention the two foremost: Skolem’s “paradox” and metabiology.

Skolem’s “paradox” derives from Cantor’s famous theorem on the uncountability of infinite sets, for instance of real numbers or of the set of all subsets of natural numbers, and also from Löwenheim-Skolem’s theorem on the size of models in satisfiable theories. Briefly, the “paradox” is: there is a countably infinite model for a theory (e.g. ZFC, if we accept it as consistent) that proves there are uncountably infinite sets. Therefore, when we look at the set of elements in the theorys model which correspond homomorphically to the elements in the set that the theory demonstrates contain an uncountable amount of elements, may however contain a countable amount of elements. Does this contradiction represent, in fact, a paradox?

That question was answered by Skolem in 1922, being that the property of countability of real numbers depends on the existence of a function within the model that makes this bijective enumeration. This function cannot exist within any ZFC model – if that is the chosen model – because, if it existed, it would render countable the set of all real numbers. However, it may exist when seen “from the outside”, when this function never belongs to the model. In other words, the function that “bijects” the natural onto the real numbers never belongs to any model of any Set Theory¹ – but exists nevertheless. Thus, it is understood that this does not constitute a true paradox. It forms what one may call a pseudoparadox: when seen “from the outside”, an object has a certain property, but when seen seem “from within” it has the opposite property. For this reason, it makes sense to call the Skolem’s “paradox” a pseudoparadox of countability. Therefore, one may ask the question: just as there is a pseudoparadox of countability, could there be a pseudoparadox of computability? We will address this subject in the present paper.

Metabiology is a field of theoretical computer science with a transdisciplinary “heart” that studies general principles of biological relations at a meta-level focusing on the open-ended evolution of systems and is inspired by both the theories of biological evolution and by algorithmic information theory (AIT). While the already developed and well-established fields of population genetics and evolutionary computations are driven towards simulations of evolutionary populations and statistical properties of those populations, metabiology is driven towards achieving theorems. It uses all available tools from theory of computation, algorithmic information and metamathematics to build and study abstract models – applicable or not.

Unlike the first models made by Chaitin, if we want a “nature” without access to oracles – at least, without access to real oracles – it needs to be a system that can be completely simulated on a universal Turing machine, or on a sufficiently powerfu...

Table of contents

• Cover
• Halftitle
• Series Editors
• Title
• Copyright
• Contents
• Preface: The Interplay Between Information and Complexity
• Part I. Classical Information and Complexity
• Part II. Quantum Information and Complexity
• Part III. Applications
• Index