Honest Computability and Complexity

Udi Boker and Nachum Dershowitz

Goldstein: And what causes you to say that?

Davis: Honesty.

—Martin Davis: An Interview Conducted by Andrew Goldstein (IEEE History Center, July 18, 1991)

For Martin—scientist, scholar, and thinker.

Abstract We raise some issues posed by the use of representations for data structures. A nefarious representation can turn the incomputable into computable, the non-recursively-enumerable into regular, and the intractable into trivial. To overcome such problems, we propose criteria for “honesty” of implementation. In particular, we demand that inputs to functions and queries to decision procedures be specified as constructor terms.

Keywords Computability • Representation • Encoding • Simulation • Computational models • Computational power • Computational complexity • Effectiveness • Church-Turing Thesis • Universality

This author’s research benefited from a fellowship at the Institut d’Etudes Avancees de Paris (France), with the financial support of the French state, managed by the French National Research Agency’s “Investissements d’avenir” program (ANR-11-LABX-0027-01 Labex RFIEA+).

U. Boker (B)

School of Computer Science, Interdisciplinary Center, Herzliya, Israel e-mail: This email address is being protected from spam bots, you need Javascript enabled to view it

N. Dershowitz

School of Computer Science, Tel Aviv University, Ramat Aviv, Israel e-mail: This email address is being protected from spam bots, you need Javascript enabled to view it

© Springer International Publishing Switzerland 2016 151

E.G. Omodeo and A. Policriti (eds.), Martin Davis on Computability,

Computational Logic, and Mathematical Foundations,

Outstanding Contributions to Logic 10, DOI 10.1007/978-3-319-41842-1_6

 
Source
< Prev   CONTENTS   Source   Next >