Есть ли у машины Тьюринга понятие "время"?

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

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

3 6
language-agnostic turing-machines

3 ответа:

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

ПС. Это из-за энтропии, время получается из вычислений. Вы можете сбросить компьютер в мгновение ока, - это в противоположном направлении от энтропии. Вот почему загрузка почти всегда занимает больше времени, чем выключение, особенно если вы отключаете питание.

5

Конечно, машина Тьюринга может вычислять время.

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

  1. Записать текущее время на ленту машины Тьюринга (равняется установке время в BIOS или загрузка его из интернета)

  2. Отредактируйте машину, чтобы она добавляла 1 секонт к времени на ленте на каждом шаге (равно электрический "генератор Тика" на материнской плате увеличивает число в BIOS в каждом ТИКе)

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

Но помните, что машина Тьюринга работает с алфавитом. Компьютеры работают с алфавитом {0,1}. Машина Тьюринга (или компьютер) не знает, представляют ли эти нули и единицы буквы, цифры, картинки или видео.
1

Возможно, вы захотите прочитать неформальное определение или, если вы предпочитаете, формальное определение того, что такое машина Тьюринга в Википедии

Случайно гуглянув, я также нашел Этот, который кажется многообещающим.

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