Nie jesteś zalogowany | Zaloguj się

We study abstract notations for natural numbers, which may differ from

standard notations, so that the functions and relations classically

uncomputable become computable, and vice versa. This question was

raised by a philosopher Stewart Shapiro in course of the debate on

Church-Turing thesis.

We discover that in some notations the standard ordering of natural

numbers is computable, but successor is not; or multiplication is

computable, whereas addition and exponentiation are not. Apart from

surprising counter-examples, we search for a general theory,

explaining how computability of some functions and relations may

induce computability of some others.

How computability depends on notation?