Dlaczego sumy funkcji nie są policzalne?

Dowiedzieliśmy się o koncepcji wyliczenia funkcji. W praktyce odpowiadają one językom programowania.

W pewnej uwadze profesor wspomniał, że klasa wszystkich całkowitych funkcji (tj. Funkcji, które zawsze kończą się dla każdego wejścia) nie jest wyliczalna. Oznaczałoby to, że nie możemy opracować języka programowania, który pozwala nam pisać wszystkie funkcje całkowite, ale żadnych innych --- co byłoby miło mieć!

Więc jak to jest, że (najwyraźniej) musimy zaakceptować potencjał braku rozwiązania, jeśli chcemy przyzwoitej mocy obliczeniowej?

computability semi-decidability enumeration

— Raphael
źródło

Odpowiedzi:

Z powodu diagonalizacji. Jeśli był obliczalnym wyliczeniem wszystkich wszystkich obliczalnych funkcji od do , tak że każdy był całkowity, to również byłby całkowitą funkcją obliczalną, ale nie byłoby jej w wyliczeniu. Byłoby to sprzeczne z założeniami dotyczącymi sekwencji. Zatem żadne obliczalne wyliczenie funkcji nie może składać się z całkowitej liczby funkcji obliczalnych. $(f_e: e \in \mathbb{N})$ $\mathbb{N}$ $\mathbb{N}$ $f_e$ $g(i) = f_i(i)+ 1$

Załóżmy, że myślimy o uniwersalnej funkcji obliczeniowej , gdzie „uniwersalna” oznacza jest obliczalną funkcją binarną i że dla każdej całkowitej obliczalnej funkcji jednoargumentowej istnieje pewna liczba taka że dla wszystkich . Zatem musi być też taki , że nie jest funkcją całkowitą z powodu poprzedniego akapitu. W przeciwnym razie dałoby obliczalne wyliczenie całkowitych obliczalnych funkcji jednoargumentowych, które obejmuje wszystkie całkowite obliczalne funkcje jednoargumentowe. $h(e,i)$ $h$ $f(n)$ $e$ $f(i) = h(e,i)$ $i$ $e$ $g(n) = h(e,n)$ $h$

Zatem wymóg, że każda funkcja jest systemem funkcji całkowitych, jest niezgodny z istnieniem funkcji uniwersalnej w tym systemie. W przypadku niektórych słabych systemów, takich jak pierwotne funkcje rekurencyjne, każda funkcja jest całkowita, ale nie ma funkcji uniwersalnych. Silniejsze systemy, które mają funkcje uniwersalne, takie jak obliczalność Turinga, po prostu muszą mieć funkcje częściowe, aby umożliwić istnienie funkcji uniwersalnej.

— Carl Mummert
źródło

Chciałem tylko dodać, że ktoś znalazł lukę w diagonalizacji. Jeśli używasz reprezentacji maszynowej dla programu, możesz użyć systemu typów, aby uniemożliwić diagonalizację i stworzyć całkowitą interpreter. Szczegółowe informacje można znaleźć w artykule Przełamywanie bariery normalizacyjnej: interpreter języka F-omega .

— hatch22

Oczywiście System F nie jest kompletnym systemem Turinga. Papier, który połączyłeś, jest interesujący; Wygląda na to, że udaje im się w ciekawy sposób wykorzystać nieukończenie Turinga.

— Carl Mummert,

Nie rozumiem, dlaczego „to również byłoby całkowitą funkcją obliczalną”. Jeśli jest całkowitą funkcją obliczalną, to , a następnie ocena wymaga oceny : sprzeczność. Wydaje się więc, że jeśli istnieje wyliczenie całkowitych funkcji obliczeniowych, nie możemy nawet zbudować , więc nie możemy osiągnąć sprzeczności w celu obalenia początkowej hipotezy (Możemy dojść do sprzeczności, ale to po prostu obala całkowitą obliczalność).

g (i) = f_{i} (i) + 1

$g(i) = f_i(i) + 1$

g

$g$

\exists k, f_{k} = g

$\exists k, f_k = g$

g (k)

$g(k)$

g (k) = f_{k} (k) + 1 = g (k) + 1

$g(k) = f_k(k) + 1 = g(k) + 1$

g

$g$

g

$g$

— agemO,

I nawet użycie przesuniętej przekątnej, aby uniknąć tego problemu, wydaje się prowadzić do sprzeczności.

— agemO,

Żeby było jasne, musimy rozróżnić funkcje matematyczne (nazywam je funkcjami i często jest ich niepoliczalnie wiele, więc w ogóle nie są one policzalne) i funkcje, które można napisać: wywołam je programami lub funkcjami obliczalnymi .

Podzbiór o zbiór przeliczalny nazywany jest obliczalny , czy istnieje program, który, biorąc pod uwagę element z odpowie „tak”, jeśli i „nie”, jeśli . (I zawsze musi coś odpowiedzieć). Zestaw jest wywoływany przez wyliczanie rekurencyjne, jeśli program jest upoważniony do nie odpowiadania zamiast powiedzieć „nie”. (równoważne jest wymaganie, aby program wydrukował wszystkie elementy w dowolnej kolejności) $S$ $E$ $x$ $E$ $x∈S$ $x\not∈S$ $S$

Zestaw wszystkich programów, które są sumą w zestawie skończonym, jest wymienny, ponieważ możesz napisać interpreter, który po prostu uruchamia program na wszystkich elementach zestawu skończonego i zwraca „tak”, jeśli wszystkie się zakończą. (Ale nie widzę, czy któryś z nich nie)

Twój profesor powiedział, że zestaw wszystkich programów, które są sumą w zestawie nieskończonym, nie jest wyliczalny, ponieważ nie możesz po prostu uruchomić programu na nieskończonej liczbie elementów.

Ale to nie znaczy, że to źle:

Na przykład zestaw, jeśli wszystkie programy, które są możliwe do udowodnienia, jest policzalny, ponieważ można wyliczyć wszystkie dowody i mechanicznie sprawdzić, czy dowodzą, że twój program jest sumą.
Nawet wymienny zestaw nie byłby praktyczny, ponieważ być może będziesz musiał czekać wiecznie, nie mając pewności, czy procedura zostanie zakończona pewnego dnia. Nie widzę, jak korzystać z programów, które wyliczają wszystkie funkcje ogółem ...

Istnieje kilka języków programowania, w których wszystko, co piszesz, z pewnością kończy się na pisaniu statycznym! Są nawet takie, które gwarantują ci wielomianowe ograniczenie. Na razie są w większości akademiccy, pisanie w nich prawdopodobnie sprawi, że poczujesz ograniczenia bardziej niż pisanie w Pythonie, ale wielu naukowców pracuje nad tym.

Aby odpowiedzieć na twoje pytanie: w pewnym sensie tak. Potencjalny brak zakończenia jest konieczny, aby być kompletnym Turinga (jak na razie najwyższa moc obliczeniowa). Ale nie uważam tego za bezpośrednio związane z faktem, że wszystkie funkcje są policzalne, czy nie. Nadal możesz pisać wszystkie programy!

— jmad
źródło

„ponieważ nie można po prostu uruchomić programu na nieskończonej liczbie elementów” - to słaby argument, ponieważ nie musiałbym tego robić, jeśli mogę uratować wszystkie informacje, których potrzebuję od samego programu. Zobacz tutaj pytanie ilustrujące niebezpieczeństwo twojego rozumowania.

— Raphael

W rzeczy samej. Nie twierdziłem, że to dowód (jak zawsze trzeba zbudować przekątny argument) i może nie powinienem był używać słowa „ponieważ”. Próbowałem odpowiedzieć na twoje pytanie, które (myślałem) nie dotyczyło dowodu wypowiedzi twojego profesora, ale tego, dlaczego wypowiedzenie jest sprzeczne z mocą obliczeniową.

— jmad