6837093536
4
Paweł Stacewicz
3. IDEA NIEOBLICZALNOŚCI
Narodziny informatyki — bez której idea umysłu-liczby nie mogłaby przemówić do wyobraźni człowieka współczesnego — zbiegły się w czasie z niezwykle ważnym odkryciem w teorii liczb. Chodzi o nowy podział liczbowego continuum na wielkości obliczalne i nieobliczalne. Dokonał go w roku 1936 Alan Turing, który w głośnej pracy On computable numbers, with an application to Entsheidungsproblem przedstawił koncepcję abstrakcyjnej maszyny, zwanej dziś maszyną Turinga [Turing 1936]. Maszyna ta, z jednej strony stała się podstawą nowego podziału liczb, a z drugiej strony pozwoliła uściślić nie dość do tej pory jasne pojęcie algorytmu, czyli mechanicznej procedury przekształcania symbolicznych danych w symboliczne wyniki. Jak widać zatem, stała się matematycznym spoiwem informatyki i teorii liczb.
Zakładając u czytelnika elementarną znajomość koncepcji Turinga. przypomnijmy drobnym drukiem, że maszynę, o której mowa, rozumie się dwojako. Z jednej strony, chodzi o pewne urządzenie fizyczne — wyposażone w podzieloną na komórki taśmę, głowicę do odczytu/zapisu danych oraz tablicę instrukcji — które to urządzenie odczytując, kasując i zapisując symbole na taśmie, a także zmieniając swoje stany wewnętrzne, realizuje program zawarty w tablicy in-stmkcji.
Z drugiej strony, automat Turinga jest pewną ideą teoretyczną, która pokazuje, na czym polega mechaniczne przetwarzanie danych w wynik, czyli działanie algorytmiczne. Zgodnie z tąże ideą dane trzeba w sposób jednoznaczny zakodować, a potem poddać ściśle określonym przekształceniom, zestawionym jedno po dmgim, bez żadnych luk, w programie maszyny. Przy takim rozumieniu fizyczna konstrukcja maszyny nie ma większego znaczenia; ważne, że działalne automatu jest jakoś skorelowane z jego programem. Turing podał po prostu pewien skrajnie prosty i raczej czysto teoretyczny schemat takiej korelacji (por. [Marciszewski, Stacewicz 2011, s: 120-124]).
Zwieńczeniem turingowskiej koncepcji automatu i algorytmu zarazem jest idea maszyny uniwersalnej — takiej maszyny, która potrafi symulować pracę dowolnego automatu konkretnego, a jako taka potrafi zrealizować każdy program.
Mówiąc bardzo zgrubnie, uniwersalna maszyna Turinga (UMT) działa w sposób następujący. Na jej taśmę wprowadza się zakodowany opis pewnej maszyny konkretnej M (chodzi głównie o definiujący ją program, czyli tablicę zmian stanów) oraz dane wejściowe maszyny M. Następnie maszyna UMT czyta naprzemiennie: raz dane wejściowe automatu M, raz jego tablicę instrukcji (tym właśnie steruje jej uniwersalny program) i zależnie od bieżących instrukcji wypisuje na taśmie odpowiednie sy mbole. Są to takie same symbole, jakie pojawiałyby się na taśmie maszyny M.1
Ze względu na jej nieograniczone możliwości symulacyjne maszynę UMT traktuje się jako ostateczną podstawę pojęcia algorytmiczności. Algorytmem bowiem wolno nazwać każdy schemat, który można zapisać jako program pewnej maszyny
Przyrównując maszynę UMT do współczesnych komputerów cyfrowych, powiedzielibyśmy, że przypomina ona komputer wyposażony w system operacyjny, który to system — dzięki różnym kompilatorom, interpreterom itp. — zapewnia wykonanie każdego dostarczonego mu programu
Wyszukiwarka
Podobne podstrony:
kilku innych kierunków rozwoju informatyki, bez których Dialog Człowieka z Komputerem nie mógłby zai
CCI00179 418 Anglia XVII wiek rozumnej, bez której właściwie władza ta nie jest ro
DSC02115 (4) Pamięci mojej Mamy bez której ta ksiąika by nie powstała Tłumaczka WSTĘP Ein mon, ain w
CCI00179 418 Anglia XVII wiek rozumnej, bez której właściwie władza ta nie jest rozumem. A mianowici
14 Paweł Stacewicz W informatyce natomiast dychotomii tej odpowiada ważka różnica między analogowymi
Paweł Stacewicz Liczby obliczalne Liczby nieobliczalne la. Istnieją maszyny Turinga zdolne
img070 (3) ■m c) Bóg mi odmówił tej anielskiej miary, ( Bez
S5006405 (2) łopolskich, bez której niemożliwe byłoby tak doskonałe opanowanie wszystkich etapów pro
metody pracy z grupą w poradnictwie zawodowym strona? 91 1. Więcej wiedzy i inform
15107 S5006405 (2) łopolskich, bez której niemożliwe byłoby tak doskonałe opanowanie wszystkich etap
Paweł StacewiczCo łączy umysł z teorią liczb? Najbardziej naturalna — i rzecz jasna prawdziwa —
10 Paweł Stacewicz 6. OBLICZALNOŚĆ UMYSŁU A JEGO REALIZACJA KOMPUTEROWA Ponieważ odnoszące do teorii
12 Paweł Stacewicz być może programy komputerowe działające i/lub modyfikowane w sposób losowy lepie
16 Paweł Stacewicz Russel S., Norvig P. (1994), Artificial Inteligence: A Modern Approach, Englewood
2 Paweł Stacewicz mialej dla tejże maszyny. Na przykład aby sprzężony z kamerą komputer cyfrowy mógł
6 Paweł Stacewicz Tak w istocie przedstawia się dostrzeżony przez Alana Turinga związek między sferą
16 Paweł Chlipała klienta, elastyczność, lepsza informacja) można zwiększać efektywność i wartość
więcej podobnych podstron