Описание тега turing-machines

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

Вики

Машина Тьюринга - это устройство, которое манипулирует символами на полосе ленты в соответствии с таблицей правил. Несмотря на свою простоту, машина Тьюринга может быть адаптирована для моделирования логики любого компьютерного алгоритма и особенно полезна для объяснения функций центрального процессора внутри компьютера.

Машины Тьюринга - это не физические объекты, а математические. Машина Тьюринга - это своего рода машина состояний. В любой момент машина находится в любом из конечного числа состояний. Инструкции для машины Тьюринга состоят в определенных условиях, при которых машина будет переходить из одного состояния в другое.

В tape используется для хранения данных. Кроме того, он также может хранить серию переходов (небольшие программы) и, таким образом,head может бежать sub-programs. По аналогии с современными компьютерами, лента - это память, а головка - это микропроцессор.

Использование тегов

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

Обратите внимание: https://cstheory.stackexchange.com/ - еще один веб-сайт обмена стеками, который вы можете использовать для решения теоретических и концептуальных проблем с машинами Тьюринга с тегами.

Источник