Pytania otagowane jako turing-machines

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

6
Dlaczego maszyna Turinga jest popularnym modelem obliczeniowym?
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 podstawowe znaczenie? DFA jest elegancki - wydaje się, że dokładnie przechwytuje to, …
10
Moc obliczeniowa człowieka: czy ludzie mogą rozwiązać problem zatrzymania na maszynach Turinga?
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 tego słowa znaczeniu, zawsze możesz powiedzieć „nie”, …
1
Czy automat zwijający z dwoma stosami jest równoważny maszynie Turinga?
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 prawda, czy nie? Jaki jest dobry sposób na …
5
Co oznacza bycie kompletnym Turinga?
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 dobrze określone, czy różne systemy są Turinga kompletne, czy nie, …
7
Czy istnieje związek między problemem zatrzymania a entropią termodynamiczną?
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 silnika cieplnego, a Carnot udowodnił twierdzenie Carnota , kolejny wynik niemożliwości związany …
2
Teza Churcha-Turinga i moc obliczeniowa sieci neuronowych
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 (ustawienia są przedstawione w artykule) jest silniejsza. Autorzy twierdzą, że w …
4
Co miał na myśli Turing, mówiąc, że „maszyny nie mogą wywoływać niespodzianek” wynika z błędu?
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 konsekwencje tego faktu stają się widoczne umysł jednocześnie z nim. Jest …
2
Dlaczego jest więcej funkcji, które nie są obliczalne niż funkcje obliczalne?
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 zaakceptować, ale książka nie daje formalnego dowodu …
2
Dlaczego typ pustki C nie jest analogiczny do typu pusta / dolna?
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 określa, że ​​funkcja …
28 type-theory  c  logic  modal-logic  coq  equality  coinduction  artificial-intelligence  computer-architecture  compilers  asymptotics  formal-languages  asymptotics  landau-notation  asymptotics  turing-machines  optimization  decision-problem  rice-theorem  algorithms  arithmetic  floating-point  automata  finite-automata  data-structures  search-trees  balanced-search-trees  complexity-theory  asymptotics  amortized-analysis  complexity-theory  graphs  np-complete  reductions  np-hard  algorithms  string-metrics  computability  artificial-intelligence  halting-problem  turing-machines  computation-models  graph-theory  terminology  complexity-theory  decision-problem  polynomial-time  algorithms  algorithm-analysis  optimization  runtime-analysis  loops  turing-machines  computation-models  recurrence-relation  master-theorem  complexity-theory  asymptotics  parallel-computing  landau-notation  terminology  optimization  decision-problem  complexity-theory  polynomial-time  counting  coding-theory  permutations  encoding-scheme  error-correcting-codes  machine-learning  natural-language-processing  algorithms  graphs  social-networks  network-analysis  relational-algebra  constraint-satisfaction  polymorphisms  algorithms  graphs  trees 
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.