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

19

Rozważmy , funkcja, która zwraca 1 i zer pojawiających się kolejno w . Teraz ktoś dał mi dowód, że jest obliczalny: $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^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?

computability

— Mike B.
źródło

2

Możesz użyć lateksu w swoich pytaniach, aby były bardziej czytelne.

— Dave Clarke

7

Argument jest poprawny, ale nie konstruktywny. Osoba nie daje TM, daje dwie TM i mówi, że jedna z nich oblicza żądaną funkcję, ale nie wie, która.

— Kaveh,

1

Twoja wersja jest obliczalna. Jednak źle odczytałem i przypadkowo znalazłem wersję, która moim zdaniem jest nieobliczalna. Jedyna zmiana: zamiast dokładnie n zer zapytaj, czy π ma najwyżej n zer. Jeśli tak, uważam, że nie możesz tego potwierdzić, ponieważ π ma nieskończoną liczbę cyfr i nie ma (wydaje się?) Wzorca, który nie pojawia się ponownie.

— chazisop

Kiedyś poprawiłem stronę Wikipedii, która popełniła podobny błąd, twierdząc, że istnienie stałej Chaitin udowodniło istnienie „nieobliczalnych liczb całkowitych”.

— Geoffrey Irving

tego rodzaju pytania dotyczą „trywialnych języków”. ale zwróć uwagę, jak zwykle niewielkie przeformułowanie, np. gdy językiem jest

gdzie

jest (lub pierwszą) lokalizacją ciągu

lub -1, jeśli nie ma takiego ciągu, może być nierozstrzygalne. zobacz także, jak można rozstrzygać, że

ma pewną sekwencję cyfr? / Informatyka

f (n, k) = m

$f(n, k) = m$

m

$m$

0^{k}

$0^k$

π

$\pi$

— dniu

23

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 jest prawdziwe, albo jest prawdziwe). Ale na końcu każdej z tych gałęzi zawsze udaje się udowodnić, że funkcja jest obliczalna. Dlatego bez względu na to, który z przypadków faktycznie zachodzi w rzeczywistości, musi być obliczalne. (Jednak dokładny powód, dla którego jest obliczalny, będzie różny, w zależności od gałęzi.) $p$ $p$ $\neg p$ $f$ $f$ $f$

— Ryan Williams
źródło

16

Jest poprawna. Jest to to samo, co następuje: zdefiniuj jako stałą funkcję jeśli Bóg istnieje, i 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łą albo prostą funkcją progową, zdefiniowaną za pomocą . $m$ $x \mapsto 1$ $m$

— Michaël Cadilhac
źródło

4

Chciałbym wymienić „jeśli Bóg istnieje” z

. :)

P \neq N P

$P \neq NP$

— Kaveh

Ok, przepraszam za nieporozumienie, nie mam problemu z niekonstruktywnością dowodu. Problemem jest to, że my (a przynajmniej ja) nie wiemy, czy

jest obliczalny, czy nie. Dlaczego nie trzeba tego potwierdzać?

m

$m$

— Mike B.,

5

Nie ma sensu mówić o tym, czy liczba całkowita jest obliczalna, czy nie. Bez względu na to, jaką wartość przyjmuje m, istnieje maszyna Turinga, która ją generuje. Znalezienie go może być trudne, ale nie różni się tak bardzo od ogólnej sytuacji: znalezienie algorytmów jest trudne, co sprawia, że wielu z nas jest zatrudnionych.

— Aaron Roth,

Nadal nie rozumiem. Jaka maszyna Turinga mogłaby generować ten m? Musiałby nie tylko wykazać, że

pojawia się w

, ale musiałby też sprawdzić, czy

nie ma - i to jest problem IMO.

0^{m}

$0^m$

π

$\pi$

0^{m + 1}

$0^{m+1}$

— Mike B.

To jest konstruktywny sposób mówienia. Jeśli dam ci maszynę, która wyjścia takie

, że nie trzeba przekonywać, że jest to odpowiednia

, jak to jest maszyna do outputing taką

(dobrze, maszyna przynajmniej). Jest to to samo, co przykład Boga (który BTW pochodzi od Sipsera): jeśli maszyna generuje

, nie musi cię przekonywać, że Bóg nie istnieje. Tak właśnie jest.

m

$m$

m

$m$

m

$m$

0

$0$

— Michaël Cadilhac

14

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

— Raphael
źródło

9

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!

— Aaron Roth
źródło

3

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ę.

— Nikos M.
źródło