Машина Тьюринга. Это должен знать каждый

Про машину Тьюринга должен знать любой школьник, мечтающий стать программистом. Ведь именно её считают основой основ теории алгоритмов.

Несмотря на довольно сложное формальное определение, идея в принципе проста.

Это не инженерное устройство, не изобретение наподобие арифмометра, а что-то вроде демона Максвелла: изначально абстрактное порождение мысли очень умного человека.

 Машина Тьюринга (МТ) — математическая абстракция, представляющая вычислительную машину общего вида. Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.

Машина Тьюринга является расширением модели конечного автомата и, согласно тезису Чёрча — Тьюринга, способна имитировать (при наличии соответствующей программы) любую машину, действие которой заключается в переходе от одного дискретного состояния к другому.

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