3813100538

Wstęp

Niniejsza praca magisterska poświęcona jest pojęciu automatu BiichTego, wprowadzonemu przez szwajcarskiego matematyka Juliusa Richarda Biichi’ego w 1962 r.

Teoria automatów Biichi’ego wyrosła z teorii automatów skończonych. Automat skończony to matematyczny model maszyny liczącej, która na zadanym skończonym ciągu symboli ma wykonać konkretne zadanie i zwrócić odpowiedni wynik. Automaty skończone dobrze nadają się do modelowania komputerów o bardzo małej pamięci. Tego typu komputery stanowią serce wielu urządzeń elektromechanicznych takich, jak kalkulatory, zegarki elektroniczne, czy automaty spotykane na co dzień, np. te do sprzedawania napojów.

Są jednak procesy komputerowe, do modelowania których teoria automatów skończonych się nie nadaje. Np. systemy operacyjne dla komputerów, systemy bankowe, systemy ruchu lotniczego zostały tak zaprojektowane, aby działać bezustannie, niezależnie od tego co robi użytkownik. Przekładając na język matematyczny, obliczenie wykonywane przez taki system jest ciągiem nieskończonym, w odróżnieniu od skończonych obliczeń na skończonych ciągach symboli wykonywanych przez automaty skończone.

J. R. Biichi był zainteresowany rozstrzygalnością pewnych teorii w logice. Zauważył przy tym, że istnieje związek między automatami prowadzącymi obliczenia na nieskończonych słowach, a rozstrzygalnością takich teorii. Z tego powodu opracował pierwszą definicję automatu nowego typu i tym samym stał się inicjatorem badań nad skończonymi maszynami wykonującymi nieskończone obliczenia. Wymagało to zdefiniowania pojęcia akceptowania słowa nieskończonego.

W niedługim czasie po odkryciu Biichi’ego także inni badacze podali nowe propozycje modeli nieskończonych. Różnią się one od definicji Biichi’ego i między sobą tzw. czynnikami akceptującymi oraz definicją udanego obliczenia.

Celem tej pracy jest przedstawienie pojęcia i teorii automatów Biichi’ego oraz pewnych alternatywnych podejść do tematu obliczeń nieskończonych, a następnie porównanie ich między sobą.

Praca składa się z czterech rozdziałów. Rozdział pierwszy poświęcono pojęciu

2