Nie jesteś zalogowany | Zaloguj się

How computability depends on notation?

Prelegent(ci)
Michał Wrocławski
Afiliacja
Uniwersytet Warszawski
Termin
18 grudnia 2019 14:15
Pokój
p. 5050
Seminarium
Seminarium „Teoria automatów”

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.