Pytania otagowane jako computability

Pytania związane z teorią obliczalności, czyli teorią rekurencji

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 …
1
Unikalne nachylenie kwadratów
Chcemy kafelki m×mm×mm\times m-kwadrat przy użyciu dwóch rodzajów kafelków: 1×11×11 \times 1- kwadratowa płytka i 2×22×22 \times 2- kwadratowy kafelek, tak aby każdy leżący pod nim kwadrat był przykryty bez nakładania się. Zdefiniujmy funkcjęf(n)f(n)f(n) co daje rozmiar największego, unikalnego, możliwego do uprawy kwadratu nnn 1×11×11\times 1- kwadraty i dowolna liczba …
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źć …
2
Rozstrzygalność języka przedrostka
W połowie kadencji istniała odmiana następującego pytania: Dla rozstrzygalnego zdefiniuj Pokaż, że niekoniecznie jest rozstrzygalny.LLLPref(L)={x∣∃y s.t. xy∈L}Pref(L)={x∣∃y s.t. xy∈L}\text{Pref}(L) = \{ x \mid \exists y \text{ s.t. } xy \in L\}Pref(L)Pref(L)\text{Pref}(L) Ale jeśli wybiorę to myślę, że jest również , a zatem jest rozstrzygalne. Również daje ten sam wynik. A …
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.