NORMAL FUNCTIONS AS A NEW WAY OF DEFINING COMPUTABLE FUNCTIONS

Leszek Dubiel

Abstract


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.

Keywords


The Turing Machine; recursive functions; normal functions

Full Text:

PDF

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




DOI: https://doi.org/10.7494/csci.2004.6.5.7

Refbacks

  • There are currently no refbacks.