Speaker:
Paula Quinon
 
Title:
A taxonomy of deviant encodings
 
Abstract:
The core of the problem discussed in this paper is the following: the Church-Turing Thesis states that Turing Machines formally explicate the intuitive concept of computability. The description of Turing Machines requires description of the notation used for the *input* and for the *output*. The notation used by Turing in the original account and also notations used in contemporary handbooks of computability all belong to the most known, common, widespread notations, such as standard Arabic notation for natural numbers, binary encoding of natural numbers or stroke notation. The choice is arbitrary and left unjustified. In fact, providing such a justification and providing a general definition of notations, which are acceptable for the process of computations, cause problems.  It is so, because the comprehensive definition states that such a notation or encoding has to be computable. Yet, using the concept of computability in a definition of a notation, which will be further used in a definition of the concept of computability yields an obvious vicious circle.

My objective is, firstly to discuss various versions and aspects of this problem, and then, secondly, to point towards possible solutions, both these proposed explicitly, and these which are relevant for us only implicitly, because they target some disguised version of the problem. Finally, to indicate related topics and formulate some openings raising from this discussion.