Na przykład w językach programowania często pisze się kompilator / interpreter X-w-X, ale na bardziej ogólnym poziomie wiele znanych systemów Turing-complete może symulować się w imponujący sposób (np. Symulując grę życia Conwaya w grze życia Conwaya ). Moje pytanie brzmi zatem: czy system jest w...
Problem decyzyjny CNF-SAT można opisać następująco: Dane wejściowe: wzór logiczny ϕϕ\phi w spójnej postaci normalnej. Pytanie: Czy istnieje przypisanie zmiennej spełniające ϕϕ\phi ? Rozważam kilka różnych podejść do rozwiązania CNF-SAT za pomocą niedeterministycznej maszyny Turinga z dwiema...
Czytałem gdzieś, że maszyna Turinga nie może tego obliczyć i dlatego jest nierozstrzygalna, ale dlaczego? Dlaczego komputer nie jest w stanie wygenerować parsowania drzewa i podjąć decyzji? Może się mylę i da się to
Niedawno miałem dyskusję na temat maszyn Turinga, kiedy zapytano mnie: „Czy maszyna Turinga pochodzi od automatów, czy jest na odwrót”? Oczywiście nie znałem odpowiedzi, ale jestem ciekawy, aby się dowiedzieć. Maszyna Turinga jest w zasadzie nieco bardziej wyrafinowaną wersją automatów Push-Down....
Jak wiadomo, istnieje wiele anomolii w maszynach Turinga z pojedynczą taśmą, gdy czas jest o(n2)o(n2)o(n^2) : symulacja wielopasmowa TM, symulacja większego alfabetu taśmy za pomocą tylko {0,1,b}{0,1,b}\{0,1,b\} , konstruowania czasu, nieszczelności twierdzenia o hierarchii czasu, ... Również...
Czy możliwe jest algorytmiczne testowanie, czy liczba obliczalna jest liczbą wymierną czy całkowitą? Innymi słowy, możliwe byłoby dla biblioteki, który implementuje numery obliczalne, aby zapewnić funkcje isIntegerlub isRational? Zgaduję, że nie jest to możliwe i że jest to w jakiś sposób związane...
Zastrzeżenie: Wiem bardzo mało o teorii złożoności. Przepraszam, ale tak naprawdę nie ma sposobu, aby zadać to pytanie bez (strasznie) zwięzłego: Jakie powinny być morfizmy w „kategorii” maszyn Turinga? Jest to oczywiście subiektywne i zależy od interpretacji teorii, więc odpowiedź na to...
Szukam konkretnej odpowiedzi na pytanie tytułowe. Czy istnieje zbiór zasad, które przekładają dowolny program na konfigurację skończonych elementów na nieskończonej planszy, tak że jeśli czarno-biały gra tylko legalne ruchy, gra kończy się w skończonym czasie, jeśli program się zatrzymuje? Zasady...
Każdy język, który nie jest kompletny w Turingu, nie może napisać dla siebie tłumacza. Nie mam pojęcia, gdzie to przeczytałem, ale widziałem, że używał go wiele razy. Wydaje się, że prowadzi to do pewnego rodzaju „ostatecznego” pełnego języka Turinga; te, które mogą tylkobyć interpretowanym przez...
Jedną z niesamowitych rzeczy w informatyce jest to, że fizyczne wdrożenie jest w pewnym sensie „nieistotne”. Ludzie z powodzeniem zbudowali komputery z kilku różnych podłoży - przekaźników, lamp próżniowych, dyskretnych tranzystorów itp. Ludzie mogą wkrótce odnieść sukces w budowie komputerów...
Biorąc pod uwagę język L zdefiniowany przez maszynę Turinga, która go decyduje, czy możliwe jest algorytmiczne określenie, czy L leży w
Z czysto abstrakcyjnego punktu widzenia rozumowania matematycznego / obliczeniowego (jak) można nawet odkryć lub wyjaśnić problemy takie jak 3-SAT, suma częściowa, podróżny sprzedawca itp.,? Czy bylibyśmy w stanie w jakikolwiek sensowny sposób uzasadnić je tylko z funkcjonalnego punktu widzenia?...
W związku z tym pytaniem przyszło mi do głowy: jaka jest złożoność czasu w przypadku maszyny Turinga z pojedynczą taśmą do obliczenia długości danych wejściowych? Mówiąc ściślej, powiedzmy, że alfabet na taśmie to , wejściem jest ciąg znaków w ( 0 + 1 ) ∗ otoczony spacjami, maszyna zaczyna się od...
Mówiąc wprost: jaka jest zgodność między maszynami Turinga z wyroczniami a rodzinami jednorodnych obwodów z wyroczniami? Jak te ostatnie są zdefiniowane w celu uzyskania tego samego modelu obliczeniowego dla danej maszyny Turinga z Oracle? To może być elementarne pytanie, ale nie jest oczywiste,...
Czy istnieje dowód, że emulacji maszyny Turinga na nieświadomej maszynie Turinga nie można wykonać w mniej niż gdzie jest liczbą kroków, które wykonuje maszyna Turinga ? Czy to tylko górna granica?O ( m logm )O(mlogm)\mathcal{O}\left(m\log m\right)mmm W artykule Paula Vitányi o relatywizowanych,...
Twierdzenie o hierarchii czasu stwierdza, że maszyny Turinga mogą rozwiązać więcej problemów, jeśli mają (wystarczająco) więcej czasu. Czy to w jakiś sposób się utrzymuje, jeśli przestrzeń jest asymptotycznie ograniczona? Jak DTISP(g(n),O(s(n)))DTISP(g(n),O(s(n)))\textrm{DTISP}(g(n), O(s(n)))...
Wiadomo, że problem zatrzymania jest niemożliwy do obliczenia. Możliwe jest jednak wykładnicze „kompresowanie” informacji o problemie zatrzymania, tak aby dekompresowanie było możliwe do obliczenia. Dokładniej, można obliczyć na podstawie opisu maszyn Turinga, a n- bitowa porada stanowi odpowiedź...
Jestem pewien, że nie jako pierwszy rozważyłem pomysł, który zamierzam przedstawić. Przydałoby się jednak znalezienie literatury związanej z tym pomysłem. Chodzi o to, aby zbudować Maszynę Turinga M z właściwością, że jeśli P = NP, wówczas M rozwiąże 3-SAT w czasie wielomianowym. (Wybór 3-SAT jest...
Zdefiniuj jako klasę języków, które mogą być akceptowane przez (wielopasmową) maszynę Turinga w czasie f ( n ) + 1 . („ + 1 ” ma jedynie na celu uproszczenie notacji i uniknięcie pomyłek.) Zauważ, że nie ma O ( ⋅ ) wokół f ( n ) + 1 .D T I M E (f( n ) )DTIME(f(n))\mathsf{DTIME}(f(n))fa( n ) +...
Czy istnieje Maszyna Turinga, która może zadecydować, czy prawie wszystkie inne Maszyny Turinga zatrzymają się? Załóżmy, że mamy jakieś wyliczenie maszyn Turinga i pewne pojęcie o „rozmiarze” zbioru liczb naturalnych, a my definiujemy:N →{ Mja}N→{Mi}\mathbb{N} \rightarrow \{M_i\}∥ ⋅∥‖⋅‖\| \cdot...