A Turing-gépek hasonlóak a véges automatákhoz/véges állapotú gépekhez, de megvan a korlátlan memória előnye … Képesek szimulálni az általános számítógépeket; egy olyan probléma, amelyet egy általános számítógép meg tud oldani (elegendő memóriával), szintén megoldható Turing-gép segítségével, és fordítva.
Mi a különbség a RAM és a TM között?
Egy Turing-gép nem tud Egy RAM-gép képes számolni az O(1)-ben (bizonyos korlátozások mellett). Egy Turing-gép nem tud. A Turing-gépek polinomiálisan szimulálják a RAM-gépeket, azaz valamilyen c állandó esetén bármely O(nk) időben futó RAM-gép szimulálható egy O(nck) időben futó Turing-géppel.
A Turing-gép szalagja határtalan?
A Turing-gép (TM) egy állapotgép, amely két memóriából áll: egy korlátlan szalagból és egy véges állapotvezérlő táblából. A szalag az adatokat szimbólumként tárolja. A gépnek nagyon kicsi a megfelelő műveletsora, összesen 6 (olvasás, írás, balra, jobbra, állapotváltás, leállítás) a szalagon.
Miért erős a Turing-gép?
Mennyire erősek a Turing-gépek? A Turing-gépek bármilyen reguláris vagy környezetfüggetlen nyelvet képesek elfogadni. A Turing-gépek alapvető aritmetikai számításokat hajthatnak végre … A Turing tézise kimondja, hogy bármilyen „mechanikai eszközökkel” végrehajtható számítás elvégezhető Turing-géppel (a hatékonysági kérdések figyelmen kívül hagyásával).
A Turing-gépek örökre hurkolhatnak?
turing(turingDescrip) nem tud megállni és nem lehet örökké hurkolni; egyik esetben sincs értelme.
