Pytania oznaczone «turing-machines»

Jestem studentem CS. Rozumiem, jak Turing wymyślił swoją abstrakcyjną maszynę (modelującą osobę wykonującą obliczenia), ale wydaje mi się to niewygodną, ​​nieelegacyjną abstrakcją. Dlaczego uważamy „taśmę” i maszynę piszącą symbole, zmieniającą stan, przesuwającą taśmę tam iz powrotem? Jakie jest...

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ż...

Zgadzam się, że maszyna Turinga może „rozwiązać wszystkie możliwe problemy matematyczne”. Jest tak, ponieważ jest to tylko reprezentacja algorytmu na maszynie: najpierw zrób to, a następnie zrób to, a na końcu wyślij to. Chodzi mi o to, że wszystko, co można rozwiązać, może być reprezentowane...

W obliczeniach kwantowych jaki jest równoważny model maszyny Turinga? Jest dla mnie całkiem jasne, w jaki sposób można zbudować obwody kwantowe z bram kwantowych, ale jak możemy zdefiniować kwantową maszynę Turinga (QTM), która może faktycznie korzystać z efektów kwantowych, a mianowicie działać na...

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...

Czy są jakieś teoretyczne maszyny, które przekraczają możliwości maszyn Turinga w przynajmniej niektórych

Widzę, że większość definicji tego, co ma być Turing-zupełne, jest do pewnego stopnia tautologiczna. Na przykład, jeśli Google „co oznacza bycie kompletnym Turinga”, otrzymuje: Komputer jest kompletny, jeśli może rozwiązać każdy problem, który maszyna Turinga może ... Chociaż jest bardzo...

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...

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,...

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...

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...

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...

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 /...

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

Robię prezentację na temat maszyn Turinga i chciałem przedstawić trochę informacji na temat FSM przed wprowadzeniem maszyn Turinga. Problem w tym, że tak naprawdę nie wiem, co BARDZO różni się od siebie. Oto, co wiem, że jest inaczej: FSM ma sekwencyjne stany w zależności od spełnienia...

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...

Biorąc pod uwagę tylko alfabet , ciągi, które można podać jako dane wejściowe do maszyn Turinga, pochodzą ze zbioru Σ ∗ . Ale czy ma sens, aby dane wejściowe były nieskończonym ciągiem binarnym? Na przykład, jeśli maszyna Turinga akceptuje wszystkie ciągi zaczynające się od 0, to czy ciąg binarny...

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...