Pytania otagowane jako turing-machines

Maszyna Turinga to podstawowy model obliczeń, szczególnie w pracy teoretycznej.

2
(Jak) Czy możemy odkryć / przeanalizować problemy NP przy braku modelu obliczeniowego Turinga?
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? Czy to w ogóle możliwe? Zastanawiam się nad tym pytaniem wyłącznie …
2
Emulacja Oblivious Turing Machine w dolnej granicy
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(mlog⁡m)\mathcal{O}\left(m\log m\right)mmm W artykule Paula Vitányi o relatywizowanych, nieświadomych maszynach Turinga, twierdzi Vitányi „Oni [ Pippenger …
1
Jak dobry może być detektor zatrzymania?
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 \| fa( i ) = ∥ { n : Mja nie …
1
Kompresowanie informacji o problemie zatrzymania w maszynach wyroczni Turinga
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ź na problem zatrzymania dla wszystkich 2 n - 1 maszyn Turinga, przy …
1
Hierarchie czasu w DSPACE (O (s)))
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))) odnosi się do DTISP(f(n),O(s(n)))DTISP(f(n),O(s(n)))\textrm{DTISP}(f(n), O(s(n))) jeśli fgfg\frac{f}{g} rośnie wystarczająco szybko? Ja szczególnie zainteresowany w przypadku, s(n)=ns(n)=ns(n) = n …
2
Poszukuję źródła literatury do naśladowania
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 arbitralny. To może być naprawdę …
1
Czy
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 …
3
Czy istnieją niekonstruktywne dowody na istnienie „małych” maszyn Turinga / NFA?
Po przeczytaniu powiązanego pytania dotyczącego niekonstruktywnych dowodów istnienia algorytmów, zastanawiałem się, czy istnieją metody pokazania istnienia „małych” (powiedzmy, stanowych) maszyn obliczeniowych bez ich budowania. Formalnie: załóżmy, że otrzymaliśmy język i naprawiliśmy jakiś model obliczeniowy (NFA / maszyna Turinga itp.).L ⊆ Σ∗L⊆Σ∗L\subseteq \Sigma^* Czy istnieją jakieś niekonstruktywne wyniki istnienia pokazujące, że …
6
Mały język podobny do C, który mogą symulować maszyny Turinga
Szukam małego języka, który pomoże „przekonać” studentów, że maszyny Turinga są wystarczająco ogólnym modelem obliczeniowym. To znaczy język, który wygląda jak języki, do których są przyzwyczajeni, ale można go również łatwo symulować na maszynie Turinga. Papadimitriou używa do tego zadania maszyn RAM, ale obawiam się, że porównanie czegoś dziwnego (jako …
3
Czy P zawiera niezrozumiałe języki? (Wiki społeczności TCS)
Odpowiedź: nieznana Ogromne podziękowania dla wszystkich, którzy pomogli dopracować to pytanie i związane z nim definicje. Definicje tej wiki stanowiły punkt wyjścia dla najnowszej wiki TCS „ Czy P zawiera języki, których istnienie jest niezależne od PA lub ZFC? (Wiki społeczności TCS) ”. Preferowana jest nowsza wiki, ponieważ jej definicje …
1
Czy uczeń Alana Turinga, Robin Gandy, stwierdził, że Charles Babbage nie ma pojęcia o uniwersalnej maszynie komputerowej?
Robin Gandy był uczniem Alana Turinga . Gandy przeprowadził analizę silnika analitycznego Babbage'a (patrz „Gandy - zbieżność pomysłów w 1936 r.” Cytowany w „Herken, Rolf - Uniwersalna maszyna Turinga - badanie półwiecze. Springer Verlag”) - i powiedział, że tak (por. s. 52–53): Funkcje arytmetyczne +, -, ×, gdzie - oznacza …
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.