The Question of the Boundaries of Computer Science

Abstract

A thesis defining the boundaries of computer science is first formulated in relation to a certain work of Stuart Shapiro. It is argued that these boundaries are determined by the properties of the mind in the real world. It is the Church thesis that determines and specifies these boundaries. Next, some issues concerning the understanding of the Church thesis will be considered such as the division of its formulations and versions. Finally, the relations among the classes of the recursive functions, algorithms, machines and computer programs will be discussed as the main theme of the article. Comments will also be made in the text on the understanding of the term ‘effectively’.

W pracy postawiona zostaje teza dotycząca granic informatyki w nawiązaniu do pewnej pracy Stuarta C. Shapiro. Podaje się argument za tym, że owe granice są określone przez własności umysłu w świecie rzeczywistym. Teza Churcha jest właśnie tym czynnikiem, który wyznacza i specyfikuje owe granice. Potem rozważane są pewne zagadnienia związane z rozumieniem tezy Churcha jak: podział jej sformułowań na warianty i wersje. Następnie, co jest głównym tematem pracy, przedyskutowane są relacje zachodzące pomiędzy klasami funkcji rekurencyjnych, algorytmów, maszyn i programów komputerowych. W tym kontekście podany jest także komentarz na temat rozumienia terminu ‘effectively’.