Patrzyłem na kurs Gödelization w teorii teorii obliczeń. Mogłem zrozumieć koncepcje numeracji Gödla, ale nie mogłem zrozumieć ich znaczenia w teorii obliczeń. Czy ktoś mógłby wskazać jakieś dobre materiały lub wskazać jego znaczenie.
Patrzyłem na kurs Gödelization w teorii teorii obliczeń. Mogłem zrozumieć koncepcje numeracji Gödla, ale nie mogłem zrozumieć ich znaczenia w teorii obliczeń. Czy ktoś mógłby wskazać jakieś dobre materiały lub wskazać jego znaczenie.
Odpowiedzi:
Numeracja Gödla w informatyce oznacza mniej więcej „kod źródłowy” i „dane w formacie binarnym”, więc mam nadzieję, że znaczenie tego powinno być oczywiste, jeśli mogę was przekonać, że tak naprawdę jest.
Zanim powstały współczesne komputery, ludzie tworzyli urządzenia komputerowe do jednego celu (opowiadam historię, a nie historię), na przykład ktoś stworzył maszynę do obliczania , a ktoś inny stworzył maszynę do obliczania funkcji Bessela. Pierwotny wgląd Turinga polegał na tym, że musieliśmy zbudować tylko jedną maszynę ( uniwersalną ), która wzięła jako dane wejściowe opis dowolnej maszyny i ją zasymulowała. Ale czym jest „opis maszyny”? Inżynier może pomyśleć o projektach obwodów i instrukcjach montażu. Jest to jednak bardzo skomplikowane i trudne do przedstawienia maszynie. A może coraz bardziej skomplikowane maszyny wymagają coraz bardziej skomplikowanych opisów?
Potrzebujemy sposobu opisywania maszyn, który jest tak prosty, jak to możliwe. Tutaj pomysł Gödela był ważny: pokazał kilka lat przed Turingem, że wszelkiego rodzaju rzeczy w logice (formuły, dowody) mogą być kodowane liczbami, a następnie manipulowane w ramach arytmetyki. Możemy zrobić podobną sztuczkę z maszynami Turinga: zakodować program, aktualny stan i zawartość dotychczas używanej taśmy, za pomocą ciągu symboli na taśmie (na przykład i ), a następnie manipuluj sznurkiem za pomocą maszyny Turinga.
W praktyce nie zapisywać sekwencje „si ” s kiedy programu. Używamy innej warstwy kodowania i piszemy „kod źródłowy”, który jest tłumaczony na kompilatory na i („kod maszynowy”). Ale w rzeczywistości wczesnych informatycy zrobił odpis „si ” s bezpośrednio przez przełączniki obracanie. To była gödelizacja w czystej postaci.
W praktyce możemy reprezentować programów i danych w różnych formatach, znanych jako .java, .py, .mp3, .jpg, itd. W logice i teorii informatyki ludzie wolą trzymać się starych dobrych numerów, ponieważ są one łatwiej manipulować wewnątrz matematyki.
W dzisiejszych czasach każdy wie, że „komputery zrobić wszystko, co w kategoriach «si »s”. Fakt ten stał się tak znany, że trudno docenić jego oryginalność. Wiele lat temu, kiedy istniały żadne nowoczesne komputery, to było oczywiste, że z dala od maszyny, tekst, muzyka, zdjęcia i filmy mogą być wszystkie zakodowane z numerami, lub sekwencje „si ” s.