Mark Burgin

TCS Journal 2007 Journal Article

Algorithmic complexity as a criterion of unsolvability

• Mark Burgin

There is a dependency between computability of algorithmic complexity and decidability of different algorithmic problems. It is known that computability of the algorithmic complexity C ( x ) is equivalent to decidability of the halting problem for Turing machines. Here we extend this result to the realm of superrecursive algorithms, considering algorithmic complexity for inductive Turing machines. We study two types of algorithmic complexity: recursive (classical) and inductive algorithmic complexities. Relations between these types of algorithmic complexity and decidability of algorithmic problems for Turing machines and inductive Turing machines are considered. In particular, it is demonsrated that computability of algorithmic complexity is equivalent not only to decidability of the halting problem, but also to decidability by inductive Turing machines of the first order of many other problems for Turing machines, such as: if a Turing machine computes a recursive (total) function; if a Turing machine gives no result only for n inputs; if a Turing machine gives results only for n inputs.

TCS Journal 2007 Journal Article

Preface

• Mark Burgin
• Cristian S. Calude

TCS Journal 2004 Journal Article

Algorithmic complexity of recursive and inductive algorithms

• Mark Burgin

The main goal of this paper is to compare recursive algorithms such as Turing machines with such super-recursive algorithms as inductive Turing machines. This comparison is made in a general setting of dual complexity measures such as Kolmogorov or algorithmic complexity. To make adequate comparison, we reconsider the standard axiomatic approach to complexity of algorithms. The new approach allows us to achieve a more adequate representation of static system complexity in the axiomatic context. It is demonstrated that for solving many problems inductive Turing machines have much lower complexity than Turing machines and other recursive algorithms. Thus, inductive Turing machines are not only more powerful, but also more efficient than Turing machines.

TCS Journal 2004 Journal Article

Experience, generations, and limits in machine learning

• Mark Burgin
• Allen Klinger

This paper extends traditional models of machine learning beyond their one-level structure by introducing previously obtained problem knowledge into the algorithm or automaton involved. Some authors studied more advanced than traditional models that utilize some kind of predetermined knowledge, having a two-level structure. However, even in this case, the model has not reflected the source and inherited properties of predetermined knowledge. In society, knowledge is often transmitted from previous generations. The aim of this paper is to construct and study algorithmic models of learning processes that utilize predetermined or prior knowledge. The models use recursive, subrecursive, and super-recursive algorithms. Predetermined knowledge includes: a text description, activity rules (e. g. , for cognition), and specific structured personal or social memory. Algorithmic models represent these three forms as separate structured processing systems: automata with (1) advice; (2) structured program; and (3) structured memory. That yields three basic models for learning systems: polynomially bounded turing machines, Turing machines, and inductive Turing machines of the first order.

TCS Journal 2004 Journal Article

Three aspects of super-recursive algorithms and hypercomputation or finding black swans

• Mark Burgin
• Allen Klinger