Pytania otagowane jako computability

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

4
Czyste, intuicyjne wyprowadzenie kombinatora stałoprzecinkowego (kombinator Y)?
Kombinator stałoprzecinkowy FIX (znany również jako kombinator Y) w (niepoprawnym) rachunku lambda ( ) jest zdefiniowany jako:λλ\lambda FIX≜λf.(λx.f (λy.x x y)) (λx.f (λy.x x y))≜λf.(λx.f (λy.x x y)) (λx.f (λy.x x y))\triangleq \lambda f.(\lambda x. f~(\lambda y. x~x~y))~(\lambda x. f~(\lambda y. x~x~y)) Rozumiem jego cel i doskonale mogę śledzić wykonanie …
7
Czy wszystkie języki są kompletne wymienne?
Uwaga: chociaż umiem programować, jestem całkiem początkującym w teorii CS. Zgodnie z tą odpowiedzią Kompletność Turinga jest abstrakcyjną koncepcją obliczalności. Jeśli język jest kompletny Turinga, jest on w stanie wykonać dowolne obliczenia, które może wykonać każdy inny kompletny język Turinga. I każdy program napisany w dowolnym języku kompletne Turinga mogą …
4
Dowód nierozstrzygalności problemu zatrzymania
Mam problem ze zrozumieniem dowodu nierozstrzygalności problemu zatrzymania. Jeśli zwraca, czy program a zatrzymuje się na wejściu b , dlaczego musimy przekazać kod P zarówno dla a, jak i b ?H.( a , b )H(a,b)H(a,b)zaaabbbP.PPzaaabbb Dlaczego nie możemy karmić z P i jakimś arbitralnym wejściowego, powiedzmy, X ?H.( )H()H()P.PPxxx
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 zajęty bóbr to najszybciej rosnąca funkcja znana człowiekowi?
To pytanie zostało przeniesione z Teoretycznej wymiany stosów komputerowych, ponieważ można na nie odpowiedzieć w ramach wymiany stosów komputerowych. Migrował 7 lat temu . Właśnie miałem to interesujące pytanie. Jaka jest najszybciej rosnąca funkcja znana człowiekowi? Czy to zajęty bóbr ? Znamy funkcje takie jak x2)x2)x^2 , ale ta funkcja …
4
Dlaczego funkcje obliczalne nazywane są również funkcjami rekurencyjnymi?
W teorii obliczalności funkcje obliczeniowe nazywane są również funkcjami rekurencyjnymi. Przynajmniej na pierwszy rzut oka nie mają one nic wspólnego z tym, co nazywasz „rekurencyjnym” w codziennym programowaniu (tj. Funkcjami, które same się nazywają). Jakie jest rzeczywiste znaczenie rekurencji w kontekście obliczalności? Dlaczego te funkcje nazywane są „rekurencyjnymi”? Innymi słowy: …
6
Algorytm rozwiązywania „problemu zatrzymania” Turinga
To pytanie zostało przeniesione z Teoretycznej informatyki stosu wymiany, ponieważ można na nie odpowiedzieć w sprawie informatyki stosu wymiany. Migrował 7 lat temu . „Alan Turing udowodnił w 1936 r., Że nie może istnieć ogólny algorytm rozwiązania problemu zatrzymania dla wszystkich możliwych par danych wejściowych programu” Czy mogę znaleźć ogólny …
5
Dlaczego języki funkcjonalne Turing są kompletne?
Być może moje ograniczone rozumienie tematu jest nieprawidłowe, ale rozumiem do tej pory: Programowanie funkcjonalne oparte jest na rachunku Lambda Calculus opracowanym przez Alonzo Church. Programowanie imperatywne oparte jest na modelu maszyny Turinga, stworzonym przez Alana Turinga, ucznia Churcha. Rachunek Lambda jest tak potężny i zdolny jak Maszyna Turinga, co …
3
Przybliżenie złożoności Kołmogorowa
Studiowałem coś na temat złożoności Kołmogorowa , przeczytałem kilka artykułów i książek Vitanyi i Li i wykorzystałem koncepcję znormalizowanej odległości kompresji, aby zweryfikować stilometrię autorów (określić, w jaki sposób każdy autor pisze niektóre dokumenty tekstowe i grupowe według ich podobieństwa). W takim przypadku zastosowano kompresory danych w celu przybliżenia złożoności …
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 = …
5
Czy problem zatrzymania można „rozwiązać”, przechodząc do opisu obliczeń wyższego poziomu?
Niedawno usłyszałem ciekawą analogię, która stwierdza, że ​​dowód Turinga na nierozstrzygalność problemu zatrzymania jest bardzo podobny do paradoksu fryzjerskiego Russella. Zastanawiałem się więc: matematycy w końcu zdołali ujednolicić teorię zbiorów, przechodząc od naiwnego sformułowania pola przez Cantora do bardziej złożonego systemu aksjomatów (teoria zbiorów ZFC), dokonując po drodze istotnych wyłączeń …
1
Maszyny dla języków bezkontekstowych, które nie zyskują dodatkowej mocy z niedeterminizmu
Rozważając modele maszynowe obliczeń, hierarchię Chomsky'ego zazwyczaj charakteryzuje (w kolejności), automat skończony, automat push-down, automat liniowo związany i maszyny Turinga. W przypadku pierwszego i ostatniego poziomu 1 (języki zwykłe i języki z wyliczaniem rekurencyjnym) nie ma różnicy w sile modelu, czy rozważamy maszyny deterministyczne czy niedeterministyczne, tj. DFA są równoważne …
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.