„Turing-gép” változatai közötti eltérés
| [ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
a typo |
a link |
||
103. sor:
A gép ábécéje tehát három szimbólumból áll, és négy állapotot használ.
Valójában sem időkihasználás, sem összetettség tekintetében nem ez a legjobb algoritmus de nem foglalkozunk a javításával. Egyébként elvileg nem nehéz jobb algoritmust keresni: az ezen háromelemű ábécé feletti legfeljebb négy állapotú „nem-[[Turing-gép#Formális ekvivalencia|izomorf]]” Turing gépek (azaz a definiálható átmenetfüggvények) száma mindenképp véges, tehát „pusztán” az összes definiálható átmenetfüggvényt kell végignézni, hogy működik-e a fenti inputfeltételek mellett (egy durva becslés: a megvizsgálandó Turing-gépek száma biztosan kisebb mint
: <math> \sum_{i=1}^{4}{ \left( 9i \right)}^{ 3 \cdot \left( i-1 \right) } </math> <math> = </math> <math> 1+2^{3}3^{6}+3^{18}+6^{18} </math> <math> = </math> <br /> <math> = </math> <math> 101560344094738 </math> <math> \approx </math> <math> 10^{14} </math> , tehát kb. [[billió|százbillió]] Turing-gépnél többet biztosan nem kell megvizsgálnunk …
=== A Turing-algoritmusok megszámlálhatóak és felsorolhatóak ===
| |||