Pisanie uniwersalnej funkcji rekurencyjnej [zamknięte]

9

Czy istnieje krótka wyraźna konstrukcja uniwersalnej funkcji rekurencyjnej ? Wszystkie definicje, które widziałem, obejmują w pewien sposób numerację maszyn Turinga, co jest możliwe, ale wydaje się trudne i niemożliwe do zarządzania w języku programowania wyższego poziomu (takim jak Python, Haskell itp.)

lo.logic computability pl.programming-languages sdcvvc
źródło
Pytanie zostało pierwotnie zadane w SO , tutaj wydaje się bardziej odpowiednie.
sdcvvc
1
Rozumiem, że to, co robi uniwersalna funkcja rekurencyjna, polega właśnie na podaniu pewnej numeracji funkcji rekurencyjnych (lub równoważnie maszyn Turinga), aby wynik można było obliczyć na podstawie indeksu funkcji rekurencyjnej i danych wejściowych. Dlatego „uniwersalna funkcja rekurencyjna bez numerowania maszyn Turinga” nie wydaje mi się wiarygodna.
Tsuyoshi Ito,
3
Nie poziom badań. Każdy tłumacz dla języka kompletnego Turinga jest uniwersalną funkcją rekurencyjną.
Warren Schudy,

Odpowiedzi:

13

Pewnie. Napisz procedury, które obliczają każdą z prymitywnych funkcji rekurencyjnych Godela , i napisz procedurę dla nieograniczonego operatora wyszukiwania. Zestaw funkcji, które można obliczyć w ten sposób, jest równoważny zestawowi funkcji, które mogą obliczać maszyny Turinga. Więcej informacji tutaj .

Minusem jest to, że wszelkie dane wejściowe do Twojego programu uniwersalnego musiałyby być sformułowane w kategoriach tych prostych operacji. Oczywiście po to są kompilatory.

Aaron Sterling
źródło
10

Każdy tłumacz dla dowolnego języka, który jest kompletnym językiem Turinga, jest uniwersalną funkcją rekurencyjną. Istnieją interpretatory języków wysokiego poziomu, takich jak C ++ lub Python.

Numeracja Godela istnieje, ale domyślnie. Na przykład kod C ++ obliczający funkcję rekurencyjnąsol jest indeksem dla sol.

Kaveh
źródło
Interpretator maszyn Turinga (lub maszyn rejestrujących lub funkcji rekurencyjnych) jest również uniwersalną funkcją rekurencyjną i ich implementacja nie jest trudna. Zaimplementowałem je w C ++ kilka lat temu i jestem prawie pewien, że w Pythonie byłoby to jeszcze prostsze. Korzystaj z Google, w Internecie jest wiele bezpłatnych symulatorów, a niektóre z nich są nawet typu open source.
Kaveh
8

Funkcję uniwersalną umożna dość łatwo napisać w języku podobnym do Haskella (bez skutków ubocznych, funkcje wyższego rzędu), a mianowicie:

u f x = f x

Funkcja ujest uniwersalna, ponieważ akceptuje (opis) program fi taśmy wejściowej xi informuje o wyniku prowadzenia fna x.

Chociaż odpowiedź ta nie jest do końca poważna, pokazuje, że kompilator lub interpreter języka podobnego do języka Haskell zawiera już wszystkie elementy potrzebne do utworzenia funkcji uniwersalnej. Morał tej historii jest taki, że lepiej poświęcić czas na studiowanie działania kompilatorów i tłumaczy, niż martwić się o wdrożenie uniwersalnej funkcji w zakresie maszyn Turinga.

Andrej Bauer
źródło
Jednak ubierze funkcję - nazwałbym to funkcją wyższego rzędu. Chciałbym uwziąć liczbę całkowitą lub zwykły typ danych algebraicznych. Nie wymuszam żadnego konkretnego modelu obliczeń, o ile argument do ujest namacalny - na przykład może być szeregowany z / do ciągu.
sdcvvc,
Na rzeczywistym komputerze (po skompilowaniu kodu) uprzyjmuje zamknięcie, które jest skończoną sekwencją bajtów. Nawet w zwykłym twierdzeniu utm przyjmowana liczba całkowita ureprezentuje funkcję.
Andrej Bauer,
5

Zobacz także ten artykuł Johna Trompa, wykorzystujący logikę kombinacyjną. Wcześniejszy opis, najwyraźniej już niedostępny, był jeszcze lepszy.

Yuval Filmus
źródło