Pytania otagowane jako turing-machines

Pytania o maszyny Turinga, teoretyczny model obliczeń mechanicznych zdolny do symulacji dowolnego programu komputerowego.

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?
1
Co oznacza przestrzeń podliniowa dla maszyn Turinga?
Udowodniono, że problem decydowania, czy wejście jest palindromem, czy nie wymaga miejsca na maszynie Turinga. Jednak nawet przechowywanie danych wejściowych zajmuje miejsce n, więc czy to nie znaczy, że wszystkie maszyny Turinga wymagają miejsca Ω ( n ) ?Ω ( logn )Ω(log⁡n)\Omega(\log n)nnnΩ ( n )Ω(n)\Omega(n) Oczywiście nie ma tutaj …
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 …
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 …
1
Wykazać, że funkcja boolowska obliczalna w T (n) przez maszynę RAM jest w DTIME (T (n) ^ 2)
Pytanie brzmi: ćwiczenie 1.9 z książki Arory-Barak Computational Complexity - A Modern Approach : Zdefiniuj maszynę RAM Turing jako maszynę Turinga, która ma pamięć o dostępie swobodnym. Sformalizujemy to w następujący sposób: Maszyna ma nieskończoną tablicę A, która jest inicjalizowana dla wszystkich spacji. Uzyskuje dostęp do tej tablicy w następujący …
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 …
3
Złożoność przestrzeni rozpoznawania palindromów Watsona-Cricka
Mam następujący problem algorytmiczny: Określ przestrzeń Turinga złożoności rozpoznawania ciągów DNA, które są palindromami Watsona-Cricka. Palindromy Watsona-Cricka to ciągi, których odwróconym dopełnieniem jest ciąg oryginalny. Dopełnieniem jest zdefiniowany litery mądry inspirowany DNA: A jest dopełnieniem T, a C jest dopełnieniem G. prosty przykład dla WC-palindrom jest ACGT. Wymyśliłem dwa sposoby …
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
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, …
1
Czy niedeterminizm w niedeterministycznej maszynie Turinga różni się od automatów skończonych i automatów wypychających?
Niech łańcuch wejściowy będzie podany jako w1w2...wnw1w2...wnw_1w_2...w_n. Następnie, jeśli NFA jest obecnie w stanierrr (i przeczytał wejście do alfabetu wiwiw_i ), a następnie przed odczytaniem następnego symbolu wejściowego NFA dzieli się na dwa NFA, z których jeden jest w stanie rrr i inne istnienie w sss, jeśli istnieje przejście tego …
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.