Конечный автомат: различия между версиями
[непроверенная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
Locobas (обсуждение | вклад) Нет описания правки |
Retimuko (обсуждение | вклад) что это? совершенно не энциклопедический стиль, здесь не блог |
||
Строка 66:
Хотя теоремы Клини и отвечают на вопрос о том, что может делать конечный автомат, но отвечают они на этот вопрос неэффективно. Сделаны первые попытки построения иных языков, на которых ответ может быть дан эффективно. Эта проблема языка, играющая кардинальную роль в получении эффективного ответа на вопрос, что может и что не может «делать» конечный автомат, имеет решающее значение и для первых этапов синтеза автомата, то есть для ответа на второй из сформулированных выше вопросов. Если расширить класс динамических систем, которые мы определили терминами «конечный автомат» и «последовательностная машина», включением бесконечной памяти (моделью бесконечной памяти может быть, например, бесконечная лента для хранения символов или бесконечное число состояний), то для динамических систем этого более широкого класса (абстрактные системы этого класса называют [[Машина Тьюринга|машинами Тьюринга]]) ответ на вопрос «что они могут делать?» значительно проще — они могут реализовать '''любой наперед заданный алгоритм'''. При этом само понятие алгоритма трактуется в современной математике как реализация вычисления значений какой-либо [[Рекурсивная функция (теория вычислимости)|рекурсивной функции]]. Столь однозначный и четкий ответ на вопрос «что может делать машина Тьюринга?» дает возможность положить понятие о машине Тьюринга в основу определения понятия алгоритма: алгоритмом называется любой процесс, который может быть осуществлен на конечном автомате, дополненном бесконечной памятью, то есть алгоритмически полных машинах, на машине Тьюринга, на [[Машина Поста|машине Поста]] и др.
== Примечания ==
|