Funkcje normalne jako nowy model definiowania funkcji obliczalnych

• Autorzy: Dubiel L.

Warianty tytułu

EN

Normal functions as a new way of defining computable functions

• Języki publikacji: PL

Abstrakty

PL

Artykuł prezentuje nową metodę definiowania funkcji obliczalnych. Metoda jest formalizacją tradycyjnego zapisu funkcji i pozwala na określanie funkcji w sposób intuicyjny. W systemie funkcji rekursywnych Hilberta nie wszystkie odwzorowania, które mają łatwe algorytmy obliczania, mogą być równie łatwo zdefiniowane formalnie, czego przykładem jest funkcja Ackermanna. Funkcje normalne są pozbawione tej wady.

EN

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.

Słowa kluczowe

PL

maszyna Turinga; funkcje rekursywne; funkcje normalne

EN

Turing machine; recursive functions; normal functions

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2004
• Tom: Vol. 6
• Strony: 7--28
• Opis fizyczny: Bibliogr. 23 poz.

Twórcy

autor

Dubiel L.

• Katedra Informatyki, Akademia Górniczo-Hutnicza w Krakowie,

Bibliografia

• [1] Brady J.M.: Informatyka teoretyczna w ujęciu programistycznym. Warszawa WNT, 1983
• [2] Birkhoff G., Bartee T. C.: Współczesna algebra stosowana. Warszawa PWN, 1983
• [3] Ciesielski K., Pogoda Z.: Bezmiar matematycznej wyobraźni. Warszawa, Wiedza Powszechna 1995
• [4] Davis M. D., Weyuker E. J.: Computability, complexity and languages – fundamentals of theoretical computer science. Orlando, Academic Press 1983
• [5] Dziubyński I., Świątkowski T.: Poradnik matematyczny. Warszawa, PWN 1982
• [6] Empacher A., Sęp Z, Żakowska Z., Żakowski W.: Mały Słownik Matematyczny. Warszawa Wiedza Powszechna 1975
• [7] Engeler E.: Introduction to the Theory of Computation. Nowy Jork, Academic Press 1973
• [8] Garding L.: Spotkanie z matematyką. Warszawa, Wydawnictwo Naukowe PWN 1993
• [9] Graham R. L., Knuth D.E., Patashnik O.: Matematyka konkretna. Warszawa, PWN 1996
• [10] Harel D.: Rzecz o istocie informatyki – algorytmika. Warszawa, WNT 1992
• [11] Kordos M., Skwarczyński M., Zawadowski W.: Leksykon matematyczny. Warszawa, Wiedza Powszechna 1993
• [12] Kościelski A.: Teoria obliczeń – wykłady z matematycznych podstaw informatyki. Wrocław, Wydawnictwo Uniwersytetu Wrocławskiego 1997
• [13] Kowal S.: 500 zagadek matematycznych. Warszawa, Wiedza Powszechna 1975
• [14] Kuratowski K.: Teoria mnogości wraz ze wstępem do opisowej teorii mnogości. Warszawa, PWN 1978
• [15] Lewis H., Papadimitriou H.: Elements of the theory of computation. Prentice-Hall International 1998
• [16] Penrose R.: Nowy umysł cesarza – o komputerach, umyśle i prawach fizyki. Warszawa, Wydawnictwo Naukowe PWN 1996
• [17] Pogoda Z., Ciesielski K.: Diamenty matematyki. Warszawa, Prószyński 1996
• [18] Rasiowa H.: Wstęp do matematyki współczesnej. Warszawa, PWN 1975
• [19] Sierpiński W.: Wstęp do teorii liczb. Bydgoszcz, Państwowe Zakłady Wydawnictw Szkolnych 1965
• [20] Słupecki J., Borkowski L.: Elementy logiki matematycznej i teorii mnogości. Warszawa, PWN 1984
• [21] Trachtenbrot B. A.: Algorytmy i automatyczne rozwiązywanie zadań. Warszawa, PWN 1961
• [22] Wirth N.: Algorytmy + struktury danych = programy. Warszawa, WNT 1999
• [23] Zasoby internetu