Post Korespondencja Problem (PCP) jest nierozstrzygalny. Ograniczoną wersją PCP jest -Complete i oznaczone wersja PCP (słowa jednego z obu listach muszą różnić się w pierwszej literze) jest P S P A C E [1].N P.NP\mathrm{NP}P S P A C EPSPACE\mathrm{PSPACE} Czy te ograniczone wersje są...
Czytam o zajętych liczbach bobrów io tym, jak rosną one asymptotycznie większe niż jakakolwiek obliczalna funkcja. Dlaczego tak jest? Czy to z powodu niemożności obliczenia funkcji zajętego bobra? Jeśli tak, to czy wszystkie funkcje niepoliczalne stają się asymptotycznie większe niż funkcje...
Jestem w pewnym sensie nowy, ale bardzo zainteresowany dziedziną obliczeń i teorii złożoności, i chcę wyjaśnić moje rozumienie, w jaki sposób klasyfikować problemy i jak silnie problemy odnoszą się do maszyny używanej do ich rozwiązywania. Moje zrozumienie Standardowa maszyna Turinga - maszyna...
Funkcja maksymalnych przesunięć bobra zajętego, , ma znane wartości dla n ≤ 4 . Czy istnieje jakiś podstawowy, strukturalny powód, dla którego jest nie do pomyślenia, abyśmy kiedykolwiek znaleźli S ( n ) dla n > 4 ? Czym tak różni się n = 4 niż n = 5 ? Lub n = 6 ? Gdzieś po drodze musi być jakaś...
Odpowiada sugestii Rafaela dotyczącej przecięcia dwóch NPDA : Niech i NPDA dla języków odpowiednio i . Zakładając, że wiemy, że jest kontekstu, czy możemy (skutecznie) skonstruować NPDA dla ?A1A1A_1A2A2A_2L1L1L_1L2L2L_2L=L1∩L2L=L1∩L2L = L_1 \cap L_2AAALLL Każdy typ algorytmu byłby do przyjęcia,...
Zastanawiam się, czy decydowanie o rozstrzygalności problemu jest problemem rozstrzygalnym. Chyba nie, ale po wstępnych poszukiwaniach nie mogę znaleźć literatury na ten
Wiele „znanych” nierozstrzygalnych problemów jest jednak co najmniej w połowie nierozstrzygalnych, a ich dopełnienie jest nierozstrzygalne. Jednym z przykładów może być przede wszystkim problem zatrzymania i jego uzupełnienie. Czy ktoś może jednak podać przykład, w którym zarówno problem, jak i...
Jeśli mamy dowolny dowolny program komputerowy, który może modyfikować jego instrukcje, czy można symulować ten program za pomocą programu, który nie może modyfikować jego instrukcji? Edytować: Jestem nowy w stosie wymiany, więc nie jestem pewien, czy mogę zadawać NOWE pytanie tutaj, ale oto:...
Studiuję twierdzenie smn, a koncepcja przypominała mi curry. Z artykułu w Wikipedii o twierdzeniu smn : twierdzenie mówi, że dla danego języka programowania i dodatnich liczb całkowitych m i n istnieje szczególny algorytm, który przyjmuje jako dane wejściowe kod źródłowy programu z m + n...
Mówi się, że teoria obliczalności nazywana jest również teorią rekurencyjną. Dlaczego tak się nazywa? Dlaczego rekurencja ma tak duże
Komentarz do tex.SE mnie zastanawiał. Oświadczenie to zasadniczo: Jeśli mogę napisać kompilator dla języka X w języku X, to X jest Turing-complete. Pod względem obliczalności i języków formalnych jest to: Jeśli decyduje L ⊆ L T, M i ⟨ M ⟩ ∈ L , to F L = R E .MM.ML⊆LTML.⊆L.T.M.L \subseteq...
Oto problem: Udowodnij, że maszyny Turinga z pojedynczą taśmą, które nie mogą pisać na części taśmy zawierającej łańcuch wejściowy, rozpoznają tylko zwykłe języki. Moim pomysłem jest udowodnienie, że ta konkretna baza TM jest odpowiednikiem DFA. Używanie tej TM do symulacji DFA jest bardzo...
Mam problem ze zrozumieniem problemu zatrzymania Turinga. Jego dowód zakłada, że istnieje magiczna maszyna która może ustalić, czy komputer zatrzyma się lub zapętli na zawsze dla danego wejścia. Następnie dołączamy inną maszynę, która odwraca dane wyjściowe i mamy sprzeczność i dlatego H nie...
Jak można rozstrzygać, czy ma pewną sekwencję cyfr? ππ\pizainspirowało mnie do pytania, czy można obliczyć następującą niewinnie wyglądającą odmianę: fa( n ) = { 10jeśli n¯ występuje w postaci dziesiętnej πInaczejf(n)={1if n¯ occurs in the decimal representation of π0otherwisef(n) =...
Przepisanie systemu jest zestaw reguł w postaci . Jeśli zastosujemy tę regułę do łańcucha , zastąpimy dowolny podciąg in podciągiem i odwrotnie.A↔BA↔BA \leftrightarrow BwwwAAAwwwBBB Biorąc pod uwagę początkowy ciąg możemy wyprowadzić w systemie według następujących...
Jedna z definicji zestawu wyliczalnego (ce, równoważnego rekurencyjnie wyliczalnemu, równoważnego semidecidable) jest następująca: A⊆Σ∗A⊆Σ∗A \subseteq \Sigma^* oznacza, że istnieje rozstrzygalny językV⊆Σ∗V⊆Σ∗V\subseteq \Sigma^* (zwany weryfikatorem) st dla wszystkichx∈Σ∗x∈Σ∗x\in \Sigma^* ,...
Ostatnie pytanie egzaminacyjne brzmiało następująco: jest nieskończonym zestawem rekurencyjnie wyliczalnym. Wykazać, że A ma nieskończony rekurencyjny podzbiór.ZAAAZAAA Niech jest nieskończony rekurencyjne podzbiór A . Czy C musi mieć podzbiór, którego nie można wyliczyć...
Czy teoretycznie jest możliwe określenie języka programowania, dla którego nie byłoby możliwe wdrożenie? Język programowania to sposób definiowania funkcji. Implementacja oznacza metodę wykonania danego programu w tym języku na danym wejściu na wyjściu funkcji odpowiadającej programowi na tym...
Natknąłem się na następujący interesujący problem: niech będą wielomianami na polu liczb rzeczywistych i załóżmy, że wszystkie ich współczynniki są liczbami całkowitymi (tzn. Istnieje dokładna reprezentacja tych wielomianów). W razie potrzeby możemy założyć, że stopień obu wielomianów jest równy....
Czy istnieje algorytm dla następującego problemu: Biorąc pod uwagę maszynę Turinga która decyduje o języku L , czy istnieje maszyna Turinga M 2 decydująca L, tak że t 2 ( n ) = o ( t 1 ( n ) ) ?M.1M1M_1L.LLM.2)M2M_2L.LLt2)( n ) = o ( t1( n ) )t2(n)=o(t1(n))t_2(n) = o(t_1(n)) Funkcje i t 2...