Читать фрагмент

книга

Машины в теории вычислимых функций

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

Форматы: PDF

Издательство: Инфра-Инженерия

Год: 2024

Место издания: Москва, Вологда

ISBN: 978-5-9729-2057-0

Страниц: 104

Артикул: 111804

Возрастная маркировка: 16+

Электронная книга

810 ₽

Купить и скачать

Содержание

Содержание книги "Машины в теории вычислимых функций "

Предисловие

Глава 1. Машины Тьюринга

§ 1. Основное определение машины Тьюринга

§ 2. Класс Р полиномиально вычислимых функций

Глава 2. Машины с произвольным доступом к памяти

§ 1. Определение RAM-машины

§ 2. Сравнение вычислительных возможностей RAM-машин и машин Тьюринга

Глава 3. Машины Минского

§ 1. Определение и вычисление частично-рекурсивных функций

§ 2. Класс ε² иерархии Гжегорчика

Глава 4. Стековые регистровые машины

§ 1. Основные определения

§ 2. Классы εf

§ 3. Вычисления на машинах SRM с ограничениями на зону

§ 4. Программы специального вида для машин SRM

Глава 5. Регистровые машины со счетчиками

§ 1. Основные определения

§ 2. Вычисление простых арифметических функций

§ 3. Универсальность RC-машин

§ 4. Класс функций, строго вычислимых на RC-машинах

Глава 6. Счетчиковые машины с сумматором

§ 1. Определение и вычисление простых арифметических функций

§ 2. Универсальность CS-машин

Глава 7. Неуниверсальные машины

§ 1. Двуленточные нестирающие машины Тьюринга над двубуквенным алфавитом

§ 2. Двуленточные нестирающие машины Тьюринга над однобуквенным алфавитом

Литература

Внимание!
При обнаружении неточностей или ошибок в описании книги "Машины в теории вычислимых функций (автор Сергей Марченков, Игорь Савицкий)", просим Вас отправить сообщение на почту help@directmedia.ru. Благодарим!