检索结果-内蒙古大学图书馆

algorithmic complexity as a criterion of unsolvability

THEORETICAL COMPUTER SCIENCE 2007年第2-3期383卷 244-259页

作者： Burgin, Mark Univ Calif Los Angeles Dept Math Los Angeles CA 90095 USA

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. (c) 2007 Elsevier B.V. All rights reserved.

关键词： Kolmogorov complexity recursive algorithmic complexity inductive turing machine algorithmic problem inductive algorithmic complexity decidability super-recursive algorithm

来源：评论

学校读者我要写书评

暂无评论

Second-Level algorithms, superrecursivity, and Recovery Problem in Distributed Systems

引用

THEORY OF COMPUTING SYSTEMS 2012年第4期50卷 694-705页

作者： Burgin, Mark Gupta, Bidyut So Illinois Univ Dept Comp Sci Carbondale IL 62901 USA Univ Calif Los Angeles Dept Comp Sci Los Angeles CA 90095 USA

In this paper, we analyze network recovery algorithms, which allow computer networks to properly function in spite of failures. In this analysis, we use methods and tools of the theory of super-recursive algorithms. The concept of algorithm of the second level is introduced and studied. It is demonstrated that although the main components of various check-point/recovery algorithms are recursive algorithms, check-point/recovery algorithms, as a whole, are super-recursive second-level algorithms. Treating network recovery algorithms as second level algorithms is oriented at developing more powerful algorithms by combining existing ones in a common schema.

关键词： Distributed systems Network recovery Recovery algorithm Check-point algorithm super-recursive algorithm Second level algorithm

来源：评论

学校读者我要写书评

暂无评论

Nonlinear phenomena in spaces of algorithms

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 2003年第12期80卷 1449-1476页

作者： Burgin, M Univ Calif Los Angeles Dept Math Los Angeles CA 90095 USA

Nonlinear phenomena, which are so important in nature and society, are considered here in relation to the world of algorithms and computations. To have a mathematical model for this world, formal computability spaces are introduced. It is demonstrated that the traditional approach to algorithms, which is based on such popular models as Turing machines, results in linear subspaces of the computability space. Nonlinear phenomena appear when we go to the more powerful class of such super-recursive algorithms as inductive Turing machines. It is demonstrated how this nonlinearity imports much higher computing power of inductive Turing machines in comparison with conventional Turing machines. This provides a base to consider problems of chaos, emergent computations and infinity from the algorithmic point of view.

关键词： emerging computation recursive algorithm super-recursive algorithm arithmetical hierarchy computability space chaos inductive Turing machine

来源：评论

学校读者我要写书评

暂无评论

algorithmic complexity of recursive and inductive algorithms

引用

THEORETICAL COMPUTER SCIENCE 2004年第1-3期317卷 31-60页

作者： Burgin, M Univ Calif Los Angeles Dept Comp Sci Los Angeles CA 90095 USA

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. (C) 2003 Elsevier B.V. All rights reserved.

关键词： efficiency complexity dual complexity measure Kolmogorov complexity recursive algorithm turing machine super-recursive algorithm inductive turing machine

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：