Внешняя память машины Тьюринга

Предмет Программирование

👍 Проверено Автор24

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

Научные статьи на тему «Внешняя память машины Тьюринга»

Информационные процессы обработки данных

Такую функцию можно вычислить на т.н. машине Тьюринга - абстрактном устройстве, умеющем выполнять простейшие...
Создавая всё более сложные функции на основе комбинирования простых, машина Тьюринга может выполнять...
Схема машины Тьюринга....
Некоторые функции не возвращают значений, а выводят результат на какое-нибудь устройство или в память...
.. иначе ...); циклы, повторяющие часть программы до наступления определенного условия; обращения к внешним

Статья от экспертов

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

Доказывается, что по всякой машине Тьюринга M, использующей память, не превосходящую заданной конструируемой по памяти функции s от длины записи исходных данных n, можно построить применимую к любым исходным данным машину Тьюринга M1,являющуюся продолжением машины Тьюринга M. Теорема 1. Повсякой q-ленточной машине Тьюринга M, использующей память, не превосходящую заданной конструируемой по памяти функции s от длины записи исходных данных n, можно построить применимую к любым исходным данным q +1-ленточной машину Тьюринга M1, являющуюся продолжением машины Тьюринга M одной и той же произвольной наперёд заданной константой. Утверждение 1. Для каждого внешнего и внутреннего алфавита машины Тьюринга M память, используемая всюду применимой q +1-ленточной машиной M1, являющаяся продолжением q-ленточной машины M из условия теоремы, не превосходит линейной функции от размера памяти, используемой машиной M. Классы FP-SPACE и P-SPACE расширяются до классов pFP-SPACE и pP-SPACE соответственно,...

Creative Commons

Научный журнал

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

Определение 1 Машина Тьюринга — это абстрактный исполнитель или абстрактная вычислительная машина...
Принцип работы машины Тьюринга Машина Тьюринга принципиально отличается от компьютерных модулей, у неё...
в качестве запоминающего устройства выступает бесконечная лента, а у цифровых устройств память представляет...
Функции машины Тьюринга....
Автор24 — интернет-биржа студенческих работ Программа для машины Тьюринга Программа для машины Тьюринга

Статья от экспертов

Еще термины по предмету «Программирование»

Веб-сервис, веб-служба

(web service) вид программного обеспечения, предоставляющего свою функциональность клиентам на уровне программных интерфейсов, построенных на базе HTTP протокола.

Системы программирования

предназначены для разработки новых программ на конкретном языке программирования и включают в себя компилято- 83 ры, интерпретаторы, диалоговую среду, редакторы текстов, библиотеки стандартных подпрограмм, компоновщики, отладчики, справочные службы и т.д.

HTTP (Hypertext Transfer Protocol)

протокол передачи гипертекста.

Смотреть больше терминов

Повышай знания с онлайн-тренажером от Автор24!

Напиши термин
Выбери определение из предложенных или загрузи свое
Тренажер от Автор24 поможет тебе выучить термины с помощью удобных и приятных карточек

Попробовать тренажер