Honest Computability and Complexity

DOI10.1007/978-3-319-41842-1_6zbMath1439.03074OpenAlexW2583728043MaRDI QIDQ3305319

Nachum Dershowitz, Udi Boker

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

computational complexitysimulationrepresentationuniversalityeffectivenesscomputabilityencodingcomputational powercomputational modelsChurch-Turing thesis

Mathematics Subject Classification ID

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

Related Items (1)

On efficiency of notations for natural numbers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fields of logic and computation. Essays dedicated to Yuri Gurevich on the occasion of his 70th birthday
• The influence of domain interpretations on computational models
• Acceptable notation
• Pillars of computer science. Essays dedicated to Boris (Boaz) Trakhtenbrot on the occasion of his 85th birthday
• Honest universality
• The Definition of Universal Turing Machine
• Comparing Computational Power
• A Natural Axiomatization of Computability and Proof of Church's Thesis
• Regularity Preserving but Not Reflecting Encodings
• On the parallel computation thesis
• On Universal Functions
• Sequential abstract-state machines capture sequential algorithms

This page was built for publication: Honest Computability and Complexity