|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Что собой представляет машина Тьюринга?Практическая работа №1 1. Составить алгоритм сложения натуральных чисел.
2. Составить алгоритм прибавления к любому натуральному числу единицы.
3. Составить алгоритм вычитания единицы от любого натурального числа.
4. Составить алгоритм написания на пустой ленте числа 0; 1; 2; 3; 4. 5. Пусть на ленте имеется запись из нескольких меток подряд. Каретка находится над самой крайней правой помеченной ячейкой. Составить алгоритм нахождения ближайшей пустой ячейки слева.
6. Пусть на ленте имеется запись из нескольких меток подряд. Каретка находится над самой крайней левой помеченной ячейкой. Составить алгоритм нахождения ближайшей пустой ячейки справа.
7. Составить алгоритм нахождения ближайшей помеченной ячейки.
8. Составить алгоритм удаления всех меток на ленте.
1.4. Формализация понятия алгоритма посредством машины Тьюринга В 1936 г. Аланом Тьюрингом для уточнения понятия алгоритма был предложен абстрактный универсальный исполнитель. Его абстрактность заключается в том, что он представляет собой логическую вычислительную конструкцию, а не реальную вычислительную машину. Термин «универсальный исполнитель» говорит о том, что данный исполнитель может имитировать любой другой исполнитель. Например, операции, которые выполняют реальные вычислительные машины можно имитировать на универсальном исполнителе. В последствие, придуманная Тьюрингом вычислительная конструкция была названа машиной Тьюринга. Что собой представляет машина Тьюринга? Машина Тьюринга состоит из бесконечной в обе стороны ленты, разделенной на ячейки, и автомата (каретки), которая управляется программой. Программы для машин Тьюринга записываются в виде таблицы, где первые столбец и строка содержат буквы внешнего алфавита и возможные внутренние состояния автомата (внутренний алфавит). Содержимое таблицы представляет собой команды для машины Тьюринга. Буква, которую считывает головка в ячейке (над которой она находится в данный момент), и внутренне состояние головки определяют, какую команду нужно выполнить. Команда определяется пересечением символов внешнего и внутреннего алфавитов в таблице. Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие:
Автомат машины Тьюринга в процессе своей работы может выполнять следующие действия:
Одна команда для машины Тьюринга как раз и представляет собой конкретную комбинацию этих трех составляющих: указаний, какой символ записать в ячейку (над которой стоит автомат), куда передвинуться и в какое состояние перейти. Хотя команда может содержать и не все составляющие (например, не менять символ, не передвигаться или не менять внутреннего состояния). Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.) |