АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Что собой представляет машина Тьюринга?

Читайте также:
  1. IV. Определите, какую задачу взаимодействия с практическим психологом поставил перед собой клиент.
  2. VII. Идея и деление особой науки, называемой критикой чистого разума
  3. А) представляет собой инвестиции, необходимые для поддержания капитала на одного работника, на постоянном уровнеВ) обеспечивает возмещение выбытия капитала
  4. Безопасное производство работ грузоподъемными машинами
  5. Большую угрозу для человечества представляет радиационное загрязнение окружающей среды, связанное, прежде всего, с аварийными ситуациями.
  6. Борьба с неуверенностью и беспомощностью: женщина, решившая покончить с собой
  7. БУРЯКОРІЗАЛЬНА МАШИНА
  8. Быть собой
  9. В 72-х дневном цикле подвиг длится 8 суток, из которых 2 суток – голод, а 6 – очистительные процедуры и работа над собой. В 12-ти летнем цикле подвиг длится 1 год.
  10. В биологическом смысле регенерация представляет собой приспособительный процесс, выработанный в ходе эволюции и присущий всему живому.
  11. В дни захватов каждый старший ранг обязан иметь с собой 200 грамм наркотиков и 3000 материалов для сборки оружия и раздачи наркотиков младшим рангам.
  12. В зависимости от риска, который представляет собой химикат

Практическая работа №1

1. Составить алгоритм сложения натуральных чисел.

  _                
  V V     V V V    

 

2. Составить алгоритм прибавления к любому натуральному числу единицы.

    _              
      V V V        

 

      _            
      V V V        

 

          _        
      V V V        

 

3. Составить алгоритм вычитания единицы от любого натурального числа.

    _              
      V V V        

 

      _            
      V V V        

 

          _        
      V V V        

 

4. Составить алгоритм написания на пустой ленте числа 0; 1; 2; 3; 4.

5. Пусть на ленте имеется запись из нескольких меток подряд. Каретка находится над самой крайней правой помеченной ячейкой. Составить алгоритм нахождения ближайшей пустой ячейки слева.

                _  
      V V V V V V  

6. Пусть на ленте имеется запись из нескольких меток подряд. Каретка находится над самой крайней левой помеченной ячейкой. Составить алгоритм нахождения ближайшей пустой ячейки справа.

      _            
      V V V V V V  

 

7. Составить алгоритм нахождения ближайшей помеченной ячейки.

      _            
            V V V  

 

              _    
      V V          

 

8. Составить алгоритм удаления всех меток на ленте.

  _                
      V V V V V V  

 

                _  
      V V V V V    

 

 


1.4. Формализация понятия алгоритма посредством машины Тьюринга

В 1936 г. Аланом Тьюрингом для уточнения понятия алгоритма был предложен абстрактный универсальный исполнитель. Его абстрактность заключается в том, что он представляет собой логическую вычислительную конструкцию, а не реальную вычислительную машину. Термин «универсальный исполнитель» говорит о том, что данный исполнитель может имитировать любой другой исполнитель. Например, операции, которые выполняют реальные вычислительные машины можно имитировать на универсальном исполнителе. В последствие, придуманная Тьюрингом вычислительная конструкция была названа машиной Тьюринга.
Кроме того, предполагается, что универсальный исполнитель должен уметь доказывать существование или отсутствие алгоритма для той или иной задачи.

Что собой представляет машина Тьюринга?

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

Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие:

  • Внешний алфавит. Конечное множество (например, А), элементы которого называются буквами (символами). Одна из букв этого алфавита (например, а0) должна представлять собой пустой символ.
  • Внутренний алфавит. Конечное множество состояний каретки (автомата). Одно из состояний (например, q1) должно быть начальным (запускающим программу). Еще одно из состояний (q0) должно быть конечным (завершающим программу) – состояние останова.
  • Таблица переходов. Описание поведения автомата (каретки) в зависимости от состояния и считанного символа.

Автомат машины Тьюринга в процессе своей работы может выполнять следующие действия:

  • Записывать символ внешнего алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой).
  • Передвигаться на одну ячейку влево или вправо.
  • Менять свое внутреннее состояние.

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


1 | 2 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)