Pytania dotyczące problemu Halting, który decyduje o tym, czy dany program zatrzyma się na danym wejściu.
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,...
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...
Alan Turing zaproponował model maszyny (Maszyna Turinga, TM), który oblicza (liczby, funkcje itp.) I udowodnił twierdzenie Haltinga . TM to abstrakcyjna koncepcja maszyny (lub silnika, jeśli chcesz). Twierdzenie Haltinga jest wynikiem niemożliwości. Silnik Carnota (CE) to abstrakcyjna koncepcja...
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...
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...
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
Dość proste jest zrozumienie, dlaczego problem zatrzymania jest nierozstrzygalny w przypadku nieczystych programów (tj. Tych, które mają operacje we / wy i / lub stany zależne od stanu globalnego maszyny); ale intuicyjnie wydaje się, że zatrzymanie czystego programu na idealnym komputerze byłoby...
Jak czarne dziury w informatyce. Możemy tylko wiedzieć, że istnieją, ale kiedy będziemy mieli jeden z nich, nigdy nie będziemy wiedzieć, że to jeden z
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...
Oglądałem „ Pięć etapów akceptacji konstruktywnej matematyki ” Andreja Bauera i mówi on, że istnieją dwa rodzaje dowodów sprzeczności (lub dwie rzeczy, które matematycy nazywają dowodem sprzeczności): Załóżmy, że jest fałszywe ... bla bla bla, sprzeczność. Dlatego jest...
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...
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...
Z mojego rozumienia dowodu, że problemu zatrzymania nie można obliczyć, problemu tego nie da się obliczyć, ponieważ jeśli mamy program P (x), który oblicza, czy program x zatrzymuje się, czy nie, mamy paradoks, gdy P podaje się jako dane wejściowe do to samo P, mając: P (P), próbując zdecydować,...
Czy środowisko wykonawcze może wykryć nieskończone pętle, a następnie zatrzymać powiązany proces, czy też wdrożenie takiej logiki byłoby równoznaczne z rozwiązaniem problemu zatrzymania? Na potrzeby tego pytania definiuję „nieskończoną pętlę”, która oznacza serię instrukcji i powiązanych...
Podstawowa definicja maszyny Turinga (TM), przynajmniej w moim własnym podręczniku (Hopcroft + Ullman 1979), jest deterministyczna. Stąd moje własne rozumienie problemu zatrzymania dotyczy przede wszystkim deterministycznej TM, chociaż jestem świadomy, że można go rozważyć w przypadku innych...
Czy istnieje maszyna Turinga, która zatrzymuje się na wszystkich wejściach, ale z jakiegoś powodu ta właściwość nie jest możliwa do udowodnienia? Zastanawiam się, czy to pytanie zostało zbadane. Uwaga: „nie do udowodnienia” może oznaczać „ograniczony” system dowodowy (który w słabym sensie...
Istnieją relatywistyczne czasoprzestrzenie (np. Czasoprzestrzenie MH; patrz Hogarth 1994), w których linia świata o nieskończonym czasie trwania może być zawarta w przeszłości skończonego obserwatora. Oznacza to, że normalny obserwator może mieć dostęp do nieskończonej liczby kroków...
Mam problem: Pokaż, że istnieje liczba rzeczywista, dla której nie istnieje żaden program działający nieskończenie długo i zapisujący cyfry dziesiętne tej liczby. Przypuszczam, że można to rozwiązać, redukując go do problemu Halting, ale nie mam pojęcia, jak to zrobić. Byłbym wdzięczny za...
Czytałem w Wikipedii i innych tekstach, które Problem zatrzymania jest [...] rozstrzygalny dla automatów z ograniczeniami liniowymi (LBA) [i] deterministycznych maszyn ze skończoną pamięcią. Ale wcześniej napisano, że problem zatrzymania jest problemem nierozstrzygalnym, a zatem TM nie może go...
Czytałem odpowiedź na ostatnie pytanie i przyszło mi do głowy coś dziwnego, efemerycznego. Moje pytanie może zdradzić, że moim teoretycznym kotletom poważnie brakuje (głównie prawdy) lub że jest zbyt wcześnie, aby przeczytać tę stronę. Teraz, gdy wyłączenie odpowiedzialności jest na drodze...