Unconventional algorithms: complementarity of axiomatics and construction

DOI10.3390/E14112066MaRDI QIDQ406192zbMATH OpenOpenAlexFDO

Authors Gordana Dodig-Crnkovic, Mark Burgin

Publication date 8 September 2014

Published in Entropy (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3390/e14112066

zbMATH Keywords

axiomatic models vs. constructive modelscomputation beyond the Turing limitunconventional computingunconventional models of computation

Mathematics Subject Classification ID

Review text

Summary: In this paper, we analyze axiomatic and constructive issues of unconventional computations from a methodological and philosophical point of view. We explain how the new models of algorithms and unconventional computations change the algorithmic universe, making it open and allowing increased flexibility and expressive power that augment creativity. At the same time, the greater power of new types of algorithms also results in the greater complexity of the algorithmic universe, transforming it into the algorithmic multiverse and demanding new tools for its study. That is why we analyze new powerful tools brought forth by local mathematics, local logics, logical varieties and the axiomatic theory of algorithms, automata and computation. We demonstrate how these new tools allow efficient navigation in the algorithmic multiverse. Further work includes study of natural computation by unconventional algorithms and constructive approaches.

Recommendations

• Algorithms and algorithmic problems
• Local and global models of physics and computation
• Advances in unconventional computing. Volume 1. Theory
• scientific article; zbMATH DE number 1670509
• Specification, testing and verification of unconventional computations using generalizedX-machines

Cites work

• A Natural Axiomatization of Computability and Proof of Church's Thesis
• Axiomatic recursion theory and the continuous functionals
• Computability of Recursive Functions
• scientific article; zbMATH DE number 3722109 (Why is no real title available?)
• scientific article; zbMATH DE number 52976 (Why is no real title available?)
• scientific article; zbMATH DE number 3513761 (Why is no real title available?)
• scientific article; zbMATH DE number 1201510 (Why is no real title available?)
• scientific article; zbMATH DE number 1226875 (Why is no real title available?)
• scientific article; zbMATH DE number 3310089 (Why is no real title available?)
• Information Flow
• Journeys in non-classical computation I: A grand challenge for computing research
• Located sets and reverse mathematics
• Physically-relativized Church-Turing hypotheses: physical foundations of computing and complexity theory of computational physics
• Storage Modification Machines
• The Tychonoff product theorem implies the axiom of choice
• Theory of information. Fundamentality, diversity and unification.
• Weak comparability of well orderings and reverse mathematics

Cited in

(1)

• On One Unconventional Framework for Computation

This page was built for publication: Unconventional algorithms: complementarity of axiomatics and construction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q406192)