amarao (amarao_san) wrote,
amarao
amarao_san

Category:

Детерминированность тьюринг-машины

Можно ли считать детерминированной тьюринг-машину, в которой есть таймаут? Нам для реализации таймаута вовсе не обязательно иметь внешний счётчик времени - мы можем иметь таймаут, реализованный как счётчик силами самой машины (спинлок с счётчиком).

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

Получается, что в реальном мире мы не можем иметь две детерминированные машины так, чтобы их взаимодействие было детерминированным. Каждая машина детерминирована, но их взаимодействие - нет.

Как эту задачу разбирают в computer science? (Я понимаю, что есть множество приёмов синхронизации/блокировки для реальной жизни - но в рамках теоретической модели, как это решается?)
Subscribe

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 11 comments