Maszyny i teoria obliczeń

W 1936 r., Aby obliczyć dowolną funkcję obliczeniową, maszyna wymyślona przez „Alan Turing" został nazwany "Turing Machine (TM)". W informatyce TM jest abstrakcyjnym matematycznym modelem obliczeniowym i podstawowym konstrukcją teoretyczną. Maszyny Turing działają poprzez wcześniej zaprogramowaną liczbę instrukcji. Odgrywa ważną rolę i pomaga użytkownikom znaleźć obliczenia, wyznaczając „Funkcje obliczeniowe".

Ten zapis krótko wyjaśni maszyny, ich teorię pracy i obliczenizmu.

Co to jest maszyna Turing?

Maszyna Turinga została wynaleziona przez Alan Turinga. Początkowo został nazwany „A-MACHINE (maszyna automatyczna)". Później ten termin został zmieniony na „Maszyna Turinga" przez "Kościół Alonzo”, Który był doradcą doktoranckim Turinga.

Maszyna Turinga to matematyczny model obliczeń oparty na nieskończonych zestawach instrukcji używanych do wdrożenia dowolnego algorytmu komputerowego. Manipulacja symboli odbywa się zgodnie z tabelą zasad na pasie taśmy.

Jak działa maszyna Turing?

Maszyna Turinga działa z nieskończoną taśmą pamięci podzieloną na poszczególne komórki. Każda komórka może zatrzymać jeden symbol wyciągnięty z nieskończonego zestawu symboli. Te symbole są znane jako alfabet maszyny. Maszyna ma „GŁOWA”To wskazuje na początkowy stan wdrażania algorytmu obliczeniowego.

Dodatkowo można go przesunąć nad jedną z tych komórek, aby można było ustawić. Wybór „państwo”Można wykonać z skończonego zestawu państw. Głowa odczytuje symbol (alfabety maszynowe) z komórki na każdym kroku. Po przeczytaniu symbolu komórki nowy symbol może być dodany do tej samej komórki przez maszynę Turinga. W podstawie nowego symbolu może przesunąć wskaźnik głowy o jeden krok w prawo lub w lewo. Możliwe może być zatrzymanie procesu obliczeniowego.

Czym jest kompatybilność i teza Kościoła?

Kompatybilność to nie tylko A-matka (maszyna Turing), funkcja rekurencyjna, język programowania Pascal lub rachunek, ale kombinacja wszystkich. Alonzo Church, doradca doktorski Turinga, wprowadził tę koncepcję znaną jako „Praca Kościoła". Nazywa się to również „Teza kościelna".

Ponadto nie jest to twierdzenie, ale służy do porównania funkcji obliczeniowej z funkcjami, które można obliczyć za pomocą a-matki. Funkcje, które nie są obliczalne przez A-maszyny, nie mogą być obliczone inną metodą. Kiedy w tym czasie sformułowano koncepcję tezy Kościoła, ludzie nie wiedzieli o zdolności współczesnych komputerów i było to tak znaczące osiągnięcie.

Maszyny i teoria obliczeń

Naturalny zestaw liczb to zestaw obliczeniowy lub komputerowy. Na przykład mamy maszynę Turing z liczbą „M”, Który zatrzymuje się, gdy wyjście wynosi 1, jeśli„M”Jest w zestawie obliczeniowym. Z drugiej strony zatrzymuje się, gdy wyjście wynosi 0, jeśli „M”Nie jest w naturalnym zestawie liczb. Funkcja "R”Od liczby naturalnej do liczby naturalnej to„Obliczalny". Można zauważyć, że nie każdy naturalny zestaw liczb jest obliczalny.

Wyjaśniliśmy koncepcję maszyny Turinga i teorię obliczeniową.

Wniosek

Maszyna Turinga została wymyślona przez „Alan Turing”W 1938 r. W celu obliczenia dowolnej funkcji obliczeniowej. Jest to abstrakcyjny matematyczny model obliczeń i centralny konstrukt teoretyczny w informatyce. Maszyna Turinga to matematyczny model obliczeń oparty na nieskończonych zestawach instrukcji używanych do wdrożenia dowolnego algorytmu komputerowego. Manipulacja symboli odbywa się zgodnie z tabelą zasad na pasie taśmy. Ten zapis pokazał pojęcia maszyn Turinga i teorii obliczeniowej.