Honest computability and complexity

DOI10.1007/978-3-319-41842-1_6MaRDI QIDQ3305319zbMATH OpenOpenAlexFDO

Authors Udi Boker, Nachum Dershowitz

Publication date 6 August 2020

Published in Outstanding Contributions to Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-41842-1_6

zbMATH Keywords

Church-Turing thesiscomputabilitycomputational complexitycomputational modelscomputational powereffectivenessencodingrepresentationsimulationuniversality

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• scientific article; zbMATH DE number 4007703
• Honest universality
• scientific article; zbMATH DE number 3968574
• Composition aspects of programmology. II
• scientific article; zbMATH DE number 3887669

Cites work

• A formalization and proof of the extended Church-Turing thesis (extended abstract)
• A Natural Axiomatization of Computability and Proof of Church's Thesis
• Acceptable notation
• Comparing Computational Power
• Fields of logic and computation. Essays dedicated to Yuri Gurevich on the occasion of his 70th birthday
• Honest universality
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1346527 (Why is no real title available?)
• scientific article; zbMATH DE number 1556014 (Why is no real title available?)
• scientific article; zbMATH DE number 7340320 (Why is no real title available?)
• scientific article; zbMATH DE number 3252196 (Why is no real title available?)
• scientific article; zbMATH DE number 3310089 (Why is no real title available?)
• On the parallel computation thesis
• On Universal Functions
• Pillars of computer science. Essays dedicated to Boris (Boaz) Trakhtenbrot on the occasion of his 85th birthday
• Regularity preserving but not reflecting encodings
• Sequential abstract-state machines capture sequential algorithms
• The Definition of Universal Turing Machine
• The influence of domain interpretations on computational models

Cited in

(2)

• On efficiency of notations for natural numbers
• Honest universality

This page was built for publication: Honest computability and complexity

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