Turinga pełna i obliczeniowa moc

15

W wykładzie profesor wspomniał, że współczesne komputery nie mają tak dużej mocy obliczeniowej jak maszyna Turinga, ponieważ nie mają nieskończonej pamięci, a ponieważ żaden komputer nie ma nieskończonej pamięci, maszyna Turinga jest zatem nieosiągalna i po prostu reprezentuje górną granicę informatyki. Czy z tego powodu istnieje miara lub definicja tego, jakie problemy (lub klasa problemów) leżą poza zasięgiem naszej mocy obliczeniowej?

computability JustAnotherSoul
źródło
tak, nazywa się to „teorią złożoności” =) .. poważnie pomocne jest myślenie o maszynie Turinga jako abstrakcji, która jest realizowana w praktyce, gdy komputer ma dużą pamięć, co jest całkiem realne ze względu na zmienność prawa Mooresa, w którym pamięć ceny spadły, a gęstość / wydajność wzrosły. więc w zależności od kontekstu i nastroju informatyka, mówi się, że komputery albo dokładnie odzwierciedlają maszyny Turinga, albo nie! czasem prawdziwe pytanie zen. „czy prawdziwy komputer to naprawdę maszyna Turinga?” „jaki jest dźwięk klaskania jedną ręką”? i jak plan przeciwko domowi
dniu

Odpowiedzi:

12

Jeśli myślimy o wszechświecie jako skończonym, to wszystko, co potrzebuje więcej pamięci niż ta skończona ilość, przekracza nasze możliwości obliczeniowe.

Jednak nie jest to dobry model do badania obliczalności, model maszyny Turinga działa znacznie lepiej w rzeczywistości i dlatego używamy go do badania obliczeń na prawdziwych komputerach. Maszyna Turinga tak naprawdę nie potrzebuje nieskończonej ilości pamięci, potrzebuje tylko nieograniczonej ilości pamięci. Na przykład możemy z czasem zapewnić dodatkową pamięć dla komputera (ponieważ komputer potrzebuje coraz więcej pamięci), a następnie mamy coś podobnego do maszyny Turinga. Jeśli założymy, że mamy nieograniczoną ilość czasu i pamięci na dokończenie naszych obliczeń, to maszyna Turinga w zasadzie całkiem ładnie wychwytuje tę koncepcję obliczeń.

Sprawdź artykuł w Wikipedii na temat maszyn Turinga, jest sekcja omawiająca znaczenie modelu.

P.P.bP.P.bQP.

Kaveh
źródło
2
Twoja odpowiedź jest bardzo dobra, a teoria złożoności wydaje się być zgodna z tym, co chciałem zbadać. Dziękuję Ci. Tylko uwaga: od mojego profesora miałem wrażenie, że maszyna Turinga nie jest odpowiednikiem komputera i stanowi górną granicę, a nie to, że była nieistotna. Wszelkie implikacje nieistotności były w pełni moje, a błąd w mojej próbie wyjaśnienia, skąd pochodzę.
JustAnotherSoul,
5

Możesz wziąć pod uwagę automat związany z liniami, a odpowiadające mu języki to języki kontekstowe . Zobacz Hierarchię Chomsky'ego, aby dowiedzieć się, które języki są poza zasięgiem takich automatów.

w pewnym sensie niektóre „nieosiągalne” problemy stają się teraz w zasięgu ręki z powodu ograniczonej mocy obliczeniowej!

Na przykład problem zatrzymania maszyn Turinga jest nierozstrzygalny, ale jest rozstrzygalny w przypadku automatów liniowo ograniczonych.

Aryabhata
źródło
Nie wziąłem pod uwagę faktu, że istnieją problemy, które MOŻEMY rozwiązać z powodu ograniczeń. Ciekawy.
JustAnotherSoul
4

Teoria obliczeń jest abstrakcją świata rzeczywistego. Pod wieloma względami abstrakcja nie pasuje idealnie do prawdziwego świata. Po pierwsze, nie możemy tworzyć komputerów z nieograniczoną pamięcią; więc nie możemy nawet tworzyć maszyn do rozpoznawania dowolnych zwykłych języków - ani nawet dowolnych języków skończonych!

Jednak okazuje się, że nie jest to zbyt duży problem; w prawdziwym świecie nie możemy nawet konstruować danych wejściowych dowolnej wielkości, a nawet gdybyśmy mogli, nie byłoby nas wystarczająco długo, aby zobaczyć odpowiedź.

W ścisłym tego słowa znaczeniu nie: klasa fizycznie wykonalnych komputerów jest zdecydowanie mniej wydajna niż klasa maszyn Turinga. Jest również znacznie mniej wydajny niż klasa automatów skończonych.

Patrick87
źródło