Czy każdy algorytm samodmodyfikujący może być modelowany za pomocą algorytmu niemodyfikującego?

Jeśli mamy dowolny dowolny program komputerowy, który może modyfikować jego instrukcje, czy można symulować ten program za pomocą programu, który nie może modyfikować jego instrukcji?

Edytować:

Jestem nowy w stosie wymiany, więc nie jestem pewien, czy mogę zadawać NOWE pytanie tutaj, ale oto: Ok, więc dowód, że jest to możliwe, jest naprawdę prosty, jak pokazaliście. Zastanawiam się teraz: czy istnieją problemy, w przypadku których bardziej efektywne (i do jakiego stopnia) jest użycie najbardziej wydajnego algorytmu samodmodyfikującego w celu rozwiązania problemu, w porównaniu z najbardziej wydajnym algorytmem niemodyfikującym równoważącym dane wejściowe i wyjściowe?

computability computation-models turing-completeness church-turing-thesis użytkownik56834
źródło

Odpowiedzi:

Tak, to możliwe. Możesz symulować program, używając interpretera dla języka, w którym jest napisany. Teraz program (tłumacz) jest naprawiony, a rzeczą, która kiedyś była programem samodmodyfikującym, są teraz dane tłumacza.

W szczególności możesz doskonale mieć uniwersalną maszynę Turinga, która pozwoliła TM symulować modyfikację własnego opisu. (Mam na myśli opis symulowanej maszyny; nie UTM.)

David Richerby
źródło

Nie potrzebujesz nawet hipotetycznego tłumacza. Procesor wykonujący samodmodyfikujący się algorytm sam jest maszyną, która wykonuje ustalony algorytm (który decyduje o sposobie wykonywania instrukcji)

Alexander - Przywróć Monikę

@AlexanderMomchliov istnieją procesory, które mogą modyfikować części zestawu instrukcji w locie (ale tak, pomysł jest taki sam - częścią programowalną są dane, mikrokontrolerem, który je uruchamia jest interpreter - chociaż wskazuje na mikrokontroler wewnątrz komórki FPGA może być trudne)

John Dvorak

odpowiadając na: „możesz doskonale mieć uniwersalną maszynę Turinga, która pozwala TM symulować modyfikację własnego opisu”. Myślę: czy to nie nasuwa pytania? ponieważ teraz nadal musisz udowodnić, że symulowana TM może faktycznie modelować algorytm samodmodyfikujący się, prawda? Nadal może być tak, że istnieje program samomodyfikujący, który sam NIE jest maszyną Turinga, więc nie możemy użyć kompletności Turinga do wykazania, że można go zasymulować, ponieważ kompletność Turinga dotyczy symulacji baz TM i samomodyfikacji algo nie jest TM.

user56834,

@ Programmer2134 To wcale nie nasuwa pytania. Bez względu na procesor, na którym myślisz, że uruchamiasz swój program do samodzielnej modyfikacji, mogę symulować ten procesor na maszynie Turinga. Aby wyjaśnić to w inny sposób, program początkowy jest skończoną sekwencją instrukcji, z których niektóre się zmieniają. Każda z instrukcji może być symulowana przez UTM, każda z modyfikacji może być symulowana, a każda ze zmodyfikowanych instrukcji może być symulowana. Na żadnym etapie tego procesu nic nie wykracza poza możliwości maszyn Turinga.

David Richerby,

Każdy model obliczeniowy z pełnym Turingiem, który nie ma modyfikującego kodu (lub „kodu”) służy jako dowód na to stwierdzenie. Nie wiem, że każdy ze standardowych modeli (TM, RAM, ...) nie mają kodu modyfikacji, więc nie musimy szukać zbyt daleko.

Aby uzyskać program w dowolnym języku, który masz na myśli, skompiluj z takiego modelu (i upewnij się, że kompilator nie wprowadza modyfikacji kodu).

Jest to, oczywiście, egzystencjalny argumentem: nie jest odpowiednikiem programu. Ale wiemy również, że istnieją rekurencyjne (tj. Obliczalne) kompilatory między dowolnymi dwoma językami kompletnymi Turinga, więc w ten sposób otrzymujesz program o takiej formie (czytaj: w języku), jaki chcesz.

Raphael
źródło

Aby dodać odpowiedź Davida Richerby :

Gdyby prawdą było, że nie można modelować algorytmów samomodyfikujących za pomocą algorytmów niemodyfikujących, wówczas algorytmy te musiałyby zostać wykonane na czymś, co również samo-modyfikuje się. Musiałyby to być żółwie do samego końca.

Jak wspomniałem w moim komentarzu, algorytm samodmodyfikujący może być wykonany na procesorze, który sam przestrzega reguł algorytmu statycznego (zakodowanego w jego konstrukcji), który „mówi” mu, jak wykonywać instrukcje maszynowe.

Alexander - Przywróć Monikę
źródło

Myślę, że może to być ciekawa linia podziału. Wydaje mi się, że można argumentować, że „życie” jest samomodującym algorytmem, którego nie można modelować za pomocą algorytmów niemodyfikujących się, ale z drugiej strony „życia” zazwyczaj nie uważa się za algorytm.

Cort Ammon

@CortAmmon: Jeśli postrzegamy „życie” jako algorytm, to jakie są jego dane wejściowe i wyjściowe? Jak można udowodnić, że każdy równoważny algorytm (co oznacza, że każdy algorytm, który wytwarza takie same dane wyjściowe, gdy otrzyma takie same dane wejściowe) musi sam się modyfikować?

ruakh

@ruakh Gdybym argumentował, że życie jest algorytmem samodmodyfikującym, dane wejściowe byłyby same, a dane wyjściowe byłyby sobą. Udowodnienie, że nie można go sprowadzić do algorytmu niemodyfikującego się, byłoby trudniejsze, ale myślę, że jest to popularna hipoteza. W końcu ile osób chce wierzyć, że można je sprowadzić do algorytmu działającego na komputerze?

Cort Ammon

@CortAmmon: Nie mogę zostać zredukowany do algorytmu działającego na komputerze, ponieważ ten algorytm nie jest już „ja”; Jestem czymś więcej niż tylko swoimi wejściami i wyjściami. Ale jeśli zaczniemy od założenia, że jestem tylko algorytmem, wówczas wybranie opcji „można uruchomić na komputerze” tak naprawdę nic nie zmienia. Re: „Gdybym twierdził, że życie jest algorytmem samodmodyfikującym, dane wejściowe byłyby same, a jego dane wyjściowe byłyby sobą”: W takim przypadku myślę, że skręcilibyście daleko poza CS i niebezpiecznie blisko crackpottery.

ruakh

@CortAmmon Program, który sam się wysyła jako dane wejściowe, jest sprawiedliwy cat. (Nie ma

sensu