Pytania związane z teorią obliczalności, czyli teorią rekurencji
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,...
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}...
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...
Czy istnieje zestaw konstrukcji języka programowania w języku programowania, aby można go uznać za ukończony jako Turing? Z tego, co mogę powiedzieć z wikipedii , język musi obsługiwać rekursję lub, pozornie, musi być w stanie działać bez zatrzymywania się. Czy to już...
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ą...
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...
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ą...
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...
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 ....
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ą...
Czy są jakieś teoretyczne maszyny, które przekraczają możliwości maszyn Turinga w przynajmniej niektórych
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...
Wiem, że Idris ma typy zależne, ale nie jest kompletny. Czego nie może zrobić, rezygnując z kompletności Turinga i czy wiąże się to z posiadaniem typów zależnych? Wydaje mi się, że jest to dość specyficzne pytanie, ale nie wiem zbyt wiele o typach zależnych i pokrewnych systemach...
Widząc, że w hierarchii Chomsky'ego języki Type 3 mogą być rozpoznawane przez maszynę stanową bez pamięci zewnętrznej (tj. Skończonego automatu), Type 2 przez maszynę stanową z pojedynczym stosem (tj. Automat push-down) i typ 0 przez automat stanowy z dwoma stosami (lub równoważnie taśmą, jak w...
Ten 579-bitowy program w Binary Lambda Calculus ma nieznany status
Planuję uczyć kurs zimowy na różną liczbę tematów, z których jednym będą kompilatory. Teraz natknąłem się na ten problem, myśląc o zadaniach do wykonania przez cały kwartał, ale to mnie zaskoczyło, więc mogę go użyć jako przykładu. public class DeadCode { public static void main(String[] args) {...
Czy istnieją jakieś pełne kalkulacje lambda na maszynie Turinga? Jeśli tak, jakie są
Zastanawiam się, czy istnieje dobry przykład łatwego do zrozumienia problemu NP-Hard, który nie jest NP-Complete i nie jest nierozstrzygalny? Na przykład problem zatrzymania jest NP-trudny, a nie NP-kompletny, ale jest nierozstrzygalny. Uważam, że oznacza to, że problem można zweryfikować, ale...
Rozmawiałem o tym, jak zdefiniować kwantowe maszyny Turinga? i czuję, że kwantowa TM i niedetermistyczna TM są jednym i tym samym. Odpowiedzi na inne pytanie nie dotyczą tego. Czy te dwa modele są takie same? Jeśli nie, Jakie są różnice między Quantum TM i NDTM? Czy jest jakieś obliczenie,...
Twierdzenie Rice'a mówi nam, że jedynymi właściwościami semantycznymi Maszyn Turinga (tj. Właściwościami obliczonymi przez maszynę), o których możemy decydować, są dwie trywialne właściwości (tj. Zawsze prawdziwe i zawsze fałszywe). Ale istnieją inne właściwości Maszyn Turinga, których nie można...