Generowanie maszyn Turinga poprzez zastosowanie nowych modeli obliczeniowych

• Autorzy: Dubiel L.

Warianty tytułu

EN

Generating Turing machines by use of other computation models

• Języki publikacji: PL

Abstrakty

PL

Dla każdego problemu obliczalnego istnieje algorytm jego rozwiązania, który może być przedstawiony w postaci konkretnej maszyny Turinga. Ze względu na prostotę tej maszyny programy są bardzo skomplikowane i nieprzejrzyste. Dlatego tworzy się inne modele obliczenia, na których można szybko i łatwo zapisywać algorytmy związane z danym typem problemu, a następnie symuluje się działanie tych modeli na maszynie Turinga. Niniejszy artykuł przedstawia metodologię znajdowania modelu obliczeniowego pasującego do danego typu problemów i przekształcenie go w odpowiednią maszynę Turinga na przykładzie obliczeń na liczbach naturalnych.

EN

For each problem that can be solved there exists algorithm, which can be described with a program of Turing machine. Because this is very simple model programs tend to be very complicated and hard to analyse by human. The best practice to solve given type of problems is to define a new model of computation that allows for quick and easy programming, and then to emulate its operation with Turing machine. This article shows how to define most suitable model for computation on natural numbers and defines Turing machine that emulates its operation.

Słowa kluczowe

PL

maszyna Turinga; automat; teoria obliczeń

EN

Turing machine; automatons; theory of computation

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2003
• Tom: Vol. 5
• Strony: 7--25
• Opis fizyczny: Bibliogr. 10 poz., tab.

Twórcy

autor

Dubiel L.

• Katedra Informatyki, Akademia Górniczo-Hutnicza,

Bibliografia

• [1] Brady J.M.: Informatyka teoretyczna w ujęciu programistycznym. Warszawa, WNT 1983
• [2] Davis M. D., Weyuker E. J.: Computability, complexity and languages - fundamentals of theoretical computer science. Orlando, Academic Press, Inc. 1983
• [3] Engeler E.: Introduction to the Theory of Computation. New Jork, Academic Press, Inc. 1973
• [4] Garding L.: Spotkanie z matematyką. Warszawa, Wydawnictwo Naukowe PWN 1993
• [5] Harel D.: Rzecz o istocie informatyki - algorytmika. Warszawa, WNT 1992
• [6] Kościelski A.: Teoria obliczeń - wykłady z matematycznych podstaw informatyki. Wrocław, Wydawnictwo Uniwersytetu Wrocławskiego 1997
• [7] Kowal S.: 500 zagadek matematycznych. Warszawa, Wiedza Powszechna 1975
• [8] Penrose R.: Nowy umysł cesarza - o komputerach, umyśle i prawach fizyki. Warszawa, Wydawnictwo Naukowe PWN 1996
• [9] Trachtenbrot B. A.: Algorytmy i automatyczne rozwiązywanie zadań. Warszawa, Państwowe Wydawnictwo Naukowe 1961
• [10] Wirth N.: Algorytmy + struktury danych = programy. Warszawa, WNT 1999