Pytania otagowane jako turing-machines

Pytania o maszyny Turinga, teoretyczny model obliczeń mechanicznych zdolny do symulacji dowolnego programu komputerowego.

6
Czy istnieje fizyczna analogia do maszyny Turinga?
Ostatnio w mojej klasie CS zapoznałem się z Maszyną Turinga. Po zajęciach spędziłem ponad 2 godziny, próbując dowiedzieć się, jaki jest związek między taśmą a maszyną. Byłem całkowicie nieświadomy istnienia taśm komputerowych lub tego, jak taśmy i maszyny współdziałały do ​​dziś. Nadal nie rozumiem, dlaczego maszyna odczytuje taśmy, ale skaner …
5
Praktyczne znaczenie maszyn Turinga?
Jestem inżynierem elektrykiem i 26 lat temu miałem tylko jeden kurs CS na studiach. Jednak jestem również oddanym użytkownikiem Mathematica. Mam wrażenie, że maszyny Turinga są bardzo ważne w informatyce. Czy znaczenie ma tylko w teorii informatyki? Jeśli istnieją praktyczne implikacje / zastosowania, jakie są niektóre z nich?
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
4
Czy w logice konstruktywistycznej istnieją niezdecydowane języki?
Logika konstruktywistyczna to system, który usuwa Prawo Akceptowanego Środka, a także Podwójną Negację, jako aksjomaty. Jest opisany na Wikipedii tutaj i tutaj . W szczególności system nie dopuszcza dowodu sprzeczności. Zastanawiam się, czy ktoś wie, jak to wpływa na wyniki dotyczące maszyn Turinga i języków formalnych? Zauważam, że prawie każdy …
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 …
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ń …
2
Problemy, które prawdopodobnie wymagają czasu kwadratowego
Szukam przykładów problemu, który ma dolną granicę ) dla wejścia .Ω(|x|2Ω(|x|2\Omega(|x|^2xxx Problem musi mieć następujące właściwości: Ω(n2)Ω(n2)\Omega(n^2) Środowisko wykonawcze dla dowolnego algorytmu - priorytetem jest możliwie najprostszy argument dolnej granicy. O(n2)O(n2)O(n^2)Algorytm , jeśli to możliwe, również prosty. Rozmiar wyjściowy (lub mniejszy). Oczywiście każdy problem, który wymaga wydłużonego wyjścia wymagał co …
1
Jak przekonwertować maszynę Turinga rozpoznającą język na nieograniczoną gramatykę?
Zgodnie z tym artykułem Wikipedii , nieograniczone gramatyki są równoważne maszynom Turinga. Artykuł zauważa, że ​​mogę przekonwertować dowolną maszynę Turinga na nieograniczoną gramatykę, ale pokazuje ona tylko, jak przekonwertować gramatykę na maszynę Turinga. Jak rzeczywiście to zrobić i przekonwertować maszynę Turinga rozpoznającą język na nieograniczoną gramatykę? Próbowałem zastąpić reguły przejścia …
4
Zdefiniowanie problemu zatrzymania dla niedeterministycznych automatów
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 rodzajów automatów. Zauważyłem również, że determinizm jest często mniej lub bardziej dorozumiany w …
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.