Pytania otagowane jako computability

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

3
Rozważalne języki i nieograniczone gramatyki?
Maszyny Turinga i nieograniczona gramatyka to dwa różne formalizacje, które definiują języki RE. Niektóre języki RE są rozstrzygalne, ale nie wszystkie są. Możemy zdefiniować rozstrzygalne języki za pomocą maszyn Turinga, mówiąc, że dany język jest rozstrzygalny, jeśli istnieje TM dla języka, który zatrzymuje i akceptuje wszystkie ciągi w języku oraz …
2
Jest mocą obliczeniową sieci neuronowych związaną z funkcją aktywacyjną
Udowodniono, że sieci neuronowe o racjonalnych wagach mają moc obliczeniową uniwersalnej maszyny Turinga. Obliczalność Turinga z sieciami neuronowymi . Z tego, co otrzymuję, wydaje się, że użycie ciężarów o wartościach rzeczywistych daje jeszcze więcej mocy obliczeniowej, chociaż nie jestem tego pewien. Czy istnieje jednak korelacja między mocą obliczeniową sieci neuronowej …
1
Turing Recognizable => enumerable
Dostaję dowód przejścia z modułu wyliczającego do maszyny Turinga (kontynuuj działanie modułu wyliczającego i zobacz, czy pasuje on do danych wejściowych), ale nie widzę, jak działa inny sposób. Zgodnie z moimi notatkami i książką (Wprowadzenie do teorii obliczeń - Sipser), aby pobrać moduł wyliczający Turinga z maszyny Turinga, w zasadzie …
4
Czy istnieje niezdecydowany skończony język skończonych słów?
Czy istnieje potrzeba, aby L⊆Σ∗L⊆Σ∗L\subseteq \Sigma^* była nieskończona, aby była nierozstrzygalna? Chodzi mi o to, że jeśli wybierzemy język L′L′L' jako ograniczoną skończoną wersję L⊆Σ∗L⊆Σ∗L\subseteq \Sigma^* , to znaczy |L′|≤N|L′|≤N|L'|\leq N ( N∈NN∈NN \in \mathbb{N} ), a L′⊂LL′⊂LL' \subset L . Czy jest możliwe, L′L′L' być język nierozstrzygalny? Widzę, że …
4
Czy maszyna Turinga (TM) może zdecydować, czy problem zatrzymania dotyczy wszystkich baz TM?
Na tej stronie istnieje wiele wariantów pytania, czy bazy TM mogą zadecydować o problemie zatrzymania, czy dla wszystkich innych baz TM lub niektórych podzbiorów. To pytanie jest nieco inne. Pytanie, czy problem zatrzymania dotyczy wszystkich baz TM może zostać rozstrzygnięty przez TM. Uważam, że odpowiedź brzmi „nie” i chcę sprawdzić …
4
Problem ograniczonego zatrzymania jest rozstrzygalny. Dlaczego ten konflikt z twierdzeniem Rice'a?
Jedno stwierdzenie twierdzenia Rice'a znajduje się na stronie 35 „Złożoności obliczeniowej: nowoczesne podejście” (Arora-Barak): Funkcja częściowa od do to funkcja, która niekoniecznie jest zdefiniowana na wszystkich jej wejściach. Mówimy, że TM oblicza funkcję cząstkową jeżeli dla każdego na którym zdefiniowano , i dla każdego na którym nie zdefiniowano przechodzi w …
2
Dla dowolnego języka istnieje takie, że ale
Próbuję wymyślić dowód na następujące kwestie: Dla każdego języka AAA istnieje język BBB , tak że A≤TBA≤TBA \le_{\mathrm{T}} B a B ≰TA≰TA\nleq_{\mathrm{T}} A . Myślałem o pozwoleniu BBB być ATMATMA_{\mathrm{TM}} , ale zdaję sobie sprawę, że nie wszystkie języki Turing można zredukować do ATMATMA_{\mathrm{TM}} , więc A≤TBA≤TBA \le _T B …
2
Czy to możliwe, że problem zatrzymania można rozwiązać dla wszystkich danych wejściowych oprócz kodu maszyny?
To pytanie przyszło mi do głowy z powodu problemu z zatrzymaniem i nie mogłem znaleźć dobrej odpowiedzi online, zastanawiając się, czy ktoś może pomóc. Czy jest możliwe, że problem zatrzymania jest rozstrzygalny dla dowolnej TM na dowolnym wejściu, o ile wejście nie jest samą TM? Gruntownie: Halts(TM, I) IF TM …
3
Konstruktywna wersja rozstrzygalności?
Dzisiaj podczas lunchu poruszyłem ten problem z kolegami i ku mojemu zdziwieniu argument Jeffa E., że problem jest rozstrzygalny, nie przekonał ich ( oto ściśle powiązany post na temat przepływu matematyki). Stwierdzenie problemu, które jest łatwiejsze do wyjaśnienia („czy P = NP?”) Jest również rozstrzygalne: albo tak, albo nie, a …
2
Jak udowodnić, że 3-kolorowanie jest rozstrzygalne?
Czy w celu udowodnienia, że ​​3-zabarwienie jest rozstrzygalne, wystarczy powiedzieć: Każdy węzeł na wykresie ma 3 możliwe kolory Dlatego możemy policzyć wszystkie możliwości, a następnie sprawdzić, czy żadne dwie krawędzie nie łączą węzłów o tym samym kolorze3n3n3^n Czy to dowodzi, że 3-kolorowanie jest rozstrzygalne? Czy też muszę zbudować maszynę Turinga, …
2
Rozstrzygalność sprawdzania pierwotnego?
Załóżmy, że mam dwie funkcje i i jestem zainteresowany ustaleniem, czyFFFGGG F(x)=∫G(x)dx.F(x)=∫G(x)dx.F(x) = \int G(x)dx. Załóżmy, że moje funkcje składają się z funkcji elementarnych (wielomiany, wykładnicze, logi i funkcje trygonometryczne), ale nie, powiedzmy, szereg Taylora. Czy można rozwiązać ten problem? Jeśli nie, czy jest to w połowie rozstrzygalne? (Pytam, ponieważ …
2
Czy istnieje jasna definicja „obliczalnego” dla modeli obliczeniowych, które nie są kompletne?
Jest to kontynuacja kolejnego pytania tutaj i mam nadzieję, że nie jest to zbyt filozoficzne. Jak zauważył Raphael w komentarzu do mojego poprzedniego pytania, tak naprawdę nie rozumiem definicji „obliczalnego”, ale zgodnie z niektórymi artykułami, które czytam, definicja nie jest również bardzo jasna, jeśli chodzi o modele obliczeń słabsze niż …
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.