15.05.2003

Obliczalność i dowód nierozstrzygalności logiki bez arytmetyzacji

W dowodzie nierozstrzygalności Gödela arytmetyka gra jedynie rolę języka uniwersalnego, czyli takiego, w którym można mówić o nim samym. Prostszą i bardziej intuicyjną wydaje się w tym zastosowaniu teoria konkatenacji zaproponowana przez Tarskiego. Na jej gruncie można też zdefiniować obliczalność jako rozpoznawalność tekstów i przeprowadzić cały dowód.