Pytania otagowane jako computability

Teoria obliczalności, czyli teoria rekurencji.

3
Twardość obliczeniowa „prawdziwych” programów komputerowych
Często słyszałem, jak mówiono, że nie można napisać programu do wychwytywania błędów w przeglądarce internetowej, edytorze tekstu lub systemie operacyjnym z powodu twierdzenia Rice'a: każda właściwość semantyczna dla języka pełnego Turinga jest nierozstrzygalna. Nie jestem jednak pewien, w jakim stopniu dotyczy to rzeczywistego programu, takiego jak systemy operacyjne. Czy tego …
1
Obliczeniowe konsekwencje twierdzenia Friedmana (nie do udowodnienia) na temat przesunięcia górnego o stałym punkcie?
Harvey Friedman wykazał, że istnieje dokładny wynik punktu stałego, którego nie można udowodnić w ZFC (zwykła teoria mnogości Zermelo-Frankela z Axiom of Choice). Wiele współczesnych układów logicznych opiera się na operatorach stałoprzecinkowych, więc zastanawiałem się: czy są znane konsekwencje twierdzenia o przesunięciu górnego przesunięcia dla teoretycznej informatyki? Nie do udowodnienia …
1
Czy przewidywanie (w granicach) sekwencji obliczalnych jest tak trudne, jak problem zatrzymania?
Pytanie : Czy przewidywanie (jak zdefiniowano poniżej) sekwencji obliczalnych jest tak trudne, jak problem zatrzymania? Opracowanie : „Przewidywanie” oznacza pomyślne przewidywanie, co oznacza popełnienie tylko skończonej liczby błędów w zadaniu próby przewidzenia n-tego bitu sekwencji, który ma dostęp do poprzednich bitów n-1 (zaczynając od pierwszego bitu i przechodząc przez cała …
1
Jednolita hierarchia problemów obejmujących złożoność i hierarchie obliczeniowe
Czy ktoś zna zestaw problemów, które różnią się równomiernie i obejmują jedną z „interesujących” hierarchii złożoności i obliczalności? Przez interesujące rozumiem na przykład Hierarchię Wielomianową, Hierarchię Arytmetyczną lub Hierarchię Analityczną. A może (N) P, (N) EXP, 2 (N) EXP, ……\ldots 0 , 0′, 0′¯¯¯¯, 0′ ′, 0′ ′¯¯¯¯¯, …0,0′,0′¯,0″,0″¯,…0, 0', …
1
Czy złożoność Kołmogorowa w tabelach prawdy problemu zatrzymania jest znana asymptotycznie?
Pozwolić HALTnHALTnHALT_n oznacz ciąg długości 2n2n2^n odpowiadający tabeli prawdy problemu zatrzymania dla danych wejściowych długości nnn. Jeśli sekwencja złożoności Kołmogorowa K(HALTn)K(HALTn)K(HALT_n) byli O(1)O(1)O(1), wtedy jeden z ciągów porad byłby używany nieskończenie często, a TM z tym ciągiem zakodowanym na stałe byłby w stanie rozwiązać HALTHALTHALT równomiernie nieskończenie często, o czym …
3
Definiowanie prymitywnych funkcji rekurencyjnych w stosunku do ogólnych typów danych
Pierwotne funkcje rekurencyjne są zdefiniowane ponad liczbami naturalnymi. Wydaje się jednak, że koncepcja powinna uogólnić na inne typy danych, pozwalając mówić o prymitywnych funkcjach rekurencyjnych, które mapują listy na przykład na drzewa binarne. Przez analogię częściowe funkcje rekurencyjne nad liczbami naturalnymi ładnie uogólniają się na funkcje obliczeniowe na dowolnym typie …
3
Czy klasa prymitywnych funkcjonałów rekurencyjnych jest równoważna z klasą funkcji, które płód kończy?
Płód, jeśli o nim nie słyszałeś, możesz przeczytać tutaj . Wykorzystuje system „macierzy wywołań” i „grafów wywołań”, aby znaleźć wszystkie „zachowania rekurencyjne” wywołań rekurencyjnych w funkcji. Pokazanie, że funkcja się kończy, pokazuje, że wszystkie zachowania rekurencyjne wywołań rekurencyjnych wykonanych do funkcji są zgodne z pewnym „porządkiem leksykograficznym”. Jego sprawdzanie zakończenia …
2
Czy możliwa jest meta-nierozstrzygalność?
Istnieją problemy, które można rozstrzygnąć, niektóre są nierozstrzygalne, istnieje możliwość rozstrzygnięcia itp. W tym przypadku zastanawiam się, czy problem może być nierozstrzygalny. Oznacza to (przynajmniej w mojej głowie), że nie możemy stwierdzić, czy jest to rozstrzygalne, czy nie. Być może wiadomo, że rozstrzygalność jest nierozstrzygalna (wszystko jest meta-nierozstrzygalne) i nie …
2
Dolna granica liczby wezwań wyroczni do rozwiązania przypadków problemu zatrzymania
Spotkałem następujące pytanie, które jest łatwym ćwiczeniem (spoiler poniżej). Dostajemy wystąpień problemu z zatrzymaniem (np. TM ) i musimy dokładnie zdecydować, które z nich zatrzymają się na . Oznacza to, że musimy . Dostajemy wyrocznię za problem zatrzymania, ale musimy go użyć minimalną liczbę razy.nnnM1,...,MnM1,...,MnM_1,...,M_nϵϵ\epsilon{i:Mi halts on ϵ}{i:Mi halts on …
2
Wyniki dotyczące złożoności funkcji rekurencyjnych o niższych elementach?
Zaintrygowany ciekawym pytaniem Chrisa Presseya na temat funkcji elementarno-rekurencyjnych badałem więcej i nie mogłem znaleźć odpowiedzi na to pytanie w Internecie. Te podstawowe funkcje rekurencyjne odpowiadają dobrze wykładniczemu hierarchii .DTIME (2)n) ∪ DTIME (2)2)n) ∪ ⋯DTIME(2n)∪DTIME(22n)∪⋯\text{DTIME}(2^n) \cup \text{DTIME}(2^{2^n}) \cup \cdots Z definicji wydaje się proste, że problemy decyzyjne rozstrzygalne (termin?) …
1
Prosty dowód, że rozstrzygalność typowalności w systemie F ( ) implikuje rozstrzygalność sprawdzania typu?
Załóżmy, że nie znamy wyniku Joe B. Wellsa z 1994 roku, że zarówno typowość, jak i sprawdzanie typów są nierozstrzygalne w Systemie F (AKA ). W rachunku Lambda z typami Barendregta (1992) znalazłem dowód z powodu Maleckiego 1989, że sprawdzanie typów implikuje typowość. To dlatego, żeλ 2λ2)\lambda 2 istnieje taki, …
3
Rozstrzygalność liczb transcendentalnych
Mam pytanie, na które odpowiedź jest prawdopodobnie dobrze znana, ale nie wydaje mi się, że po kilku poszukiwaniach znajdę coś znaczącego, więc byłbym wdzięczny za pomoc. Moje pytanie brzmi, czy wiadomo, że podjęcie decyzji, czy liczba jest transcendentalna, jest nierozstrzygalne. Być może ktoś przyjmuje jako dane wejściowe, powiedzmy program, który …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.