Существенная особенность работы машины Тьюринга состоит в том, что на каждом такте преобразование информации происходит ... - Большая Энциклопедия Нефти и Газа



Выдержка из книги Трахтенброт Б.А. Алгоритмы и вычислительные автоматы


Существенная особенность работы машины Тьюринга состоит в том, что на каждом такте преобразование информации происходит только в одной ячейке; остальные же ячейки в это время дожидаются посещения головки. Конечно, бывают случаи, когда такое ожидание оправдано природой решаемой задачи. Однако легко представить себе и иные ситуации, когда такой зависимости нет, и, следовательно, единственная причина, по которой преобразования в ячейках 3 и а не осуществляются одновременно ( параллельно), заключается лишь в том, что машина Тьюринга не в состоянии этого делать.

(cкачать страницу)

Смотреть книгу на libgen

Существенная особенность работы машины Тьюринга состоит в том, что на каждом такте преобразование информации происходит только в одной ячейке; остальные же ячейки в это время дожидаются посещения головки. Конечно, бывают случаи, когда такое ожидание оправдано природой решаемой задачи. Однако легко представить себе и иные ситуации, когда такой зависимости нет, и, следовательно, единственная причина, по которой преобразования в ячейках 3 и а не осуществляются одновременно ( параллельно), заключается лишь в том, что машина Тьюринга не в состоянии этого делать.