ВЫЧИСЛИТЕЛЬНАЯ МАШИНА АБСТРАКТНАЯ это:

ВЫЧИСЛИТЕЛЬНАЯ МАШИНА АБСТРАКТНАЯ

, абстрактная машина,- математическое понятие, к-рое описывает модель вычислительной машины, абстрагируясь от ограниченности емкости запоминающих устройств и других технич. параметров вычислительных машин. В отличие от последних, В. м. а. может вычислять функции, определенные на бесконечной области конструктивных объектов (напр., целых чисел, слов в конечном алфавите, конечных графов, бесконечных деревьев и т. д.). В. м. а. употребляется как понятие, уточняющее интуитивное понятие алгоритма, для исследования вопросов существования алгоритма (т. е. разрешимости или неразрешимости алгоритмических проблем), качества алгоритма (т. .е. оценок сложности различных параметров алгоритма), формализации семантики алгоритмических языков, моделирования одних классов В. м. а. другими (напр., с целью так наз. "распараллеливания" алгоритмов).

В. м. а. можно разделить на классы по уровню абстракции, а также по типу обрабатываемой информации. Ниже перечислены основные классы В. м. а.

1) В. м. а., обрабатывающие слова в конечном алфавите и относящиеся к наиболее высокому уровню абстракции в связи с подчинением структуры В. м. а. спе-цифич. запросам теории. Типичные представители - Тьюринга машина, машины Минского, нормальные алгорифмы Маркова, Поста каноническая система. В. м. а. часто употребляются для доказательства неразрешимости алгоритмич. проблем, а также для оценок сложности алгоритмов (см. Алгоритма сложность вычисления).

2) В. м. а., относящиеся к тому же уровню абстракции, что и В. м. а. из 1-го класса, но обрабатывающие матрицы, конечные графы, произвольные комплексы. Типичные представители - алгоритмы Колмогорова, автоматы Неймана - Чёрча, растущие автоматы. Если в алгоритмах Колмогорова преобразование информации производится локально, то в автоматах Неймана - Чёрча и растущих оно протекает параллельно. Построены универсальные В. м. а. с хорошими характеристиками, способные моделировать произвольные В. м. а. данного типа. Изучались вычисления с максимальным быстродействием (т. е. в реальное время) на В. м. а. из данного класса.

3) В. м. а., к-рые обрабатывают, чаще всего, слова или целые числа и относятся к низкому уровню абстракции. Их структуры сформировались под влиянием запросов практики и имеют много общего со структурами вычислительных машин. Типичные представители - так наз. операторные алгоритмы (см. [3]) и машины с произвольным доступом к памяти. Эти В. м. а. употребляются для оценки сложности алгоритмов, используемых на практике, и для моделирования двух типов В. м. а.

4) В. м. а., относящиеся к тому же уровню абстракции, что и В. м. а. из 3-го класса, но обрабатывающие произвольные графы- (чаще всего бесконечные деревья). Эти В. м. а. образовались в результате развития В. м. а. из 3-го класса, направленного на приспособление к оообенностям алгоритмич. языков. Такие В. м. а. используются для формализации семантики алгоритмич. языков, а также для доказательства правильности программ. Типичные представители - В. м. а., используемые для задания семантики языков алгол-68 и ПЛ /I.

Лит.:[1] Барздинь Я. М., "Докл. АН СССР", 1964, т. 157, № 3, с. 542-45; [2] Ван Вейнгаарден А. и др., Сообщение об алгоритмическом языке АЛГОЛ-68, "Кибернетика", 1969, № 6, с. 23-144; 1970, № 1, с. 13-160; [3] Ершов А. П., "Проблемы кибернетики", 1960, вып. 3, с. 5-48;

[4] Колмогоров А. Н., Успенский В. А., "Успехи матем. наук", 1958, т. 13, № 4, с. 3-28; [5] Минский М., Вычисления и автоматы, пер. с англ., М., 1971; [6] Трахтенброт Б. А., Алгоритмы и вычислительные автоматы, М., 1974; [7] Наrtmanis Т., "Math. Syst. Theory", 1971, v. 5, № 3, p. 232-45; [8] Wegnеr P., "Computing Surveys", 1972, v. 4, № 1, p. 5- 63. В. А. Непомнящий.


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Смотреть что такое "ВЫЧИСЛИТЕЛЬНАЯ МАШИНА АБСТРАКТНАЯ" в других словарях:

  • Абстрактная вычислительная машина — теоретическое построение, с помощью которого вводится строгое, математическое определение алгоритма. См. также: Абстрактные вычислительные машины Алгоритмы Финансовый словарь Финам …   Финансовый словарь

  • МАШИНА — (в математике) абстрактное устройство, осуществляющее переработку информации. Употребительны также термины абстрактная машина , автомат . Абстрактные М. являются частным случаем управляющих систем. Возникновение их связано с анализом понятия… …   Математическая энциклопедия

  • Машина Тьюринга для умножения чисел — Машина Тьюринга (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча… …   Википедия

  • Машина тьюринга — (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча Тьюринга, способна …   Википедия

  • Машина Поста — (МП) абстрактная вычислительная машина, предложенная Эмилем Леоном Постом (Emil L. Post), которая отличается от машины Тьюринга большей простотой. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм». Содержание 1 Принцип… …   Википедия

  • Машина поста — (МП) абстрактная вычислительная машина, предложенная Эмилем Леоном Постом (Emil L. Post), которая отличается от машины Тьюринга большей простотой. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм». Содержание 1 Принцип… …   Википедия

  • Машина Тьюринга — Художественное представление машины Тьюринга Машина Тьюринга (МТ)  абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма …   Википедия

  • Детерминированная машина Тьюринга — Машина Тьюринга (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча… …   Википедия

  • Тьюринга машина — Машина Тьюринга (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча… …   Википедия

  • Оптимизация (вычислительная техника) — Это статья об оптимизации программ и данных на всех этапах программирования. Об оптимизациях, применяемых компиляторами, см.: Оптимизация компилятора. В информатике оптимизацией называется процесс модификации системы для улучшения её… …   Википедия

Книги

  • Тьюринг, Алан, Джесси Рассел. Эта книга будет изготовлена в соответствии с Вашим заказом по технологии Print-on-Demand. High Quality Content by WIKIPEDIA articles! А?лан Мэ?тисон Тью?ринг (англ. Alan Mathison Turing; 23… Подробнее  Купить за 1254 руб
  • Машина Тьюринга, Джесси Рассел. Эта книга будет изготовлена в соответствии с Вашим заказом по технологии Print-on-Demand. High Quality Content by WIKIPEDIA articles! Маши?на Тью?ринга (МТ) — абстрактный исполнитель… Подробнее  Купить за 998 руб


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»