Implicit and Explicit Examples of the Phenomenon of Deviant Encodings

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. Providing a general definition of notations acceptable in the process of computations causes problems. This is because a notation, or an encoding suitable for a computation, has to be computable. Yet, using the concept of computation, in a definition of a notation, which will be further used in a definition of the concept of computation yields an obvious vicious circle. The circularity of this definition causes trouble in distinguishing on the theoretical level, what is an acceptable notation from what is not an acceptable notation, or as it is usually referred to in the literature, “deviant encodings”.

Deviant encodings appear explicitly in discussions about what is an adequate or correct conceptual analysis of the concept of computation. In this paper, I focus on philosophical examples where the phenomenon appears implicitly, in a “disguised” version. In particular, I present its use in the analysis of the concept of natural number. I also point at additional phenomena related to deviant encodings: conceptual fixed points and apparent “computability” of uncomputable functions. In parallel, I develop the idea that Carnapian explications provide a much more adequate framework for understanding the concept of computation, than the classical philosophical analysis.