Pytania otagowane jako computability

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

12
Dlaczego tak naprawdę problem zatrzymania jest tak ważny?
Nie rozumiem, dlaczego problem zatrzymania jest tak często wykorzystywany do odrzucenia możliwości ustalenia, czy program się zatrzymuje. Wikipedia [artykuł] [1] poprawnie wyjaśnia, że ​​deterministyczna maszyna ze skończoną pamięcią zatrzyma lub powtórzy poprzedni stan. Możesz użyć algorytmu, który wykrywa, czy lista połączona zapętla się w celu zaimplementowania funkcji zatrzymania o złożoności …
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 …
5
Czy istnieje jakikolwiek konkretny związek między twierdzeniem o niekompletności Gödla, problemem zatrzymania a uniwersalnymi maszynami Turinga?
Zawsze myślałem niejasno, że odpowiedź na powyższe pytanie była twierdząca w następujący sposób. Twierdzenie Gödela o niekompletności i nierozstrzygalność problemu zatrzymania są zarówno negatywnymi wynikami rozstrzygalności, jak i ustalonymi na podstawie przekątnych argumentów (w latach 30. XX wieku), więc muszą być jakoś dwoma sposobami spojrzenia na te same sprawy. Pomyślałem, …
10
Moc obliczeniowa człowieka: czy ludzie mogą rozwiązać problem zatrzymania na maszynach Turinga?
Wiemy, że problem zatrzymania (na maszynach Turinga) jest nierozstrzygalny dla maszyn Turinga. Czy są jakieś badania nad tym, jak dobrze ludzki umysł może poradzić sobie z tym problemem, być może wspomagane przez maszyny Turinga lub komputery ogólnego przeznaczenia? Uwaga : Oczywiście, w ścisłym tego słowa znaczeniu, zawsze możesz powiedzieć „nie”, …
3
Dlaczego ludzie mogą rozwiązać niektóre „nierozstrzygalne” problemy?
Dopasowywanie wzorca wysokiego rzędu jest nierozstrzygalnym problemem. Oznacza to, że nie ma algorytmu, który, biorąc pod uwagę równanie a => b, gdzie ai bsą otwartymi terminami na prostym typie rachunku lambda, znalazłby podstawienie Stakie, że aS => bSgdzie =>skrót oznacza „ma tę samą postać normalną Bn”. Jednak ludzie mogą skutecznie …
9
Dlaczego niektóre języki programowania Turing są kompletne, ale brakuje im umiejętności innych języków?
Napotkałem dziwny problem podczas pisania interpretera, który (powinien) zaczepia się o zewnętrzne programy / funkcje: Funkcje w „C” i „C ++” nie mogą przechwytywać funkcji variadic , np. Nie mogę utworzyć funkcji, która wywoła „printf” z dokładnie tymi samymi argumentami, które otrzymał, i zamiast tego musi wywołać alternatywną wersję, która …
5
Iteracja może zastąpić rekurencję?
Widziałem przepełnienie całego stosu, np. Tutaj , tutaj , tutaj , tutaj , tutaj i kilku innych, których nie chcę wspominać, że „każdy program, który korzysta z rekurencji, można przekonwertować na program wykorzystujący tylko iterację”. Był nawet wysoko oceniany wątek z bardzo pozytywną odpowiedzią, która powiedziała, że ​​tak, to możliwe. …
1
Czy automat zwijający z dwoma stosami jest równoważny maszynie Turinga?
W tej odpowiedzi wspomniano o tym Skończony automat może rozpoznać zwykły język. Język bezkontekstowy wymaga stosu, a język kontekstowy wymaga dwóch stosów (co jest równoważne z twierdzeniem, że wymaga pełnej maszyny Turinga) . Chciałem wiedzieć o prawdzie odważnej części powyżej. Czy to prawda, czy nie? Jaki jest dobry sposób na …
4
Jakie są typowe techniki wzajemnego ograniczania problemów?
W teorii obliczalności i złożoności (i być może w innych dziedzinach) redukcje są wszechobecne. Istnieje wiele rodzajów, ale zasada pozostaje ta sama: pokaż, że jeden problem jest co najmniej tak samo trudny jak jakiś inny problem poprzez odwzorowanie instancji z na równoważne z rozwiązaniem w . Zasadniczo pokazujemy, że każdy …
9
Czy C faktycznie Turinga jest kompletny?
Próbowałem wyjaśnić komuś, że C jest kompletne w Turinga, i zdałem sobie sprawę, że tak naprawdę nie wiem, czy w rzeczywistości jest to kompletny Turing. (C jak w semantyce abstrakcyjnej, a nie jak w rzeczywistej implementacji). „Oczywista” odpowiedź (z grubsza: może zająć się dowolną ilością pamięci, więc może emulować maszynę …
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 …
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.