Prawdziwe komputery mają tylko skończoną liczbę stanów, więc jakie jest znaczenie maszyn Turinga dla prawdziwych komputerów?


42

Prawdziwe komputery mają ograniczoną pamięć i tylko skończoną liczbę stanów. Są to w zasadzie skończone automaty. Dlaczego informatycy teoretyczni używają maszyn Turinga (i innych równoważnych modeli) do badania komputerów? Jaki jest sens studiowania tych znacznie silniejszych modeli w odniesieniu do prawdziwych komputerów? Dlaczego model automatów skończonych nie wystarczy?


7
@Kaveh Ludzie zwykle machają ręką, że tak, komputery używane w praktyce to FSM, ale FSM są zbyt duże i ciekawe właściwości strukturalne giną w widoku FSM. Nigdy nie spotkałem się z objaśnieniami bez użycia rąk. Dlatego pytanie jest tutaj na temat.
Martin Berger,

15
Prawdziwe pytanie brzmi: po co badać maszyny Turinga, kiedy używamy modelu pamięci RAM podczas analizy algorytmów.
Yuval Filmus,

39
Ponieważ czasami jest lepszym przybliżeniem do niż . 10000000000000000000000000000000 100000000000000000000000000000001000000000000000000000000000000010000000000000000000000000000000
Andrej Bauer,

30
Pamiętaj, że najbardziej znanym nierozwiązanym problemem w dzisiejszej informatyce teoretycznej jest: czy jeden rodzaj fizycznie niemożliwego komputera wyobrażonego może rozwiązać problemy tak szybko, jak jeszcze bardziej fizycznie niemożliwy komputer wyobrażony ? Nie pomyl informatyki teoretycznej z praktyczną inżynierią komputerową; szczegóły świata fizycznego nie są szczególnie istotne.
Eric Lippert,

23
Prawdziwe materiały są zbudowane z atomów i mają charakter dyskretny, więc po co badać całki?
Peter Shor,

Odpowiedzi:


32

Rozważając to pytanie, istnieją dwa podejścia: historyczne dotyczące sposobu odkrywania pojęć i techniczne, które wyjaśniają, dlaczego niektóre pojęcia zostały przyjęte, a inne porzucone, a nawet zapomniane.

Historycznie Maszyna Turinga jest być może najbardziej intuicyjnym modelem kilku opracowanych prób odpowiedzi na Entscheidungsproblem . Jest to ściśle związane z wielkim wysiłkiem podejmowanym w pierwszych dekadach XX wieku w celu całkowitej aksjatyzacji matematyki. Nadzieja polegała na tym, że gdy udowodnisz, że mały zestaw aksjomatów jest poprawny (co wymagałoby znacznego wysiłku), możesz następnie zastosować systematyczną metodę, aby uzyskać dowód na logiczne stwierdzenie, które Cię interesuje. Nawet jeśli ktoś uznałby za skończone automaty w tym kontekście zostaną szybko zwolnieni, ponieważ nie obliczą nawet prostych funkcji.

Technicznie stwierdzenie, że wszystkie komputery są automatami skończonymi, jest fałszywe. Automat skończony ma stałą pamięć, której nie można zmienić w zależności od wielkości wejścia. Nie ma żadnych ograniczeń, ani w matematyce, ani w rzeczywistości, które uniemożliwiały dostarczenie dodatkowej taśmy, dysków twardych, pamięci RAM lub innych form pamięci po użyciu pamięci w maszynie. Wierzę, że często stosowano to we wczesnych dniach obliczeń, kiedy nawet proste obliczenia mogły wypełnić pamięć, podczas gdy teraz w przypadku większości problemów i przy nowoczesnej infrastrukturze, która pozwala na znacznie bardziej wydajne zarządzanie pamięcią, w większości przypadków nie stanowi to problemu .


EDYCJA: Rozważyłem obie kwestie poruszone w komentarzach, ale postanowiłem nie uwzględniać ich zarówno zwięzłości, jak i czasu, który miałem na zanotowanie odpowiedzi. Oto moje rozumowanie, dlaczego uważam, że te punkty nie zmniejszają skuteczności maszyn Turinga w symulacji współczesnych komputerów, szczególnie w porównaniu do automatów skończonych:

  • Pozwól mi najpierw zająć się fizycznym problemem ograniczenia pamięci przez wszechświat. Po pierwsze, tak naprawdę nie wiemy, czy wszechświat jest skończony, czy nie. Co więcej, koncepcja obserwowalnego wszechświata, który z definicji jest skończony, jest również z definicji nieistotna dla użytkownika, który może podróżować do dowolnego punktu obserwowalnego wszechświata w celu wykorzystania pamięci. Powodem jest to, że obserwowalny wszechświat odnosi się do tego, co możemy obserwować z określonego punktu, a mianowicie Ziemi, i byłoby inaczej, gdyby obserwator mógł podróżować w inne miejsce we wszechświecie. Zatem wszelka argumentacja dotycząca obserwowalnego wszechświata przechodzi w kwestię skończoności wszechświata. Załóżmy jednak, że poprzez jakiś przełom zdobywamy wiedzę, że wszechświat jest rzeczywiście skończony. Chociaż miałoby to ogromny wpływ na kwestie naukowe, Wątpię, by miałoby to jakikolwiek wpływ na korzystanie z komputerów. Mówiąc najprościej, może być tak, że w zasadzie komputery są rzeczywiście automatami skończonymi, a nie maszynami Turinga. Ale dla większości obliczeń i najprawdopodobniej każdego obliczenia, którym ludzie są zainteresowani, maszyny Turinga i powiązana teoria oferują nam lepsze zrozumienie. W prostym przykładzie, chociaż wiemy, że fizyka newtonowska jest zasadniczo błędna, wątpię, aby inżynierowie mechanicy używali przede wszystkim fizyki kwantowej do projektowania samochodów lub maszyn fabrycznych; przypadki narożne, w których jest to potrzebne, można rozpatrywać na poziomie indywidualnym. Ale dla większości obliczeń i najprawdopodobniej każdego obliczenia, którym ludzie są zainteresowani, maszyny Turinga i powiązana teoria oferują nam lepsze zrozumienie. W prostym przykładzie, chociaż wiemy, że fizyka newtonowska jest zasadniczo błędna, wątpię, aby inżynierowie mechanicy używali przede wszystkim fizyki kwantowej do projektowania samochodów lub maszyn fabrycznych; przypadki narożne, w których jest to potrzebne, można rozpatrywać na poziomie indywidualnym. Ale dla większości obliczeń i najprawdopodobniej każdego obliczenia, którym ludzie są zainteresowani, maszyny Turinga i powiązana teoria oferują nam lepsze zrozumienie. W prostym przykładzie, chociaż wiemy, że fizyka newtonowska jest zasadniczo błędna, wątpię, aby inżynierowie mechanicy używali przede wszystkim fizyki kwantowej do projektowania samochodów lub maszyn fabrycznych; przypadki narożne, w których jest to potrzebne, można rozpatrywać na poziomie indywidualnym.

  • Wszelkie ograniczenia techniczne, takie jak autobusy i adresowanie, są po prostu ograniczeniami technicznymi istniejącego sprzętu i można je przezwyciężyć fizycznie. Nie jest to prawdą w przypadku obecnych komputerów, ponieważ adresowanie 64-bitowe pozwoliło nam przesunąć górną granicę przestrzeni adresowej na wysokość kilku, jeśli jakiekolwiek aplikacje mogą to osiągnąć. Ponadto wdrożenie „rozszerzalnego” systemu adresowania może potencjalnie mieć wpływ na samą większość obliczeń, które nie będą go potrzebować, a zatem jego nieefektywność. Nic nie stoi na przeszkodzie, aby zorganizować hierarchiczny system adresowania, np. Dla dwóch poziomów pierwszy adres może odnosić się do dowolnego z banków pamięci a następnie każdy bank ma264264różne adresy. Zasadniczo tworzenie sieci to świetny sposób na to, ponieważ każda maszyna dba tylko o swoją pamięć lokalną, ale może obliczać razem.


4
Druga część tej odpowiedzi jest błędna. Komputery automatami skończonymi, nawet jeśli kupiłeś całą pamięć RAM i inny sprzęt. Ilość pamięci RAM, którą można podłączyć do komputera, jest ograniczona przez szerokość jego szyny adresowej i to samo dotyczy dysków i innych urządzeń peryferyjnych.
Emil Jeřábek wspiera Monikę

12
@ EmilJeřábek nieprawda. Interfejsy szeregowe nie mają magistrali adresowej, a ilość danych, do których mogę uzyskać dostęp w Internecie, nie jest ograniczona żadnymi właściwościami mojego komputera.
Stop Harming Monica,

5
@OrangeDog, ale wszechświat nadal ograniczałby ilość danych, które mogą być przechowywane w obserwowalnym wszechświecie
maniak ratchet

9
@ratchetfreak, jak pokazuje maszyna Turinga, potrzebujesz tylko lokalnego dostępu - obecny „koniec” taśmy nie musi znajdować się w obserwowalnym wszechświecie;)
Stop Harming Monica

6
Wspominając historię, warto zacytować recenzję Kościoła dotyczącą artykułu Turinga, że ​​maszyny Turinga mają „tę zaletę, że identyfikacja ze skutecznością ... natychmiast staje się oczywista”. To znaczy, dla ludzi próbujących przekonać samych siebie, że rzeczywiście uchwycili wszystko, co można było obliczyć, definicja Turinga była przekonująca.
Jim Hefferon

44

Aby uzupełnić pozostałe odpowiedzi: Myślę, że Maszyna Turinga jest lepszą abstrakcją tego, co robią komputery, niż automatami skończonymi. Rzeczywiście, główna różnica między tymi dwoma modelami polega na tym, że w przypadku automatów skończonych oczekujemy traktowania danych, które są większe niż przestrzeń stanu, a Maszyna Turinga jest modelem na odwrót (przestrzeń stanu >> dane), tworząc stan przestrzeń nieskończona. Ta nieskończoność może być postrzegana jako abstrakcja „bardzo dużego przed wielkością danych”. Pisząc program komputerowy, próbujesz zaoszczędzić miejsce na wydajności, ale ogólnie zakładasz, że nie będziesz ograniczany przez całkowitą ilość miejsca na komputerze. Jest to jeden z powodów, dla których maszyny Turinga są lepszą abstrakcją komputerów niż automatów skończonych.


14
To jest właściwa odpowiedź IMHO. Powody są czysto pragmatyczne: maszyny Turinga radzą sobie lepiej niż automaty skończone w wyjaśnianiu, co robią komputery w danej skali.
Emil Jeřábek wspiera Monikę

3
Zgadzam się z tym, z wyjątkiem zdania „ogólnie zakładasz, że nie będziesz ograniczony całkowitą ilością miejsca na komputerze”. Wręcz przeciwnie, prawie każdy nietrywialny program jest ograniczony dostępną przestrzenią i programiści robią wszystko, aby sobie z tym poradzić (np. Usuwanie śmieci w celu automatycznego ponownego użycia pamięci), ale (1) nic nie możemy na to poradzić, i (2) ograniczamy się do wystarczająco małych nakładów. Warto zauważyć, że bazy danych dają nam naturalne wyobrażenie o wielkości problemu, a algorytmy mają tendencję do zamykania się w dół w stosunku do tego naturalnego pojęcia wielkości problemu.
Martin Berger,

2
@MartinBerger Re „prawie każdy nietrywialny program jest ograniczony dostępną przestrzenią i programiści robią wszystko, aby sobie z tym poradzić (np. Wyrzucanie elementów bezużytecznych do automatycznego ponownego użycia pamięci)”: Twierdzę, że programy napisane dla systemów z funkcją wyrzucania elementów bezużytecznych rozważają ten system, w tym gc , jako maszyna, na której programują. Garbage collector nie jest częścią programu; jest to część starań, aby dostarczyć dokładnie to, co powiedział Denis: Maszyna do programowania, na której ma praktycznie nieograniczone zasoby pamięci.
Peter - Przywróć Monikę

2
@ PeterA.Schneider Nie zgadzam się. Powodem używania GC zapewnianego przez środowisko uruchomieniowe języka jest jedna z ekonomii tworzenia oprogramowania: mechanizm zarządzania pamięcią specyficzny dla programu jest bardziej wydajny niż GC i większość programistów wolałaby go, gdyby mogli go bezpiecznie i tanio ściągnąć. Ale nie mogą, więc raczej graj bezpiecznie i korzystaj z otaczającego GC, którego koszt jest amortyzowany przez wiele programów. W tym sensie użycie GC będzie bardzo długie, aby poradzić sobie z pamięcią skończoności.
Martin Berger,

2
Maszyny Turinga nie są abstrakcjami tego, co robią komputery, są abstrakcjami tego, co robi komputer, a potem komputery zostały zbudowane. Komputery wykonują większość swoich obliczeń przy użyciu stałej ilości wewnętrznej pamięci roboczej, ale maszyny Turinga nie zostały wymyślone z powodu wnioskowania o obliczeniach z ograniczoną ilością pamięci roboczej.
reinierpost 20.04.16

10

W komentarzach Andrej Bauer podał jeden ważny powód:

Ponieważ czasami jest lepszym przybliżeniem do niż .10000000000000000000000000000000 100000000000000000000000000000001000000000000000000000000000000010000000000000000000000000000000

Pozwolę sobie uzupełnić pozostałe odpowiedzi niektórymi punktami, które prawdopodobnie były zbyt oczywiste, aby je wymienić:

  • Jeśli Twoim celem jest badanie prawdziwych komputerów, to zarówno automaty skończone, jak i maszyny Turinga będą często zbyt prostymi modelami dla odpowiednich pytań. Prawdziwe komputery mają wiele rdzeni przetwarzających z hierarchią pamięci podręcznej (lub innym inteligentnym schematem zarządzania), dostępem do przyzwoitej ilości szybkiej pamięci, dostępem do ogromnej ilości wolnej pamięci zewnętrznej (dysków twardych) i mogą komunikować się z innymi podobnymi komputerami prędkość w przybliżeniu porównywalna z prędkością dostępu do wolnej pamięci zewnętrznej.
  • Jeśli teraz zadajesz sobie pytanie, dlaczego potrzebujesz tych wszystkich szczegółów, okazuje się, że Twoim prawdziwym celem jest badanie instancji problemów i skuteczność ich rozwiązywania. Jeśli mówisz o prawdziwych komputerach, może to również oznaczać, że przeprowadzasz eksperymenty z rzeczywistymi instancjami problemów na różnych typach (prawdziwych) architektur komputerowych.
  • Opisany powyżej model prawdziwych komputerów jest wciąż idealizowany, ponieważ ignoruje różne tryby awarii prawdziwych komputerów. Ponieważ awaria zasilania może występować częściej niż awaria dysku twardego (a dyski twarde i tak mogą mieć kopie zapasowe), niektóre domeny problemowe, takie jak niezawodne działanie bazy danych, mogą wymagać wzięcia tego pod uwagę.
  • Jeśli teraz zaakceptujemy, że klasy problemów i instancje problemowe są tym, co naprawdę nas interesuje, to maszyny Turinga (a także automaty skończone) stają się matematycznymi (i językowymi) narzędziami do przedstawiania (i potwierdzania) interesujących propozycji dotyczących klas problemów i instancji problemów. Przykładowo, konkretny przykład problem może być Riemanna Hipoteza i założenie o tym to, że jest to równoważne z zdaniuΠ10 .

8

Formalizm jest przydatny lub nie, w oparciu o to, co ludzie chcą wykorzystać formalizm do modelowania i rozumienia.

Maszyna Turinga to formalizm przydatny do zrozumienia programów . Programy są warte zrozumienia; większość faktycznych obliczeń jest wykonywana przez programy, a nie przez maszyny specjalnego przeznaczenia. Formalizm maszyny Turinga pozwala nam modelować ważne problemy w świecie rzeczywistym, takie jak złożoność czasu i przestrzeni. O wiele mniej naturalne jest badanie tych pojęć za pomocą automatów skończonych.

Maszyny Turinga nie są zbyt przydatne, gdy próbujemy zbadać złożoność obliczania funkcji skończonych (powiedzmy funkcje, których domena składa się z danych wejściowych o długości co najwyżej 10 milionów). Złożoność obwodów jest znacznie lepsza w opisywaniu złożoności funkcji skończonych ... ale z kolei maszyny Turinga były bardzo przydatne w zrozumieniu złożoności obwodów.

Automaty skończone były również przydatne w zrozumieniu złożoności obwodu; wszystkie te modele mają swoje miejsce w arsenale matematycznym.

Odrzucam argument, że automaty skończone są lepszym modelem rzeczywistości wyłącznie dlatego, że komputery świata rzeczywistego mają tylko skończoną liczbę stanów wewnętrznych. Badanie automatów skończonych zasadniczo zajmuje się danymi wejściowymi pochodzącymi z nieskończonego zestawu ciągów, podczas gdy komputery w świecie rzeczywistym radzą sobie z danymi wejściowymi o określonej stałej maksymalnej długości (chyba że uważasz, że żyjemy w nieskończonym wszechświecie, albo pod względem przestrzeni lub czas).

Model należy oceniać pod kątem jego użyteczności w zrozumieniu tych aspektów rzeczywistości, na których nam zależy. Lub (alternatywnie) pod względem użyteczności w rozumieniu wszechświata matematycznego, który ludzie uważają za wystarczająco przekonujący, nawet jeśli ten wszechświat matematyczny nie ma oczywistych przejawów fizycznych.

Maszyny Turinga, maszyny o stanie skończonym oraz obwody (i inne modele oprócz tego) sprawdziły się.


6

Rzeczywiste komputery nie są FSA. Rzeczywisty komputer to komputer uniwersalny w tym sensie, że możemy opisać komputer, który ma być emulowany, a komputer będzie go emulował. Aby znaleźć wiele przykładów, wyszukaj „maszynę wirtualną”.

Możliwe jest zbudowanie Uniwersalnej Maszyny Turinga - TM, która otrzymuje opis innej TM, a następnie emuluje działanie tej TM na dostarczonym wejściu.

n22n

Jako punkt wyjścia do literatury mogę polecić „ O istnieniu uniwersalnych automatów skończonych lub wypychających ”, który bada nieistnienie automatów uniwersalnych. Możesz także spojrzeć na jego odniesienia (i tak dalej).


3
Jest to przydatne podejście do intuicyjnego uchwycenia różnych poziomów „mocy obliczeniowej”. Wydaje się jednak, że OP uważa, że ​​prawdziwe komputery to FSM, ponieważ liczba stanów jest ograniczona, np. Z powodu skończonej pamięci RAM. Twój argument oznacza, że ​​prawdziwe komputery bardziej przypominają FSM niż Maszyny Turinga, ponieważ nie mogę swobodnie podwoić liczby stanów w symulowanej maszynie; Nie mam nieskończonej taśmy jako miejsca do przechowywania.
amon

1
Maszyny Turinga również nie muszą mieć nieskończonej taśmy. Komputery mogą wykorzystywać w swoich obliczeniach dowolnie dużą pamięć zewnętrzną (a staje się to szczególnie łatwe w przypadku dostawców usług w chmurze, które mamy dzisiaj), więc zasadniczo są to maszyny Turinga, a nie FSM.
reinierpost

1
Jeśli założymy, że komputer ma określoną ilość pamięci, zabraknie mu pamięci podczas symulacji komputera z większą pamięcią, więc przy takim założeniu nie jest tak naprawdę uniwersalny.
Kaveh

3

To, co wyróżnia maszynę Turinga, to to, że będąc bardzo, bardzo prostym, może uruchamiać wszystkie (klasy) algorytmy, o których możemy myśleć. Nie ma znanej maszyny, która byłaby bardziej wydajna (ponieważ mogłaby obsługiwać algorytmy, do których nie jest zdolna maszyna Turinga).

Będąc mechanicznie prostym, łatwo jest wykazać, czy lub w jakim stopniu inne maszyny są równoważne maszynie Turinga. To z kolei sprawia, że ​​stosunkowo łatwo jest wykazać, czy dany komputer (lub język komputera) jest naprawdę uniwersalny (c / f „Turing-complete”).


Pytanie dotyczy relacji modelu maszyny Turinga z prawdziwymi komputerami. Zakładając, że komputer ma ustaloną ilość pamięci, nie jest tak naprawdę uniwersalny.
Kaveh

1

Dlaczego model automatów skończonych nie wystarczy?

Podczas gdy inne odpowiedzi wspominały już o wielu istotnych aspektach, uważam, że główną zaletą maszyn Turinga nad automatami skończonymi jest separacja danych i programów . Pozwala to analizować dość skończony program i wypowiadać się na temat tego, jak program ten obsługiwałby różne dane wejściowe, bez ograniczania rozmiaru danych wejściowych.

Chociaż teoretycznie można opisać zarówno rzeczywisty komputer, jak i maszynę Turinga z taśmą skończoną jako maszynę stanu, nie jest to tak naprawdę wykonalne: liczba stanów jest wykładnicza w ilości pamięci, jaką ma maszyna, i ogólnie skończonej formalizm automatu państwowego wymaga wyraźnego wyszczególnienia przejść między tymi stanami. Tak więc w przypadku ogólnego automatu stanu skończonego o tej wielkości dokonywanie jakichkolwiek dedukcji na podstawie pełnego wyliczenia wszystkich przejść stanu jest całkiem niemożliwe.

Oczywiście na prawdziwym komputerze zmiany stanów nie mogą się zdarzyć arbitralnie. Nie ma polecenia zamiany jednej trzeciej bitów w pamięci w jednym kroku obliczeń. Możesz więc spróbować opracować bardziej zwartą specyfikację przejść stanu. Coś w rodzaju specyfikacji zestawu instrukcji dla twojej architektury. Oczywiście rzeczywiste architektury komputerów są skomplikowane ze względu na wydajność, więc można to jeszcze bardziej uprościć, tworząc bardzo prosty zestaw instrukcji, który wykonuje tylko bardzo małe kroki przy bardzo ograniczonym wejściu i wyjściu. W końcu może się okazać, że twoja architektura przypomina coś w rodzaju interpretera maszyny Turinga: używając kawałków kodu programu i jednego bitu danych wejściowych, wygeneruj trochę danych wyjściowych i poruszaj się w kodzie programu.

Alternatywą byłoby użycie stanów automatu stanu skończonego tylko do przedstawienia danych przetwarzanych przez program, przy jednoczesnym kodowaniu samego programu w stanach przejściowych. To pociągałoby za sobą ten sam problem, jak wyliczyć wszystkie stany, a zwarta reprezentacja może znów być zbliżona do tego, co robi maszyna Turinga.

Jaki jest sens studiowania tych znacznie silniejszych modeli w odniesieniu do prawdziwych komputerów?

Ogólnie rzecz biorąc, powiedziałbym, że maszyna Turinga ze skończoną taśmą byłaby prawdopodobnie lepszym modelem dla rzeczywistych komputerów. Jednak w przypadku wielu pytań naukowych rozróżnienie między skończoną, ale dużą i nieskończoną taśmą jest nieistotne, więc samo twierdzenie, że nieskończona taśma ułatwia. W przypadku innych pytań najważniejsza jest ilość zastosowanej taśmy, ale model z łatwością pozwala mówić o ilości zużytej taśmy bez konieczności określania, co się stanie, jeśli w obliczeniach zabraknie taśmy.


1

Większość problemów wymaga maszyn Turinga o skończonych rozmiarach

Chociaż założenie, że nieograniczona taśma jest użytecznym uproszczeniem, większość problemów / algorytmów w rzeczywistości wymaga skończonej ilości taśmy, a granice wymaganej pamięci (być może w zależności od rozmiaru wejścia) można analizować i często dowodzić.

Często uogólnia to również na inne typy komputerów (dla których związana analiza lub dowód może być znacznie bardziej nieporządny niż na maszynie Turinga) i pozwala oszacować ilość tymczasowej pamięci wymaganej dla konkretnego problemu - czy można to zrobić w określonej ilości przestrzeni? Proporcjonalny do wkładu? Czy wymaga to wykładniczej ilości miejsca w miarę wzrostu nakładów?


1

Jedną ważną cechą maszyn Turinga, których nie dzielą automaty skończone, jest to, że mogą skalować ilość pamięci potrzebnej do rozwiązania problemu wraz z rozmiarem problemu .

nn2

Chodzi o to, że wiele problemów ma naturalne rozwiązania, które zużywają więcej pamięci, im większy jest problem. Naturalne jest zatem opisywanie tych rozwiązań za pomocą reprezentacji, które mogą korzystać z nieskończonej pamięci - nie dlatego, że każde wystąpienie użyje nieskończonych ilości, ale dlatego, że istnieje instancja, która wykorzystuje każdą ilość. Możesz to zrobić za pomocą maszyn Turinga, ale także za pomocą sekwencji automatów skończonych.


Z powiązanej uwagi, jeśli maszyna Turinga z stanami N zostanie uruchomiona z taśmą, która ma skończoną liczbę C niepustych znaków przed i za pozycją początkową, będzie pewna liczba T (N, C) taka, że ​​dowolna maszyna który kiedykolwiek się zakończy, może być emulowany przez jedną maszynę, maszynę, której taśma jest ograniczona do znaków T (N, C).
supercat 21.04.16

-2

Prawdziwe komputery mają ograniczoną pamięć i tylko skończoną liczbę stanów. Są to w zasadzie skończone automaty.

Maszyny Turinga są pochodnymi automatów skończonych. Maszyny Turinga są praktycznie architekturą von Nuemann.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.