(Fałsz?) Dowód na obliczalność funkcji?

Rozważmy , funkcja, która zwraca 1 i zer pojawiających się kolejno w . Teraz ktoś dał mi dowód, że jest obliczalny:n π f ( n $f(n)$$n$$\pi$$f(n)$

Albo dla wszystkich n, pojawia się w , lub jest st pojawia się w a nie. Dla pierwszej możliwości ; Dla drugiego iff , w przeciwnym razie 0. π 0 m π 0 m + 1 f ( n ) : = 1 f ( n ) : = 1 n ≤ $0^n$$\pi$$0^m$$\pi$$0^{m+1}$$f(n) := 1$$f(n) := 1$$n \leq m$

Autor twierdzi, że dowodzi to obliczalności , ponieważ istnieje algorytm do jej obliczenia.$f(n)$

Czy ten dowód jest poprawny?

Pomyśl o tym w ten sposób, Mike: Ten dowód „rozgałęzia się” na wiele możliwych przypadków, z których jeden musi być prawdziwy (używając prawa wykluczonego środka, że ​​dla każdej zdania albo p jest prawdziwe, albo ¬ p jest prawdziwe). Ale na końcu każdej z tych gałęzi zawsze udaje się udowodnić, że funkcja f jest obliczalna. Dlatego bez względu na to, który z przypadków faktycznie zachodzi w rzeczywistości, f musi być obliczalne. (Jednak dokładny powód, dla którego f jest obliczalny, będzie różny, w zależności od gałęzi.)$p$$p$$\neg p$$f$$f$ $f$

Jest poprawna. Jest to to samo, co następuje: zdefiniuj jako stałą funkcję x ↦ 0, jeśli Bóg istnieje, i x ↦ 1, jeśli Bóg nie istnieje. Wynikowa funkcja jest funkcją stałą, dlatego jest obliczalna. To, czego możesz nie być w stanie zrobić, to dać tę funkcję, ale sama funkcja jest obliczalna.$f(x)$$x \mapsto 0$$x \mapsto 1$

Tutaj jedna z dwóch możliwości jest prawdą: albo istnieje takie , albo nie. Funkcja jest albo funkcją stałą x ↦ 1, albo prostą funkcją progową, zdefiniowaną za pomocą m .$m$$x \mapsto 1$$m$

Myślę - i mam nadzieję - że każdy student informatyki ma do czynienia z tym problemem, który wydaje się paradoksonem. Jest to bardzo dobry przykład różnicy obliczalnej w sensie TCS i obliczalnej w sensie praktycznym.

$\pi$$\pi$

$f$$\exists M \in TM : f_M = f$

Podstawową ideą dowodu jest: Daję ci nieskończoną klasę funkcji, wszystkie z nich obliczalne (aby pokazać; trywialne tutaj). Udowadniam zatem, że funkcja, której szukasz, znajduje się w tej klasie (aby pokazać; rozróżnienie wielkości liter tutaj). co było do okazania

Tak, zgadza się, jego obliczalność. Problem polega na tym, że twoja funkcja tak naprawdę nie tworzy rozwiązania nieskończonej rodziny problemów, tak jak (powiedzmy) funkcja obliczająca rozwiązanie problemu zatrzymania jest - więc nie ma problemu z obliczeniami. Zamiast tego reprezentujesz w formie funkcji pojedynczy fakt matematyczny ze skończoną reprezentacją - albo liczbą całkowitą, albo fakt, że f jest funkcją zawsze 1

$\Omega$

Znalezienie poprawnego algorytmu może oczywiście być trudnym problemem. Ale znalezienie prawidłowych algorytmów jest zwykle trudne!

post nieco stary, ale chciałem opublikować inną odpowiedź.

Jest to niekonstruktywny dowód (lub argument) obliczalności. Po prostu mówi, że funkcja musi istnieć w pewnym sensie, ponieważ mogę ją reprezentować (lub bardziej poprawnie indeksować), w zestawie (lub we wszechświecie) funkcji obliczalnych. Jednak ani nie konstruuje samej maszyny (tj. Algorytmu), ani indeksu (zakładając skuteczne wyliczenie maszyn obliczalnych). Angielskie wyrażenie „ dzięki za nic ” wydaje się w tych przypadkach najbardziej odpowiednie, takie jak:

-- Look, I proved there is water somewhere! 

Now you can be happy, while dying from thirst!

Ludzie w historii matematyki sporo spierali się o faktyczną ważność (lub zakres ważności) i znaczenie takich argumentów. Rezultatem końcowym jest to, że ten sam typ argumentów pojawia się ponownie w twierdzeniach o niekompletności Goedela i zwraca się przeciwko temu „założeniu zamkniętego wszechświata” .

Jeśli nie podobają ci się te argumenty, nie winiłbym cię.