Kiedy możemy powiedzieć, że dwa programy są różne?

Pytanie 1 Kiedy możemy powiedzieć, że dwa programy (napisane w jakimś języku programowania, takim jak C ++) są różne?

Pierwszą skrajnością jest stwierdzenie, że dwa programy są równoważne, jeśli są identyczne. Inną skrajnością jest stwierdzenie, że dwa programy są równoważne, jeśli obliczają tę samą funkcję (lub wykazują to samo obserwowalne zachowanie w podobnych środowiskach). Ale to nie jest dobre: ​​nie wszystkie programy sprawdzające pierwotność są takie same. Możemy dodać wiersz kodu bez wpływu na wynik i nadal uważalibyśmy go za ten sam program.

Q2 Czy programy i algorytmy są tym samym rodzajem obiektu? Jeśli nie, jaka jest definicja algorytmu i czym różni się od definicji programu? Kiedy możemy powiedzieć, że dwa algorytmy są równoważne?

P1: Istnieje wiele pojęć równoważności programu (równoważność śladu, równoważność kontekstowa, równoważność obserwacyjna, podobieństwo), które mogą, ale nie muszą uwzględniać takich rzeczy, jak czas, zużycie zasobów, niedeterminizm, zakończenie. Dużo pracy włożono w znalezienie użytecznych pojęć równoważności programu. Na przykład: Teorie równoważności programów oparte na operacjach autorstwa Andy'ego Pittsa . Ale to ledwo rysuje powierzchnię. Powinno to być przydatne, nawet jeśli jesteś zainteresowany, gdy dwa programy nie są równoważne. Można nawet argumentować za programami bez zatrzymywania (za pomocą bisimulacji i koindukcji).

Q2: Jedną z możliwych odpowiedzi na część tego pytania jest to, że programy interaktywne nie są algorytmami (zakładając, że jeden algorytm bierze cały swój wkład naraz, ale ta wąska definicja wyklucza algorytmy online). Program może być zbiorem interaktywnych procesów, które również wchodzą w interakcje z ich środowiskiem. To z pewnością nie pasuje do pojęcia algorytmu opartego na maszynie Turinga / teorii rekurencji.

Inną skrajnością jest stwierdzenie, że dwa programy są równoważne, jeśli obliczają tę samą funkcję (lub wykazują to samo obserwowalne zachowanie w podobnych środowiskach). Ale to nie jest dobre: ​​nie wszystkie programy sprawdzające pierwotność są takie same. Możemy dodać wiersz kodu bez wpływu na wynik i nadal uważalibyśmy go za ten sam program.

Nie jest to ekstremalne: równoważność programu musi zostać zdefiniowana w odniesieniu do pojęcia obserwacji.

Najczęstszą definicją w badaniach PL jest równoważność kontekstowa. W kontekście kontekstowym chodzi o to, że obserwujemy programy, wykorzystując je jako elementy większych programów (kontekst). Więc jeśli dwa programy obliczają tę samą wartość końcową dla wszystkich kontekstów, wówczas są one oceniane jako równe. Ponieważ ta definicja określa ilościowo wszystkie możliwe konteksty programu, trudno jest z nią pracować bezpośrednio. Tak więc typowy program badawczy w PL polega na znalezieniu zasad wnioskowania kompozycyjnego, które implikują kontekstową równoważność.

Nie jest to jednak jedyne możliwe pojęcie obserwacji. Na przykład możemy łatwo powiedzieć, że pamięć, czas lub zachowanie programu są obserwowalne. W tym przypadku zachowuje się mniej odpowiedników programów, ponieważ możemy odróżnić więcej programów (np. Scalesort można teraz odróżnić od szybkiego sortowania). Jeśli chcesz (powiedzmy) zaprojektować języki odporne na ataki kanału czasowego lub zaprojektować języki programowania ograniczone do przestrzeni, to jest coś, co musisz zrobić.

Możemy również zdecydować o ocenieniu niektórych stanów pośrednich obliczeń jako możliwych do zaobserwowania. Dzieje się tak zawsze w przypadku jednoczesnych języków, ze względu na możliwość zakłóceń. Ale możesz chcieć wziąć ten widok nawet dla języków sekwencyjnych --- na przykład, jeśli chcesz się upewnić, że żadne obliczenia nie przechowują niezaszyfrowanych danych w pamięci głównej, musisz uznać zapisy w pamięci głównej za obserwowalne.

Zasadniczo nie ma jednego pojęcia równoważności programu; zawsze zależy od wybranej przez ciebie koncepcji obserwacji i zależy to od zastosowania, które masz na myśli.

Q2: Myślę, że zwykłe definicje teoretyczne tak naprawdę nie rozróżniają algorytmów od programów, ale „algorytm”, jak się powszechnie używa, bardziej przypomina klasę programów. Dla mnie algorytm przypomina program, w którym niektóre podprogramy nie są w pełni określone (tzn. Zdefiniowane jest ich pożądane zachowanie, ale nie ich implementacja). Na przykład algorytm eliminacji Gaussa tak naprawdę nie określa, w jaki sposób należy wykonać mnożenie liczb całkowitych.

Przepraszam, jeśli to naiwne. Nie prowadzę badań PL.