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...
Obecnie czytam książkę o algorytmach i złożoności. W tej chwili czytam o funkcjach obliczalnych i niepoliczalnych, a moja książka stwierdza, że jest o wiele więcej funkcji, które nie są obliczalne niż obliczalne, w rzeczywistości większość jest niepoliczalna. W pewnym sensie intuicyjnie mogę to...
Natknąłem poniżej rachunku przez Alana M. Turinga tutaj : „Pogląd, że maszyny nie mogą wywoływać niespodzianek, jest, jak sądzę, spowodowany błędem, któremu szczególnie podoba się filozofów i matematyków. Jest to założenie, że jak tylko fakt zostanie przedstawiony umysłowi, wszystkie...
Dowiedzieliśmy się o koncepcji wyliczenia funkcji. W praktyce odpowiadają one językom programowania. W pewnej uwadze profesor wspomniał, że klasa wszystkich całkowitych funkcji (tj. Funkcji, które zawsze kończą się dla każdego wejścia) nie jest wyliczalna. Oznaczałoby to, że nie możemy opracować...
Teza Church-Turinga stwierdza, że wszystko, co można fizycznie obliczyć, można obliczyć na maszynie Turinga. Artykuł „Obliczenia analogowe przez sieci neuronowe” (Siegelmannn i Sontag, Theoretical Computer Science , 131: 331–360, 1994; PDF ) twierdzi, że sieć neuronowa o określonej formie...
Wikipedia, jak również inne źródła, które znalazłem, wskazują voidtyp C jako typ jednostki, a nie typ pusty. Uważam to za mylące, ponieważ wydaje mi się, że voidlepiej pasuje do definicji typu pustego / dolnego. voidO ile wiem, nie zamieszkują żadnych wartości . Funkcja z typem zwracanym void...
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...
Czy istnieją programy, które potrafią „tłumaczyć” kod źródłowy między dowolnymi dwoma językami (zakładając, że tłumacz ma dostęp do wymaganych bibliotek)? Jeśli tak, to w jaki sposób działają (zastosowane techniki, wymagana wiedza itp.)? Jak można by je wykonalnie skonstruować? Jeśli nie są,...
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....
Problem zatrzymania mówi, że nie ma algorytmu, który określi, czy dany program się zatrzyma. W rezultacie powinny istnieć programy, o których nie możemy powiedzieć, czy się kończą, czy nie. Jakie są najprostsze (najmniejsze) znane przykłady takich
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...
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ę...
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...
To pytanie zostało przeniesione z Teoretycznej wymiany stosów komputerowych, ponieważ można na nie odpowiedzieć w ramach wymiany stosów komputerowych. Migrował 6 lat temu . Natknąłem się na wiele definicji języków rekurencyjnych i rekurencyjnie wyliczalnych. Ale nie...
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?...
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...
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...
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...
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...
Maszyna Turinga, która powróci do wcześniej napotkanego stanu z głowicą do odczytu / zapisu w tej samej komórce dokładnie tej samej taśmy, zostanie przechwycona w pętli. Taka maszyna się nie zatrzymuje. Czy ktoś może podać przykład ciągłej maszyny, która się nie...