Участник:Bioqwer/Машина Тьюринга. Количество. — Решение Александрова

Материал из DISCOPAL
Перейти к: навигация, поиск


Машина Тьюринга. Количество.

Исходя из определения Hopcroft and Ullman (1979, p. 148)

One-tape Turing machine can be formally defined as a 7-tuple where

  • is a finite, non-empty set of states
  • is a finite, non-empty set of tape alphabet symbols
  • is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the computation)
  • is the set of input symbols
  • is a partial function called the transition function, where L is left shift, R is right shift. (A relatively uncommon variant allows "no shift", say N, as a third element of the latter set.) If is not defined on the current state and the current tape symbol, then the machine halts.
  • is the initial state
  • is the set of final or accepting states. The initial tape contents is said to be accepted by if it eventually halts in a state from .

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


Суммируя, получаем


StasFomin (обсуждение) 11:24, 1 декабря 2016 (UTC): Оцените полиномом относительно размера алфавита и числа состояний. Ибо зачем нужна такая «хрен посчитаешь» оценка.