Pytania otagowane jako computability

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

8
Dlaczego możemy założyć, że algorytm może być reprezentowany jako ciąg bitowy?
Zaczynam czytać książkę o złożoności obliczeniowej i maszynach Turinga. Oto cytat: Algorytm (np. Maszyna) może być reprezentowany jako ciąg bitów, gdy zdecydujemy się na pewne kodowanie kanoniczne. To twierdzenie zostało przedstawione jako prosty fakt, ale nie rozumiem tego. Na przykład, jeśli mam algorytm, który przyjmuje jako dane wejściowe i oblicza …
3
Czy istnieje baza TM, która zatrzymuje się na wszystkich danych wejściowych, ale tej właściwości nie da się udowodnić?
Czy istnieje maszyna Turinga, która zatrzymuje się na wszystkich wejściach, ale z jakiegoś powodu ta właściwość nie jest możliwa do udowodnienia? Zastanawiam się, czy to pytanie zostało zbadane. Uwaga: „nie do udowodnienia” może oznaczać „ograniczony” system dowodowy (który w słabym sensie uważa, że ​​odpowiedź musi być twierdząca). Jestem oczywiście zainteresowany …
5
Czy interakcja ma większą moc niż algorytmy?
Słyszałem motto oddziaływanie jest silniejsze niż algorytmów z Peterem Wegner . Podstawą tego pomysłu jest to, że (klasyczna) Maszyna Turinga nie jest w stanie poradzić sobie z interakcją, to znaczy komunikacją (wejście / wyjście) ze światem zewnętrznym / środowiskiem. Jak to może być tak? Jak coś może być mocniejsze niż …
4
Czy problem grafu skończonego jest rozstrzygalny? Jakie czynniki decydują o problemie?
Chcę wiedzieć, czy można rozwiązać następujący problem i jak się dowiedzieć. W każdym problemie, który widzę, mogę powiedzieć „tak” lub „nie”, więc czy większość problemów i algorytmów można rozstrzygać, z wyjątkiem kilku (które podano tutaj )? Wejście: kierowane i skończonych wykres z i , jak wierzchołki Pytanie: Czy ścieżką w …
2
Kiedy połączenie dwóch regularnych języków jest jednoznaczne?
Biorąc pod uwagę języki i , powiedzmy, że ich konkatenacja jest jednoznaczna, jeśli dla wszystkich słów istnieje dokładnie jeden rozkład z i , a niejednoznaczny inaczej. (Nie wiem, czy istnieje ustalony termin dla tej właściwości - trudna rzecz do wyszukania!) Jako trywialny przykład konkatenacja z samym sobą jest niejednoznaczna ( …
1
Czy jest rozstrzygalne, czy automat przesuwający rozpoznaje dany regularny język?
Problem, czy dwa automaty przesuwające rozpoznają ten sam język, jest nierozstrzygalny. Problem, czy automat przesuwający rozpoznaje pusty język, jest rozstrzygalny, a zatem decydujące jest, czy rozpoznaje dany język skończony. Nie można rozstrzygnąć, czy język akceptowany przez automat pushdown jest regularny. Ale ... ... czy można zadecydować, czy automat przesuwający rozpoznaje …
1
Czy nierozwiązywalność problemu N-ciała jest równoważna problemowi zatrzymania
Nie ma ogólnego analitycznego rozwiązania problemu n-ciała, który mógłby wytworzyć funkcję analityczną, która mogłaby zostać użyta do nadania stanu układu n-ciała w dowolnej chwili t z dokładną dokładnością. Istnieją jednak pewne szczególne przypadki układów n-ciała, dla których znana jest funkcja analityczna. W podobny sposób nie ma ogólnego algorytmu, który mógłby …
1
Ciekawa przestrzeń metryczna związana z maszynami Turinga
W tym pytaniu rozważamy tylko maszyny Turinga, które zatrzymują się na wszystkich wejściach. Jeśli to przez oznaczamy maszynę Turinga, której kod tok∈Nk∈Nk \in \mathbb{N}TkTkT_kkkk . Rozważ następującą funkcję s(x,y)=min{k∣|L(Tk)∩{x,y}|=1}s(x,y)=min{k∣|L(Tk)∩{x,y}|=1}s(x,y) = \min\{k \mid |L(T_k) \cap \{x,y\}| = 1\} Innymi słowy, jest kodem najmniejszej maszyny Turinga, która rozpoznaje dokładnie jeden z ciągówMożemy …
2
Jakie języki są rozpoznawane przez maszyny z jednym licznikiem?
Maszyny liczące z dwoma lub więcej licznikami są zwykle pokazywane jako równoważne maszynom Turinga w kursach teorii teorii obliczeń. Jednak nie widziałem formalnej analizy tego, które języki mogą być rozpoznawane przez maszynę z jednym kontem. Czy te języki są równoważne z językami bezkontekstowymi (być może przez jakąś sprytną konstrukcję odnoszącą …
3
Turinga pełna i obliczeniowa moc
W wykładzie profesor wspomniał, że współczesne komputery nie mają tak dużej mocy obliczeniowej jak maszyna Turinga, ponieważ nie mają nieskończonej pamięci, a ponieważ żaden komputer nie ma nieskończonej pamięci, maszyna Turinga jest zatem nieosiągalna i po prostu reprezentuje górną granicę informatyki. Czy z tego powodu istnieje miara lub definicja tego, …
2
Dlaczego kompletność Turinga jest słuszna?
Korzystam z komputera cyfrowego, aby napisać tę wiadomość. Taka maszyna ma właściwość, która, jeśli się nad tym zastanowić, jest naprawdę niezwykła: jest to jedna maszyna, która przy odpowiednim zaprogramowaniu może wykonać dowolne możliwe obliczenia . Oczywiście kalkulatory tego rodzaju wracają do starożytności. Ludzie zbudowali maszyny, które wykonują dodawanie i odejmowanie …
5
Czy istnieją nierozstrzygalne właściwości niekompletnych automatów?
Czy istnieją nierozstrzygalne właściwości automatów z ograniczeniami liniowymi (unikanie sztuczki z pustym językiem ustawiania)? A co z deterministycznym automatem skończonym? (odłóż na bok trudność). Chciałbym uzyskać przykład (jeśli to możliwe) niezdecydowanego problemu, który jest zdefiniowany bez jawnego używania maszyn Turinga . Czy kompletność modelu Turinga jest niezbędna do obsługi problemów …
3
Czy są jakieś zbiory policzalne, których nie można wyliczyć?
Zbiór jest policzalny, jeśli ma bijectję z liczbami naturalnymi, i jest obliczalny (ce), jeśli istnieje algorytm, który wylicza jego elementy. Każdy nieskończony obliczalny zestaw wyliczalny musi być policzalny, ponieważ możemy zbudować bijection z wyliczenia. Czy są jakieś przykłady zbiorów policzalnych, których nie da się wyliczyć? Oznacza to, że istnieje bijection …
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.