Pytania dotyczące problemów, których nie może rozwiązać żadna maszyna Turinga.
Otrzymaliśmy następujące ćwiczenie. Pozwolić f(n)={100n occurs in the decimal representation of πelsef(n)={10n occurs in the decimal representation of π0else\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases}...
Widziałem już wspomniane, że systemy typów zależnych nie są wnioskami, ale można je sprawdzić. Zastanawiałem się, czy istnieje proste wyjaśnienie, dlaczego tak jest, i czy istnieje granica „zależności”, w której typy mogą być indeksowane według wartości, poniżej której możliwe jest wnioskowanie...
Podsumowanie: Zgodnie z twierdzeniem Rice'a wszystko jest niemożliwe. A jednak cały czas robię to , jak się wydaje, rzeczy niemożliwe ! Oczywiście twierdzenie Rice'a nie mówi po prostu „wszystko jest niemożliwe”. Mówi coś bardziej szczegółowego: „Każda właściwość programu komputerowego jest...
Twierdzenie Rice'a mówi nam, że jedynymi właściwościami semantycznymi Maszyn Turinga (tj. Właściwościami obliczonymi przez maszynę), o których możemy decydować, są dwie trywialne właściwości (tj. Zawsze prawdziwe i zawsze fałszywe). Ale istnieją inne właściwości Maszyn Turinga, których nie można...
Rozumiem dowód nierozstrzygalności problemu zatrzymania (podany na przykład w podręczniku Papadimitriou), oparty na przekątnej. Chociaż dowód jest przekonujący (rozumiem każdy jego krok), nie jest dla mnie intuicyjny w tym sensie, że nie widzę, jak ktoś by go wyprowadził, zaczynając od samego...
Każdy nierozstrzygnięty problem, który znam, należy do jednej z następujących kategorii: Problemy nierozstrzygalne z powodu diagonalizacji (pośrednie samodzielne odniesienie). Problemy te, podobnie jak problem zatrzymania, są nierozstrzygalne, ponieważ można użyć rzekomego decydenta dla języka do...
Najwyraźniej nie ma żadnych nierozstrzygalnych problemów w NP. Jednak według Wikipedii : NP jest zbiorem wszystkich problemów decyzyjnych, dla których przypadki, w których odpowiedź brzmi „tak”, mają […] dowody, które są] weryfikowalne w czasie wielomianowym przez deterministyczną maszynę...
Logika konstruktywistyczna to system, który usuwa Prawo Akceptowanego Środka, a także Podwójną Negację, jako aksjomaty. Jest opisany na Wikipedii tutaj i tutaj . W szczególności system nie dopuszcza dowodu sprzeczności. Zastanawiam się, czy ktoś wie, jak to wpływa na wyniki dotyczące maszyn...
Czy istnieje jakiś „naturalny” język, który jest nierozstrzygalny? przez „naturalny” rozumiem język zdefiniowany bezpośrednio przez właściwości ciągów, a nie przez maszyny i ich odpowiedniki. Innymi słowy, jeśli język wygląda jak gdzie to TM, DFA (lub regularny exp), PDA (lub gramatyka) itp., To...
Powszechnie wiadomo, że wnioskowanie typu Hindleya-Milnera (prosty typ calculus z polimorfizmem) ma rozstrzygające wnioskowanie: można zrekonstruować typy zasad dla dowolnych programów bez adnotacji.λλ\lambda Dodanie klas typu Haskell wydaje się zachowywać tę rozstrzygalność, ale dalsze dodawanie...
Rozważ problemy decyzyjne sformułowane w jakimś „rozsądnym” języku formalnym. Powiedzmy, że wzory w arytmetyce Peano wyższego rzędu z jedną wolną zmienną jako ramą odniesienia, ale równie interesują mnie inne modele obliczeń: równania diofantyczne, problemy słowne z przepisywania reguł za pomocą...
Niech . Muszę zdecydować, czy F jest rozstrzygalne, czy rekurencyjnie wyliczalne. Myślę, że jest to rozstrzygalne, ale nie wiem, jak to udowodnić.F={⟨M⟩:M is a TM which stops for every input in at most 50 steps}F={⟨M⟩:M is a TM which stops for every input in at most 50 steps}F = \{⟨M⟩:\text{M is a...
Problemu zatrzymania nie można rozwiązać w ogólnym przypadku. Można wymyślić zdefiniowane reguły, które ograniczają dozwolone dane wejściowe i czy problem zatrzymania można rozwiązać w tym szczególnym przypadku? Na przykład wydaje się prawdopodobne, że język, który nie dopuszcza na przykład pętli,...
Oprawa: wyrażenia regularne z referencjami wstecznymi język jednoargumentowy (alfabet 1-symbolowy) Czy w tym ustawieniu można rozstrzygać następujący problem: Biorąc pod uwagę wyrażenie regularne z odniesieniami wstecznymi, czy definiuje ono zwykły język? Na przykład (aa+)\1definiuje zwykły...
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...
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...
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...
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...
Mam te pytania ze starego egzaminu, który próbuję rozwiązać. Dla każdego problemu wejście jest kodowanie pewnej maszyny Turingowi .MMM Dla liczby całkowitej i następujących trzech problemów:c>1c>1c>1 Czy to prawda, że dla każdego wejścia , M nie przechodzi przez pozycję podczas...
Wiadomo, że język słów o równej liczbie 0 i 1 nie jest regularny, podczas gdy język słów o równej liczbie 001 i 100 jest regularny ( patrz tutaj ). Biorąc pod uwagę dwa słowa , czy jest rozstrzygalne, czy język słów zawierający taką samą liczbę i jest regularny?w 1 w...