Pytania otagowane jako undecidability

Pytania dotyczące problemów, których nie może rozwiązać żadna maszyna Turinga.

3
Jak można rozstrzygać, czy ma pewną sekwencję cyfr?
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} Wykazać, że jest obliczalne.fff Jak to jest możliwe? O ile mi …
1
Co sprawia, że ​​wnioskowanie o typach dla typów zależnych jest nierozstrzygalne?
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 typu, a powyżej której nie jest?
2
Zakłopotany twierdzeniem Rice'a
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 niepoliczalna”. (Jeśli chcesz podzielić włosy, każdą właściwość „nietrywialną”. To znaczy …
1
Twierdzenie Rice'a o właściwościach nie semantycznych
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 rozstrzygać. Na przykład właściwość, że istnieje stan nieosiągalny w danej maszynie Turinga, …
7
Czy istnieje bardziej intuicyjny dowód nierozstrzygalności problemu zatrzymania niż przekątna?
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 problemu. W książce dowód wygląda następująco: „załóżmy, że MHMHM_H …
2
Czy są jakieś szczególne problemy, o których wiadomo, że są nierozstrzygalne z powodów innych niż przekątna, samodzielne odniesienie lub redukowalność?
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 zbudowania bazy TM, której zachowanie prowadzi do sprzeczności. Możesz także wrzucić do tego obozu wiele …
5
Dlaczego nie jest to nierozstrzygalny problem w NP?
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ę Turinga. [...] Mówi się, że problem występuje w NP wtedy i tylko …
4
Czy w logice konstruktywistycznej istnieją niezdecydowane języki?
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 Turinga i języków formalnych? Zauważam, że prawie każdy …
1
Jakie są najsilniejsze znane typy systemów, dla których można wnioskować?
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 sprawia, że ​​wnioskowanie bez adnotacji jest nierozstrzygalne (rodziny typów, GADT, typy zależne, typy Rank-N, System …
2
Czy istnieje „naturalny” nierozstrzygalny język?
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 nie jest naturalne. Jednak jest naturalne.L={⟨M⟩∣…}L={⟨M⟩∣…} L = …
1
Współczynnik rozstrzygalnych problemów
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ą maszyn Turinga itp. Odpowiedź wyrażona w dowolnym klasyczna formalizacja byłaby …
5
Czy można rozwiązać problem zatrzymania, jeśli masz ograniczony lub przewidywalny wkład?
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, bardzo łatwo będzie stwierdzić, czy program się zatrzyma, czy nie. …
1
Wyrażenia regularne z odniesieniami wstecznymi do jednoznacznego alfabetu
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 język, podczas gdy (aa+)\1+nie. Czy możemy zdecydować, który jest właściwy? Dla konkretności, „wyrażenia regularne z …
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.