105
правок
Изменения
Нет описания правки
Доказательство аналогично предыдущей теореме.
}}
{{Теорема
|statement=Для произвольного ЛКА можно построить эмулирующую его машину Тьюринга.
|proof=
}}
Из доказанных выше теорем следует, что линейный клеточный автомат и машина Тьюринга эквивалентны.
==Литература==
* A.R. Smith III, Simple Computation-Universal Cellular Spaces, Journal of Association for Computing Machinery, Vol. 18, No. 3, July 1971.
* M. Delorme, An Introduction to CellularAutomata, July 1998.
