<<
>>

1.1.2 Машина Тьюринга - Поста.

Имеется устройство просматривающее бесконечную ленту, где есть ячейки содержащие элементы алфавита: , где - пустой символ (пустое слово), который может принадлежать и не принадлежать А.

Также существует управляющая головка (устройство) (УУ)/(УГ), которая в начальный момент расположена в определенном месте, в состоянии . Также существуют внутренние состояния машины:

Слово в данном алфавите - любая конечная упорядоченная последовательность букв данного алфавита, притом длина слова это количество букв в нем (у пустого слова длина 0).

Допустимые команды:

1) ,где .

2) (остановка программы).

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

<< | >>
Источник: Конспекты лекций по математической логике. 2017

Еще по теме 1.1.2 Машина Тьюринга - Поста.:

  1. ФИЛОСОФИЯ И ЕЕ ОТНОШЕНИЕ И КАРДИНАЛЬНЫМ ВОПРОСАМ ЛИНГВИСТИЧЕСКОЙ НАУКИ 
  2.   2.1.7. Физика, математика и компьютерные науки  
  3. 3.3. Проблема останова для человека
  4. Глава 7(2). Информационная война как целенаправленное информационное воздействие информационных систем
  5. 27(3).2. «Структура магии» и проблема останова
  6. 12.3.1 Источник компьютерных аналогий
  7. 12.3.2 Критика «машинного функционализма»
  8. 13.5.1.1 Элементы функционализма в изучении сознания
  9. 13.5.2.2 Функционализм против физикализма
  10. 1-41 Механическая кулинарная обработка овощей
  11. 19. Типи і еволюція економічних систем. Теоретичні підходи до класифікації ек с-м.
  12. Предисловие
  13. Глава 4. Алгоритмы и машины Тьюринга
  14. §4.1. О понятии алгоритма. Тезис Чёрча
  15. §4.2. Машина Тьюринга
  16. §4.3. Рекурсивные функции
  17. §4.4. Алгоритмически неразрешимые задачи
  18. 1.1 Различные подходы к определению алгоритма:
  19. 1.1.2 Машина Тьюринга - Поста.
  20. 5.2.1. Машины Тьюринга