4183
правки
Машина Тьюринга: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 47: | Строка 47: | ||
Однако в машине Тьюринга лента неограниченно простирается вправо и влево, а головка не только читает, но и пишет. В силу этого лента в машине Тьюринга играет роль не только входной ленты | Однако в машине Тьюринга лента неограниченно простирается вправо и влево, а головка не только читает, но и пишет. В силу этого лента в машине Тьюринга играет роль не только входной ленты | ||
в конечном и магазинном автоматах, но и бесконечной вспомогательной памяти последнего, причем без присущих [[МП- автомат|''МП-автомату'']] ограничений на "магазинный" характер ее использования. | в конечном и магазинном автоматах, но и бесконечной вспомогательной памяти последнего, причем без присущих [[МП-автомат|''МП-автомату'']] ограничений на "магазинный" характер ее использования. | ||
Поэтому не случайно, что машины Тьюринга обладают большей вычислительной мощностью, чем МП- автоматы, определяющие класс [[КС-язык|''КС-языков'']]. Известно, что язык порождается грамматикой | Поэтому не случайно, что машины Тьюринга обладают большей вычислительной мощностью, чем МП- автоматы, определяющие класс [[КС-язык|''КС-языков'']]. Известно, что язык порождается грамматикой | ||