Существует так называемая машина Тьюринга, придуманная великим математиком Алланом Тьюрингом. Она представляет собой ленту, потенциально бесконечную в обе стороны и устройство, которое может писать или стирать символ на ленте и двигаться влево или вправо. Так вот, любой алгоритм может быть выражен некоторой машиной Тьюринга. Кроме того, существует универсальная машина Тьюринга, которая может реализовать любую другую машину Тьюринга.
Добавить комментарий