Honest Computability and Complexity
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, w
- PDF / 367,732 Bytes
- 23 Pages / 439.37 x 666.142 pts Page_size
- 59 Downloads / 191 Views
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’Études Avancées 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: [email protected] N. Dershowitz School of Computer Science, Tel Aviv University, Ramat Aviv, Israel e-mail: [email protected] © Springer International Publishing Switzerland 2016 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
151
152
U. Boker and N. Dershowitz
6.1 Honesty Is Needed Computations have no choice but to manipulate representations of objects rather than the objects themselves. Most often, strings of symbols taken from some finite alphabet are used for the purpose. Numbers, for example, are usually denoted by sequences of decimal symbols, or binary bits, or unary strokes (like the tally numbers of paleolithic times). In logic, one therefore distinguishes between numbers n, which reside in an ideal Platonic world, and numerals n, their symbolic representation as (first-order) terms. Similarly, graphs, which are set-theoretic objects, are typically either represented as lists of edges (pairs of nodes) or as binary adjacency matrices. Given that representation is an inescapable necessity, some natural questions arise immediately: • How much of a difference can the choice of representation make to computability or complexity measurements? Answer: It can make all the difference between computable and incomputable, or between tractable and intractable. • Who gets to choose the representation: Abe who formulates the queries, or Cay who designs the program to answer them? Our answer: Cay may reinterpret Abe’s formulation any way she sees fit, but the reinterpretation is part and parcel of the process of answering. • What is wrong with a representation of graphs that lists nodes in the order of a Hamiltonian path, if there is suc
Data Loading...
