Pytania otagowane jako computability

Teoria obliczalności, czyli teoria rekurencji.

1
Nieporównywalne liczby naturalne
„Nazwa największej gry liczbowej” wymaga od dwóch graczy potajemnego zapisania numeru, a zwycięzcą jest osoba, która zapisała większą liczbę. Gra zazwyczaj pozwala graczom zapisywać funkcje ocenione w danym momencie, więc byłoby również do przyjęcia.2)2)2)2)2)2)2)2)2^{2^{2^{2}}} Wartości funkcji Busy Beaver, , nie można ustalić (w ZFC lub w żadnym rozsądnym spójnym systemie …
1
Entscheidungsproblem vs. Unvollständigkeitssatz (miękkie pytanie)
Pierwszy termin jest używany przez Hilberta w swojej pracy z 1928 roku, ale w późniejszej pracy Gödela to samo nazywa się Unvollständigkeitssatz („twierdzenie o niekompletności”). Dla dzisiejszych niemieckich badaczy CS wydaje się, że częściej stosuje się Unvollständigkeitssatz , a Entscheidungsproblem („problem decyzyjny”) jest nadal rozumiany, ale niekoniecznie związany z das …
4
Czy istnieje algorytmiczna analiza matematyczna?
Istnieją teorie grafów algorytmicznych / teoria liczb / kombinatoryka / teoria informacji / teoria gier. Czy istnieje algorytmiczna analiza matematyczna? Według wiki analiza matematyczna obejmuje teorie różniczkowania, całkowania, miary, limitów, szeregów nieskończonych i funkcji analitycznych. Można skupić się na analizie rzeczywistej (wiki), która zajmuje się liczbami rzeczywistymi i funkcjami wartości …
2
Jak ocenić, czy definicja złożoności obliczeniowej rzeczywistych jest naturalna czy odpowiednia?
Jak wiemy, definicja złożoności obliczeniowej algorytmu prawie nie budzi kontrowersji, ale definicja złożoności obliczeniowej rzeczywistych lub modeli obliczeniowych rzeczywistych nie jest w takim przypadku. Model i model Bluma i Smalesa znamy w książce Computable Analysis. I pozornie model w analizie obliczeniowej jest zgodny z modelem klasycznym, ale definicja złożoności obliczeniowej …
2
Jak mogę obliczyć węzły?
Czy istnieje udokumentowany sposób obliczania węzłów? (obwody osadzone w trójwymiarowej przestrzeni euklidesowej). Mam na myśli typ danych, który je reprezentuje, oraz algorytm określający, czy dwa wystąpienia typu danych reprezentują ten sam węzeł. Jeśli odpowiedź jest pozytywna, co ze złożonością tego problemu?
2
Związek twierdzeń o niekompletności Gödla z tezą Kościoła Turinga
To może być naiwne pytanie, ale proszę bardzo. (Edycja - nie ma głosów pozytywnych, ale nikt też nie odpowiedział; być może pytanie jest trudniejsze, niejasne lub niejasne, niż myślałem?) Pierwsze twierdzenie Gödela o niekompletności można udowodnić jako następstwo nierozstrzygalności problemu zatrzymania (np. Sipser Ch. 6; post na blogu Scotta Aaronsona …
1
Biorąc pod uwagę PDA M taki, że L (M) jest w DCFL konstruuj DPDA N, tak że L (N) = L (M)
Czy można zbudować algorytm, który przyjmuje jako dane wejściowe automat do przesuwania wraz z obietnicą, że język zaakceptowany przez ten automat L ( M ) jest deterministycznym językiem bezkontekstowym i wysyła deterministyczny automat do przesuwania N, który akceptuje dokładnie zaakceptowany język przez M ?MMML(M)L(M)L(M)N.NNM.MM Równoważne problemu byłoby skonstruować algorytm, który …
4
Znalezienie skończonego modelu
Wiem, że pytanie „czy formuła pierwszego rzędu ma model” jest ogólnie nierozstrzygalne.ϕϕ\phi Czy ktoś mógłby mi dać link lub książkę, która da odpowiedź na skończone modele. Jeśli mam wzór pierwszego rzędu , czy można rozstrzygnąć, czy ϕ ma model skończony? Jestem pewien, że pytanie jest dobrze znane, ale nawet nie …
1
Równowaga w grze w postój
Rozważ następującą grę 2-osobową: Natura losowo wybiera program Każdy gracz gra liczbę w [0, nieskończoność] włącznie w odpowiedzi na ruch natury Weź minimalną liczbę graczy i uruchom program dla (maksymalnie) tak wielu kroków (chyba że obaj gracze wybiorą nieskończoność) Jeśli program się zatrzyma, gracz, który zagrał minimalną liczbę, otrzymuje 1 …
1
Czy równania różniczkowe można zaklasyfikować do własnych klas złożoności?
Problemy zostały sklasyfikowane jako całość dzięki złożoności obliczeniowej. Ale czy w równaniach różniczkowych można klasyfikować równania różniczkowe w zależności od ich struktury obliczeniowej? Na przykład, jeśli równanie niejednorodne pierwszego rzędu jest stosunkowo trudne do rozwiązania niż, powiedzmy, równanie jednorodne 100 rzędu, czy można je zaklasyfikować jako osobne klasy wypukłości, biorąc …
1
Odwracalne plandeki Turinga?
To pytanie o to, czy istnieją jakieś znane tarpits odwracalny Turinga, gdzie „odwracalne” oznacza w sensie Axelsen i Glück , a „Tarpit” jest znacznie bardziej nieformalny pojęcie (i może nie być bardzo dobrym wyborem słowa), ale postaram się wyjaśnić, co mam na myśli. Co rozumiem przez „tarpit” Niektóre modele obliczeń …
2
O Inverse 3-SAT
Kontekst : Kavvadias i Sideri wykazali, że odwrotny problem 3-SAT jest coNP zakończony: Biorąc pod uwagę ϕϕ\phi zestaw modeli nnn zmiennych, czy istnieje wzór 3-CNF taki, że ϕϕ\phi jest jego dokładnym zestawem modeli? Powstaje formuła bezpośredniego kandydata, która jest połączeniem wszystkich 3-klauzul spełnionych przez wszystkie modele w ϕϕ\phi . Ponieważ …
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.