There is a dependency between computability of algorithmiccomplexity and decidability of different algorithmic problems. It is known that computability of the algorithmiccomplexity C(x) is equivalent to decidability...
详细信息
There is a dependency between computability of algorithmiccomplexity and decidability of different algorithmic problems. It is known that computability of the algorithmiccomplexity 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 algorithmiccomplexity for inductive Turing machines. We study two types of algorithmiccomplexity: recursive (classical) and inductivealgorithmic complexities. Relations between these types of algorithmiccomplexity and decidability of algorithmic problems for Turing machines and inductive Turing machines are considered. In particular, it is demonsrated that computability of algorithmiccomplexity 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.
暂无评论