Nie jesteś zalogowany | zaloguj się

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Aktualności — Wydarzenia

Teoria Automatów


How computability depends on notation?

Prelegent: Michał Wrocławski

2019-12-18 14:15

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.