Задать вопрос юристу

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

М шиной Тьюринг н зыв ется пятерк объектов: T=(A,S,¶,μ,t), где А={a1, a2,..., an}- лф вит; λ – символ пустой ячейки. S={ s0, s1,..., sm} – множество внутренних состояний, причем s0 – з ключительное, s1 – н ч льное состояния.

Если при р боте происходит переход в состояние s0, то м шин прекр щ ет свою р боту и говорят, что он применим для д нного слов , т.е. з циклен .

ν: A´S ®S – функция переход ;

μ: A´S ® A – функция выход ;

t: A´S ® { Н,Л,П } – функция упр вления (н месте, лево, пр во).

Пример:

s1 s2
λ 1, П, s2 1, Н, s0
1 1, П, s1 λ, П, s1

Счит ем, что м шин Т, при р боте со словом, н чин ет р боту из состояния s1, считыв ющее устройство з вис ет н д первым слев непустым символом слов .

1 1 λ 1, 1 1 λ 1, 1 1 λ 1, 1 1 1 1, 1 1 1 λ λ, 1 1 1 λ 1
s1 s1 s2 s2 s2 s0

Т ким обр зом Т(12λ1)=13λ1.

Конфигур цией м шины Тьюринг в д нный момент времени н зыв ется з пись вид α1, ai, α2, где α1 – н ч ло слов , ai – символ в д нный момент времени, α2 – конец (хвост) слов .

Пример: Н пис ть м шину Тьюринг применимую к слов м вид x1, x2,..., xn (n≥2), где xiÎ{a,b}, и переводящую их в слово α=

1 2 3 4 5
λ λ Н 0 b П 5 b Н 0
a a П 2 λ П 3 λ П 3 a П 4
b b П 2 b П 4 λ П 3 b П 4

Проверим для слов abba:

a b b a a b b a a b b a a b b a a b b a λ a b b a b λ a b b a b b
1 2 4 4 4 5 0

Проверим для слов bab:

b a b b a b b λ b b λ λ λ b λ λ λ
1 2 3 3 0
<< | >>
Источник: Лекции по м тем тической логике. 2017
Вы также можете найти интересующую информацию в научном поисковике Otvety.Online. Воспользуйтесь формой поиска:

Еще по теме М шин Тьюринг .:

  1. Кодировк м шин Тьюринг .
  2. Вопрос 18 Машины Тьюринга. Тезис Тьюринга. Машина Тьюринга – Поста.
  3. Вопрос 18 Машины Тьюринга. Тезис Тьюринга.
  4. 8.4 МАШИНА ТЬЮРИНГА.
  5. Машина Тьюринга
  6. Особенности учета автомобильных шин
  7. Композиции машин Тьюринга
  8. № 108 Общие правила подготовки и наложения транспортных шин.
  9. в) Алгоритм нахождения кратчайших расстояний от выделенной вершины до всех остальных вер­шин графа (алгоритм Дейкстры).
  10. Числов я функция
  11. Алгоритмически нер зрешимые проблемы.
- Аналитическая геометрия - Высшая математика - Высшая математика - Вычислительная математика - Вычислительные методы линейной алгебры - Дискретная математика - Дифференциальное и интегральное исчисление - Дифференциальные уравнения - Исследование операций - История математики - Комбинаторика - Комплексное исчисление - Линейная алгебра - Линейная алгебра и аналитическая геометрия - Линейное программирование - Математическая логика - Математическая статистика - Математическая физика - Математический анализ - Метод конечных элементов - Методы оптимизации - Обработка результатов измерений - Общая алгебра - Операционное исчисление - Основы математики - Планирование эксперимента - Пределы - Ряды - Теория вероятностей - Теория графов - Теория игр - Теория конечных автоматов - Теория массового обслуживания - Теория принятия решений - Теория случайных процессов - Теория чисел - Философия математики - Функциональный анализ - Элементарная математика -