|
Тьюринг - безусловно знаменитость. С именем Тьюринга всегда связывают "машину Тьюринга". Неформально, Машина Тьюринга (далее МТ) представляет собой автомат с конечным числом состояний и неограниченной памятью, представленной набором одной или более лент, бесконечных в обоих направлениях. Ленты поделены на соответственно бесконечное число ячеек, и на каждой ленте выделена стартовая (нулевая) ячейка. В каждой ячейке может быть записан только один символ из некоторого конечного алфавита Σ, где предусмотрен символ «*» для обозначения пустой ячейки. Программисты в узком кругу шутят "На машине Тьюринга далеко не уедешь" Рассмотрим
|