Istnieją relatywistyczne czasoprzestrzenie (np. Czasoprzestrzenie MH; patrz Hogarth 1994), w których linia świata o nieskończonym czasie trwania może być zawarta w przeszłości skończonego obserwatora. Oznacza to, że normalny obserwator może mieć dostęp do nieskończonej liczby kroków...
Wiem, że bram NAND można używać do tworzenia obwodów, które implementują każdą tabelę prawdy, a nowoczesne komputery są zbudowane z bram NAND. Jaki jest teoretyczny związek między bramkami NAND a kompletnością Turinga? Wydaje mi się, że obwody bramki NAND są bliższe automatom skończonym niż maszyny...
Mam te pytania ze starego egzaminu, który próbuję rozwiązać. Dla każdego problemu wejście jest kodowanie pewnej maszyny Turingowi .MMM Dla liczby całkowitej i następujących trzech problemów:c>1c>1c>1 Czy to prawda, że dla każdego wejścia , M nie przechodzi przez pozycję podczas...
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...
Czytałem w Wikipedii i innych tekstach, które Problem zatrzymania jest [...] rozstrzygalny dla automatów z ograniczeniami liniowymi (LBA) [i] deterministycznych maszyn ze skończoną pamięcią. Ale wcześniej napisano, że problem zatrzymania jest problemem nierozstrzygalnym, a zatem TM nie może go...
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...
Próbuję zrozumieć istnienie języków nierozpoznawalnych. Aby to uzyskać, muszę wiedzieć, dlaczego maszyna Turinga rozpoznaje tylko jeden język, a nie wiele. Dlaczego
Przeglądałem definicję języka kontekstowego w Wikipedii i znalazłem to: Każda kategoria języków jest odpowiednim podzbiorem kategorii bezpośrednio nad nią. Każdy automat i gramatyka w każdej kategorii ma równoważny automat lub gramatykę w kategorii bezpośrednio nad nią. Widziałem, że automat...
Definicje maszyn Turinga zawsze wyrażają jasno, że pusty symbol nie jest częścią alfabetu wejściowego. Zastanawiam się, co poszło nie tak, kiedy byłoby uczynić go częścią alfabetu wejściowego, ponieważ skutecznie pusty symbol już wydaje się być częścią wejścia. Aby wyjaśnić, że „wydaje się” w...
Tło: Jestem kompletnym laikiem w dziedzinie informatyki. Czytałam o numerach Busy Beaver tutaj i znalazłem następujący fragment: Ludzkość może nigdy nie poznać wartości BB (6) na pewno, nie mówiąc już o wartości BB (7) lub jakiejkolwiek większej liczbie w sekwencji. Rzeczywiście, wymyka się...
Czytałem odpowiedź na ostatnie pytanie i przyszło mi do głowy coś dziwnego, efemerycznego. Moje pytanie może zdradzić, że moim teoretycznym kotletom poważnie brakuje (głównie prawdy) lub że jest zbyt wcześnie, aby przeczytać tę stronę. Teraz, gdy wyłączenie odpowiedzialności jest na drodze...
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...
Zastanawiałem się, dlaczego taśma / taśmy nie są częścią formalnej definicji maszyny Turinga. Rozważmy na przykład formalną definicję maszyny Turinga na stronie Wikipedii . Definicja, po Hopcroft i Ullman, obejmuje: skończony zestaw stanów , alfabet taśmy Γ , pusty symbol b ∈ Γ , stan początkowy q...
Powiedziano mi, że komputery kwantowe nie są obliczeniowo mocniejsze niż maszyny Turinga. Czy ktoś mógłby pomóc w udzieleniu referencji literaturowych wyjaśniających ten
Przeczytałem kilka razy, że nie można skutecznie odwrócić odpowiedzi NDTM. Nie rozumiem jednak dlaczego. Na przykład, ze względu na NDTM MMM , która działa w , w tym tekstu (punkt 3.3), stwierdzono, że nie jest jasne, w jaki inny NDTM można określić w czas Jak Flip mówiąc”.T O ( n 100 )...
Czy istnienie nierozwiązywalnych problemów natychmiast implikuje nieprzewidywalność układów fizycznych? Rozważmy problem zatrzymania, najpierw konstruujemy fizyczny UTM, powiedzmy, używając zwykłej konstrukcji opartej na obwodach. Wtedy nie może istnieć rozstrzygalna teoria fizyczna, która mogłaby...
Niech Czy istnieje maszyna Turinga R, która decyduje (nie mam na myśli rozpoznać) język L ∅ ?L∅={⟨M⟩ ∣ M. jest maszyną Turinga i L ( M) = ∅ } .L∅={⟨M⟩∣M is a Turing Machine and L(M)=∅}.L_\emptyset = \{\langle M\rangle \mid M \text{ is a Turing Machine and...
W pracy miałem za zadanie wnioskować o pewnych typach informacji o dynamicznym języku. Przepisuję sekwencje instrukcji na letwyrażenia zagnieżdżone , tak jak poniżej: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then { T;...
Czytam Sipser i trudno mi zrozumieć, na czym polega ten proces, więc jeśli dasz mi k maszyn Turinga z k taśmami, mogę wypluć równoważną maszynę Turinga za pomocą tylko jednej taśmy. Przykład byłby miły. Właściwie to naprawdę opracowany przykład, który pokazuje, jak przejść z TM z taśmami na tę,...
Widziałem maszyny Turinga przedstawiane za pomocą taśm nieskończonych w jednym i w dwóch kierunkach. Czy jest jakaś różnica w mocy takich maszyn Turinga, czy są one zasadniczo równoważne? W mojej głowie myślę, że są one równoważne, ponieważ sądzę, że musi istnieć jakiś sposób na przedstawienie...