Pytania otagowane jako computability

Pytania związane z teorią obliczalności, czyli teorią rekurencji

2
-algebrze na wejściu algorytmu
Chcę sprecyzować, co to znaczy podać algebrę jako dane wejściowe do algorytmu i nie znalazłem zbyt wiele literatury na ten temat. Najpierw chciałbym zapytać, czy możesz polecić książkę lub artykuł, który porusza temat analizy złożoności algebr nad polami i jasno określa problem decyzyjny . Po kilku kopaniach znalazłem coś i …
1
podzbiory nieskończonych zbiorów rekurencyjnych
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ć rekurencyjnie?doCCZAAAdoCC Odpowiedziałem już 1.. W odniesieniu do 2. odpowiedziałem twierdząco i twierdziłem, co następuje. Załóżmy, że wszystkie …
1
Czy w tym systemie przepisywania można uzyskać ciąg znaków?
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 reguł:AAABBAAABBAAABBBAABBAABBAAB A↔BAA↔BAA \leftrightarrow BA BABA↔AABBBABA↔AABBBABA \leftrightarrow AABB AAA↔ABAAA↔ABAAA \leftrightarrow AB BA↔ABBA↔ABBA \leftrightarrow AB Czy jest …
1
Czy funkcja szukająca podciągów cyfr
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) = \begin{cases} 1 & \text{if \(\bar n\) occurs in the decimal …
1
Czy są jakieś istniejące problemy, których nie można rozwiązać za pomocą wyroczni zatrzymującej?
Rozumiem, że większość problemów jest trywialna, jeśli dostępna jest wyrocznia zatrzymująca (lub, moim zdaniem, hiper-obliczenia). Jednak zastosowanie argumentu, który pokazuje, że problem zatrzymania jest niemożliwy dla maszyny Turinga, pokazuje również, że wyrocznia Turinga + nie może zdecydować o problemie zatrzymania dla wyroczni Turinga +. Czy istnieją jakieś rzeczywiste, praktyczne przykłady …
2
Jeśli A mapuje się redukowalnie do B, to dopełniacz A jest mapowalny redukowalny do dopełniacza B
Studiuję do finałowej teorii obliczeń i walczę z właściwym sposobem odpowiedzi na pytanie, czy to stwierdzenie jest prawdziwe w odniesieniu do fałszu. Przez definicję z możemy skonstruować następujące oświadczenie,≤m≤m\leq_m w ∈ A⟺fa( w ) ∈ B → w ∉ A⟺fa( w ) ∉ Bw∈A⟺f(w)∈B→w∉A⟺f(w)∉Bw \in A \iff f(w) \in B …
2
Czy możemy pokazać, że języka nie da się wyliczyć, pokazując, że nie ma dla niego weryfikatora?
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^* , IFF istnieje y ∈ Ď * st ⟨ x , y ⟩ ∈ V .x∈Ax∈Ax\in Ay∈Σ∗y∈Σ∗y\in\Sigma^*⟨x,y⟩∈V⟨x,y⟩∈V\langle x, y \rangle \in V …
1
Czy istnieje logiczna koncepcja „Turing Complete”?
Można wykazać, że dwa modele obliczeniowe są kompletne, jeśli każdy z nich może zakodować uniwersalny symulator dla drugiego. Można wykazać, że dwie logiki są kompletne, jeśli kodowanie reguł wnioskowania (i może aksjomatów, jeśli są obecne) każdego z nich jest twierdzeniem drugiej. W obliczeniach doprowadziło to do naturalnego pomysłu kompletności Turinga …
1
Analiza złożoności algorytmu dla implementacji funkcjonalnego języka programowania
Dowiedziałem się dzisiaj, że analiza algorytmów różni się w zależności od modelu obliczeniowego. To jest coś, o czym nigdy nie myślałem ani nie słyszałem. Przykładem podanym mi przez użytkownika @chi , który dalej to ilustruje : Np. Rozważ zadanie: dany zwraca x i . W pamięci RAM można to rozwiązać …
1
Czy problem zatrzymania jest rozstrzygalny w przypadku trójwymiarowych automatów komórkowych?
Próbowałem dowiedzieć się, czy problem zatrzymania jest rozstrzygalny w przypadku trójwymiarowych jednowymiarowych automatów komórkowych. Definicja Niech f(w,i)f(w,i)f(w,i) oznacza konfigurację systemu w kroku czasowym iii . Bardziej formalnie f:A∗×N→A∗f:A∗×N→A∗f:A^*\times \mathbb{N} \to A^* , gdzie AAA jest alfabetem. Definicja. Automat komórkowy zatrzymał się w konfiguracji f(w,i)f(w,i)f(w,i) , jeśli ∀k∈N∀k∈N\forall k\in \mathbb{N} mamy …
3
Obliczenia nieskończone w czasie skończonym
Jest to prawdopodobnie głupia myśl, ale załóżmy, że mamy komputer, który jest zaprogramowany do wykonywania nieskończonej sekwencji obliczeń i załóżmy, że wykonanie obliczenia zajmuje sekundy sekundę. Następnie ten komputer może wykonać nieskończoną liczbę obliczeń w skończonym czasie.jathjathi^\text{th}1 / 2ja1/2)ja1/2^i Dlaczego to jest niemożliwe? Czy istnieje dolna granica czasu potrzebnego do …
1
W jaki sposób uniwersalna maszyna Turinga może symulować „większe”?
Próbuję znaleźć odpowiedzi na dwa pytania dotyczące uniwersalnej maszyny Turinga. Jak uniwersalna maszyna Turinga może symulować maszynę Turinga, jeśli symulowana ma większą liczbę stanów? Jak uniwersalna maszyna Turinga może symulować maszynę Turinga, jeśli symulowana ma większą liczbę znaków alfabetu? Czy ktoś może mi pomóc z tymi pytaniami?
2
Zatrzymanie problemu bez odniesienia
W przypadku problemu zatrzymania jesteśmy zainteresowani, czy istnieje maszyna Turinga T.TT która może stwierdzić, czy dana maszyna Turinga M.MM zatrzymuje się, czy nie na danym wejściu . Zwykle dowód zaczyna zakładać, że taki istnieje. Następnie rozważamy przypadek, w którym ograniczamy do samego , a następnie wyprowadzamy sprzeczność za pomocą wystąpienia …
2
Jasny, kompletny, dowód na to, że język jest konkurencyjny w Turingu?
Widziałem strony internetowe, które rzekomo „dowodzą”, że HTML5 + CSS jest Turing Complete. Widziałem strony internetowe, które rzekomo „dowodzą”, że SQL jest Turing Complete. Widziałem kilka stron internetowych, które rzekomo „wyjaśniają”, co to znaczy być Turing Complete. Wystarczająco! Gdzie mogę znaleźć książkę (napisaną przez eksperta w dziedzinie teorii obliczeń) lub …
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.