Pytania otagowane jako computability

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

5
Czym dokładnie jest obliczenie?
Wiem, czym jest obliczenie w jakimś niejasnym sensie (tak robią komputery), ale chciałbym bardziej rygorystyczną definicję. Dictionary.comDefinicje obliczeń, obliczeń, obliczeń i obliczeń są okrągłe, więc to nie pomaga. Wikipediadefiniuje obliczenia jako „każdy rodzaj obliczeń zgodny z dobrze zdefiniowanym modelem”. Definiuje obliczenia jako „zamierzony proces, który przekształca jeden lub więcej danych …
1
Czy istnieją w pełni optymalizujące kompilatory do kończenia programów?
W książce Andrew W. Appela, Modern Compiler Implementation in ML , mówi w rozdziale 17, że teoria obliczalności pokazuje, że zawsze będzie możliwe wynalezienie nowych transformacji optymalizacyjnych i udowadnia, że ​​w pełni optymalizujący kompilator rozwiąże problem zatrzymania: Program Q, który nie wytwarza mocy wyjściowej i nigdy nie zatrzymuje się, można …
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 …
1
Równoważność definicji złożoności Kołmogorowa
Istnieje wiele sposobów definiowania złożoności Kołmogorowa i zwykle wszystkie te definicje są równoważne do stałej addytywnej. To znaczy, jeśli K1K1K_1 i K2K2K_2 są funkcjami złożoności Kołmogorowa (zdefiniowanymi za pomocą różnych języków lub modeli), wówczas istnieje stała ccc taka, że ​​dla każdego łańcucha xxx , |K1(x)−K2(x)|&lt;c|K1(x)−K2(x)|&lt;c|K_1(x) - K_2(x)| < c . …
4
Strategie utknięcia w zrozumieniu TCS
Jestem studentem kończącym kurs teorii teorii i mam poważne problemy z tworzeniem treści, gdy tylko o to poproszę. Potrafię śledzić podręcznik (Wstęp do teorii obliczeń Michaela Sipsera) i wykłady; jednak kiedy poproszono mnie o udowodnienie czegoś lub sformułowanie formalnego opisu konkretnej bazy TM, po prostu dusiłem się. Co mogę zrobić …
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
Czy funkcja obliczalna może zbiegać się w liczbę nieobliczalną?
Czy istnieje funkcja obliczalna taka, że:f:N→Qf:N→Qf:\mathbb{N}\rightarrow \mathbb{Q} Dla wszystkicht∈N:0≤f(t)&lt;Xt∈N:0≤f(t)&lt;Xt\in\mathbb{N}: 0\le f(t) < X limt→∞f(t)=Xlimt→∞f(t)=X\lim\limits_{t\rightarrow\infty} f(t) = X Gdzie XXX jest nieobliczalną liczbą rzeczywistą. Jedyne odniesienie do tego pytania, które znalazłem, to odpowiedź na to pytanie : /math//a/1052579/168764 , gdzie wydaje się, że funkcja się utrzyma, ale nie mam pojęcia, jak …
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 …
2
W jakim sensie zestaw Mandelbrota jest „obliczalny”?
Zestaw Mandelbrota to piękne stworzenie w matematyce. Istnieje wiele pięknych obrazów tego zestawu stworzonych z dużą precyzją, więc oczywiście ten zestaw jest w pewnym sensie „obliczalny”. Jednak niepokoi mnie fakt, że nie można go nawet wyliczyć rekurencyjnie - po prostu dlatego, że zbiór jest niepoliczalny. Można to rozwiązać, wymagając pewnego …
7
Czy komputer bez pamięci RAM, ale z dyskiem, odpowiada komputerowi z pamięcią RAM?
Jak rozumiem, pamięć jest wykorzystywana do wielu rzeczy. Służy jako pamięć podręczna dysku i zawiera instrukcje programów oraz ich stos i stos. Oto eksperyment myślowy. Jeśli ktoś nie dba o szybkość lub czas, jaki zajmuje komputerowi wykonanie chrupnięcia, jaka jest minimalna ilość pamięci, jaką można mieć, zakładając, że ma on …
4
Jak sprawdzić, czy dwa algorytmy zwracają ten sam wynik dla dowolnego wejścia?
Jak sprawdzisz, czy dwa algorytmy (powiedzmy: Sortuj i Naiwne) zwracają ten sam wynik dla dowolnego wejścia, gdy zestaw wszystkich danych wejściowych jest nieskończony? Aktualizacja: Dziękuję Ben za opisanie, w jaki sposób niemożliwe jest algorytmiczne wykonanie tego przypadku w ogólnym przypadku. Odpowiedź Dave'a jest doskonałym podsumowaniem metod algorytmicznych i ręcznych (w …
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.