Стартовая страница
Тематическая группировка Расширить глоссарий Первый глоссарий Предыдущий глоссарий Основные темы Следующий глоссарий Последний глоссарий
 Глоссарий

Абстрактные вычислительные машины

Оглавление 

Входы 

Алгоритмы >

Устройства >


 

§ Информационные технологии

Абстрактная вычислительная машина

Абстрактная вычислительная машина - теоретическое построение, с помощью которого вводится строгое, математическое определение алгоритма.
 
Новая функция:  Формула глоссария
 

 Выходы

 >> Конечные автоматы


 

Абстрактная вычислительная машина

Абстрактная вычислительная машина - теоретическое построение, с помощью которого вводится строгое, математическое определение алгоритма.

Автомат

Автомат - разновидность абстрактной вычислительной машины, которая определяется:
- множеством входных и выходных сигналов;
- множеством состояний;
- функцией, задающей переходы из одних состояний в другие; и
- функцией, определяющей выходные сигналы в зависимости от входного сигнала и текущего состояния.
Автомат предназначен для формальной переработки последовательностей символов.
 >> Конечный автомат

Finite-state machine

Конечный автомат - математическая модель устройства с конечной памятью. Конечный автомат перерабатывает множество входных дискретных сигналов в множество выходных сигналов. Различают синхронные и асинхронные конечные автоматы.

Машина Поста

Машина Поста - математическое построение, предназначенное для уточнения понятия алгоритма. Машина Поста состоит:
- из неограниченной в обе стороны ленты, разделенной на ячейки;
- из головка чтения/записи, которая может перемещаться вдоль ленты и управляется программой на специальном языке из шести команд.
Доказано, что классы алгоритмов, представленных в форме машины Поста, и класс алгоритмов, представленных в форме машины Тьюринга, совпадают.

Машина Тьюринга

Машина Тьюринга - математическое построение, предназначенное для уточнения понятия алгоритма.
Машина Тьюринга состоит:
- из неограниченной в обе стороны ленты, разделенной на ячейки;
- из головка чтения/записи, которая может перемещаться вдоль ленты.
Программа для машины Тьюринга, задается в виде таблицы, определяющей команды для головки.

Нормальный алгоритм Маркова

Нормальный алгоритм Маркова - математическое построение, предназначенное для уточнения понятия алгоритм. Нормальный алгоритм Маркова:
- задается алфавитом и нормальной схемой подстановок, выполняемых по заранее определенной схеме;
- определяет преобразование строк.
Доказано, что класс нормальных алгоритмов Маркова и класс алгоритмов, представленных в форме машины Тьюринга, совпадают.

Тезис Тьюринга

Тезис Тьюринга - принимаемое без доказательства фундаментальное положение теории алгоритмов, согласно которому всякий алгоритм представим в форме машины Тьюринга.

  Первый  <<  Предыдущий

 Оглавление глоссария No.22

Следующий  >>  Последний 

Абстрактная вычислительная машина / Автомат / Конечный автомат / Машина Поста / Машина Тьюринга / Нормальный алгоритм Маркова / Тезис Тьюринга


Библиография  |  webadmin@glossary.ru
Copyright © 2000-2013 «Web-and-Press»

  

Курильский бобтейл;
Служебная библиотека
СИАРЕС

Деловой двор
Бухгалтерский учет для


  


Rambler's Top100
Rambler's Top100