The Influence ofDomain Interpretationson Computational Models.ppt

The Influence of Domain Interpretationson Computational Models Udi Boker and Nachum Dershowitz Tel-Aviv, Israel The Need for Interpretations Computational models are usually defined over specific domains E.g. Turing machines over strings and the recursive functions over the natural numbers Yet, we often use them over different domains E.g. Turing machines (or modern computers) for functions over the natural numbers We do it by representing one domain by another E.g. Representing natural numbers as strings via binary or decimal notation Representation and Interpretation ‘Representation’ and ‘Interpretation’ are dual: Function and Model Interpretation Interpretations extend to functions and computational models: Does the Choice of Interpretation Matter? Intuitively it matters for complexity What about computability? Can it be that one interpretation, ? , is better than another, ?, by strictly containing it? Can the original extensionality be enlarged? Interpretations Do Matter! Yes! Interpretations do matter to the extensionality. A model might be enlarged! Example: Two counter machines (2CM) 2CM are known to be as powerful as the recursive functions (REC) [Minsky 60’s] 2CM cannot compute ?n.n2 [R. Schroeppel 72, F. Yao, J. Barzdins] ?The key is the interpretation: Interpreting two counter machines via the representation ? strictly enlarges its extensionality So, What is the Problem? How “serious” is the interpretation issue, in the sense that a model can be enlarged? [BD 2005] How should we compare the power of computational models?[Rogers 66, Sommerhalder Westrehenen 88, …, BD 2005, 2006] Can Turing machines be interpreted to compute more than the recursive functions? [BD 2005] What are the “proper” representations?[Rogers 66, Shapiro 82, Weihrauch 2000, …, BD 2008] What is effectiveness over an arbitrary domain?[Montague 60, Rabin 60, Shapiro 82, Weihrauch 2000, Rescorla 2007, …, BD 2008] Handling the problem Trying to Eliminate the Problem Res