Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Advances in Unconventional ComputingDecreasing Complexity in Inductive Computations

Advances in Unconventional Computing: Decreasing Complexity in Inductive Computations [Kolmogorov or algorithmic complexity has found applications in many areas including medicine, biology, neurophysiology, physics, economics, hardware and software engineering. Conventional Kolmogorov/algorithmic complexity and its modifications are based on application of conventional, i.e., recursive, algorithms, such as Turing machines. Inductive complexity studied in this paper is based on application of unconventional algorithms such as inductive Turing machines, which are super-recursive as they can compute much more than recursive algorithm can. It is possible to apply inductive complexity in all cases where Kolmogorov complexity is used. In particular, inductive complexity has been used in the study of mathematical problem complexity. The main goal of this work is to show how inductive algorithms can reduce complexity of programs and problems. In Sect. 8.2, we build the constructive hierarchy of inductive Turing machines and study the corresponding hierarchy of inductively computable functions. Inductive Turing machines from the constructive hierarchy are very powerful because they can build (compute) the whole arithmetical hierarchy. In Sect. 8.3, it is proved that inductive algorithms from the constructive hierarchy can essentially reduce complexity of programs and problems and the more powerful inductive algorithms are utilized the larger reduction of complexity is achievable.] http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png

Advances in Unconventional ComputingDecreasing Complexity in Inductive Computations

Part of the Emergence, Complexity and Computation Book Series (volume 22)
Editors: Adamatzky, Andrew
Burgin, Mark
Advances in Unconventional Computing — Jul 19, 2016
Download PDF
20 pages

Loading next page...
 
/lp/springer-journals/advances-in-unconventional-computing-decreasing-complexity-in-mPUrMEWpdH
Publisher
Springer International Publishing
Copyright
© Springer International Publishing Switzerland 2017
ISBN
978-3-319-33923-8
Pages
183 –203
DOI
10.1007/978-3-319-33924-5_8
Publisher site
See Chapter on Publisher Site

Abstract

[Kolmogorov or algorithmic complexity has found applications in many areas including medicine, biology, neurophysiology, physics, economics, hardware and software engineering. Conventional Kolmogorov/algorithmic complexity and its modifications are based on application of conventional, i.e., recursive, algorithms, such as Turing machines. Inductive complexity studied in this paper is based on application of unconventional algorithms such as inductive Turing machines, which are super-recursive as they can compute much more than recursive algorithm can. It is possible to apply inductive complexity in all cases where Kolmogorov complexity is used. In particular, inductive complexity has been used in the study of mathematical problem complexity. The main goal of this work is to show how inductive algorithms can reduce complexity of programs and problems. In Sect. 8.2, we build the constructive hierarchy of inductive Turing machines and study the corresponding hierarchy of inductively computable functions. Inductive Turing machines from the constructive hierarchy are very powerful because they can build (compute) the whole arithmetical hierarchy. In Sect. 8.3, it is proved that inductive algorithms from the constructive hierarchy can essentially reduce complexity of programs and problems and the more powerful inductive algorithms are utilized the larger reduction of complexity is achievable.]

Published: Jul 19, 2016

Keywords: Turing Machine; Algorithmic Complexity; Computable Function; Kolmogorov Complexity; Inductive Algorithm

There are no references for this article.