Pytania otagowane jako turing-machines

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

6
Czy maszyny Turinga zakładają kiedyś coś nieskończonego?
W poprzednim pytaniu Czym dokładnie jest algorytm? , Zapytałem, czy posiadanie „algorytmu”, który zwraca wartość funkcji opartej na tablicy wstępnie obliczonych wartości, jest algorytmem. Jedną z odpowiedzi, która zwróciła moją uwagę, była ta: Przykład silni wchodzi w inny model obliczeń, zwany obliczeniami nierównomiernymi. Maszyna Turinga jest przykładem jednolitego modelu obliczeniowego: …
2
Czy funkcje logiczne Turinga są kompletne?
Funkcja boolowska jest funkcją .fa: { 0 , 1}n→ { 0 , 1 }f:{0,1}n→{0,1}f:\{0,1\}^n\rightarrow\{0,1\} Podstawa logiczna jest znana jako Turing complete, ponieważ pozwala na odwrócenie dowolnej sekwencji lub pozostawienie jej bez zmian. To samo można powiedzieć o bramkach .( ∨ , ∧ )(∨,∧)(\vee,\wedge)s ∈ { 0 , 1 }s∈{0,1}s\in\{0,1\}X O …
2
Dwustanowa maszyna Turinga do dopasowywania nawiasów
Na studiach poznawaliśmy ogólnie teorię obliczeń, a dokładniej maszyny Turinga. Jednym z wielkich wyników teoretycznych jest to, że kosztem potencjalnie dużego alfabetu (symboli) można zmniejszyć liczbę stanów do zaledwie 2. Szukałem przykładów różnych maszyn Turinga, a częstym przedstawionym przykładem jest dopasowywanie / sprawdzanie nawiasów. Zasadniczo sprawdza, czy ciąg nawiasów, np. …
2
Wariant funkcji bobra zajętego
Po przeczytaniu tego pytania „ Naturalne problemy RE nierozstrzygalne, ale nie pełne Turinga ” przyszedł mi do głowy następujący język: Jeśli jest funkcją bobra zajętego (maksymalny osiągalny wynik wśród wszystkich zatrzymujących 2-symbolowych maszyn Turinga n-stanu opisanego powyżej typu, gdy jest uruchamiany na czystej taśmie), zdefiniuj funkcję:Σ ( ⋅ )Σ(⋅)\Sigma(\cdot) B …
2
Maszyna Turinga z nieskończonym alfabetem
Czy maszyna Turinga, która może odczytywać i zapisywać symbole z nieskończonego alfabetu, ma większą moc niż zwykła TM (to jedyna różnica, maszyna wciąż ma skończoną liczbę stanów)? Intuicja mówi mi, że nie, ponieważ potrzebujesz nieskończonej liczby stanów, aby odróżnić każdy symbol. Myślę więc, że niektóre symbole lub przejścia spowodowane przez …
1
Udowodnij to
Chciałbym skorzystać z Twojej pomocy przy następującym problemie: L = { ⟨ M⟩ ∣ L ( M) jest pozbawiony kontekstu }L={⟨M⟩∣L(M) is context-free}L=\{⟨M⟩ ∣ L(M) \mbox{ is context-free} \} . Pokaż, że .L ∉ R E∪ C.o R EL∉RE∪CoREL \notin RE \cup CoRE Wiem, że aby udowodnić , wystarczy znaleźć …
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.