Dwa dokumenty, które chciałbym załączyć to: D. Kozen, „Indeksowanie klas subrekursywnych” , STOC, 1978. R. Ladner, „O strukturze wielomianowej redukcji czasu” , JACM,
Jak rozumiem, dowód, że P = NP lub P ≠ NP musiałby być nierelatywny (jak w wyroczniach teorii rekurencji). Praktycznie wszystkie dowody wydają się być relatywne. Jakie są dobre przykłady spoza relativizable dowodów, w tym rodzaju, że P = NP / P ≠ NP dowód musiałby być, że nie są błahe albo...
Zwykłym sposobem udowodnienia nierozstrzygalności jest redukcja problemu RE-zupełnego, takiego jak problem zatrzymania, trafność w logice pierwszego rzędu, spełnienie równań diofantycznych itp. Wiadomo, że istnieją rekurencyjnie wyliczalne, ale nierozstrzygalne problemy, które nie są uzupełniane...
Czy można zbudować mechaniczną implementację powiedzmy Microsoft Word w jednym celu (bez Turinga)? Czy można wdrożyć takie rzeczy jak iteratory, funkcje pierwszego rzędu, całą gamę technik programowania? Czy koła zębate i inne części mechaniczne mogą reprezentować struktury danych, a nawet obiekty...
HT(n)HT(n)HT(n)nnnBB(n)=maxHT(n)BB(n)=maxHT(n)BB(n) = \max HT(n) Co możemy powiedzieć o drugiej największej liczbie w ? Nazwij to .HT(n)HT(n)HT(n)BB2(n)BB2(n)BB_2(n) BB2(n)BB2(n)BB_2(n) jest banalnie nieobliczalny, ponieważ pozwala obliczyć : wystarczy poczekać, aż zatrzyma się jeszcze jedna...
Wiadomo, że problem zatrzymania jest niemożliwy do obliczenia. Możliwe jest jednak wykładnicze „kompresowanie” informacji o problemie zatrzymania, tak aby dekompresowanie było możliwe do obliczenia. Dokładniej, można obliczyć na podstawie opisu maszyn Turinga, a n- bitowa porada stanowi odpowiedź...
Jest to prawdopodobnie dość proste, ale weź pod uwagę standardowy problem z korespondencją: Biorąc pod uwagę, i β 1 , ... , β N , znaleźć sekwencję indeksów i 1 , ... , i K tak, że a i 1 ⋯ α i K = β i 1 ⋯ β i K . Jest to oczywiście nierozstrzygalne.α1, … , ΑN.α1,…,αN\alpha_1, \ldots, \alpha_Nβ1, …...
Próbowałem owinąć głowę wokół tego, co, dlaczego i jak rachunek, ale nie jestem w stanie poradzić sobie z „dlaczego to działa”?λλ\lambda „Intuicyjnie” dostaję model obliczeniowy Turing Machines (TM). Ale ta abstrakcja wprawia mnie w zakłopotanie.λλ\lambda Załóżmy, że bazy danych nie istnieją -...
Jaki jest najprostszy model obliczeniowy, dla którego problem pustki jest nierozstrzygalny? Problem pustki dla modelu obliczeniowego (np. Automat skończony, automat przemienny, automat kwantowy z ograniczeniem błędu z licznikiem, deterministyczny LBA itp.) Polega na ustaleniu, czy dla danej takiej...
Możemy myśleć o złożoności łańcucha Kołmogorowa jako długości najkrótszego programu P i wprowadzić y tak, że x = P ( y ) . Zazwyczaj programy te są pobierane z jakiegoś kompletnego zestawu Turinga (np. P może być opisem maszyny Turinga lub może to być program w LISP lub C). Nawet gdy patrzymy na...
Papier Lauri Hella i José María Turull-Torres, Obliczanie zapytań z logiką wyższego rzędu , TCS 355 197–214, 2006. doi: 10.1016 / j.tcs.2006.01.009 proponuje logikę VO, logikę zmiennego rzędu. Umożliwia to kwantyfikację zamówień ponad zmiennymi. VO jest dość potężny i może wyrażać niektóre...
Niech s i zmisjazmisize z λλ\lambda -terms być zdefiniowana w następujący sposób: s i ze ( x ) = 1sjazmi(x)=1size(x) = 1 , s i ze ( λ x . t ) = s i ze ( t ) + 1sjazmi(λx.t)=sjazmi(t)+1size(λx.t) = size(t) + 1 , s i ze ( t s ) = s i ze ( t ) + s i ze ( s ) + 1sjazmi(ts)=sjazmi(t)+sjazmi(s)+1size(t...
Zwykle łatwiej jest uzasadnić rachunek różniczkowy, w którym ograniczeniem jest skończoność obliczeń, a nie próg taki jak „obliczalny w wielomianowym czasie”. Na przykład w teorii języków formalnych, zamiast używać aby scharakteryzować aperiodic monoïd, łatwiej jest używać profinite wyrazów, aby...
Czy istnieją rozstrzygalne problemy, takie że dla żadnego algorytmu, który nie rozwiązałby problemu, możemy wyznaczyć limit czasowy jako funkcję długości n instancji wejściowej? Doszedłem do tego pytania, ponieważ myślałem o następujących kwestiach: Załóżmy, że mamy rekurencyjnie wymienny, ale...
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...
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...
Rozstrzyga się następujący problem: Biorąc pod uwagę bezkontekstową gramatykę , czy ?L ( G ) = ∅solGGL ( G ) = ∅L(G)=∅L(G) = \varnothing Następujący problem jest nierozstrzygalny: Biorąc pod uwagę bezkontekstową gramatykę , czy L (G) = A ^ {\ ast} ?L ( G ) = A ∗solGGL ( G ) = A∗L(G)=A∗L(G) =...
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...
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...
„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...