NORMAL FUNCTIONS AS A NEW WAY OF DEFINING COMPUTABLE FUNCTIONS
DOI:
https://doi.org/10.7494/csci.2004.6.5.7Keywords:
The Turing Machine, recursive functions, normal functionsAbstract
Report sets new method of defining computable functions. This is formalization of traditional function descriptions, so it allows to define functions in very intuitive way. Discovery of Ackermann function proved that not all functions that can be easily computed can be so easily described with Hilbert’s system of recursive functions. Normal functions lack this disadvantage.Downloads
References
Brady J. M.: Informatyka teoretyczna w ujęciu programistycznym. Warszawa WNT, 1983
Birkhoff G., Bartee T. C.: Współczesna algebra stosowana. Warszawa PWN, 1983
Ciesielski K., Pogoda Z.: Bezmiar matematycznej wyobraźni. Warszawa, Wiedza Powszechna 1995
Davis M. D., Weyuker E. J.: Computability, complexity and languages – fundamentals of theoretical computer science. Orlando, Academic Press 1983
Dziubyński I., Świątkowski T.: Poradnik matematyczny. Warszawa, PWN 1982
Empacher A., Sęp Z., Żakowska Z., Żakowski W.: Mały Słownik Matematyczny. Warszawa Wiedza Powszechna 1975
Engeler E.: Introduction to the Theory of Computation. Nowy Jork, Academic Press 1973
Gårding L.: Spotkanie z matematyką. Warszawa, Wydawnictwo Naukowe PWN 1993
Graham R. L., Knuth D. E., Patashnik O.: Matematyka konkretna. Warszawa, PWN 1996
Harel D.: Rzecz o istocie informatyki – algorytmika. Warszawa, WNT 1992
Kordos M., Skwarczyński M., Zawadowski W.: Leksykon matematyczny. Warszawa, Wiedza Powszechna 1993
Kościelski A.: Teoria obliczeń – wykłady z matematycznych podstaw informatyki. Wrocław, Wydawnictwo Uniwersytetu Wrocławskiego 1997
Kowal S.: 500 zagadek matematycznych. Warszawa, Wiedza Powszechna 1975
Kuratowski K.: Teoria mnogości wraz ze wstępem do opisowej teorii mnogości. Warszawa, PWN 1978
Lewis H., Papadimitriou H.: Elements of the theory of computation. Prentice-Hall International 1998
Penrose R.: Nowy umysł cesarza – o komputerach, umyśle i prawach fizyki. Warszawa, Wydawnictwo Naukowe PWN 1996
Pogoda Z., Ciesielski K.: Diamenty matematyki. Warszawa, Prószyński 1996
Rasiowa H.: Wstęp do matematyki współczesnej. Warszawa, PWN 1975
Sierpiński W.: Wstęp do teorii liczb. Bydgoszcz, Państwowe Zakłady Wydawnictw Szkolnych 1965
Słupecki J., Borkowski L.: Elementy logiki matematycznej i teorii mnogości. Warszawa, PWN 1984
Trachtenbrot B. A.: Algorytmy i automatyczne rozwiązywanie zadań. Warszawa, PWN 1961
Wirth N.: Algorytmy + struktury danych = programy. Warszawa, WNT 1999
