Можно ли сделать функцию остановки, если вы не вызываете ее самостоятельно?

Question

Стандартным доказательством невозможности решения проблемы остановки обычно является что-то вроде этого

//does_halt() takes a function as input and returns true if it will ever finish computing

function paradox()
    {if does_halt(paradox())
        {
          while(true){}
        }
    }        

Это доказательство требует, чтобы вы вызывали функцию остановки рекурсивно, но возможно ли создать функцию остановки, которая всегда вычисляет правильный результат, пока он не вызывается сам по себе?

Answer 1

Это доказательство не требует рекурсии. Вы упускаете суть! Вы не вызываете парадокс, но передаете его как функцию более высокого порядка. Возьмите эту функцию в схеме и ее использование:

;; does operation passed as x to 2 and 5
(define (do2by5 x)
  (x 2 5))

;; examples    
(do2by5 +)    ; ==> 7
(do2by5 *)    ; ==> 10
(do2by5 expt) ; ==> 32

Как видите, я не подаю заявку +, * или же expt в моих примерах. Я просто передаю это в качестве аргумента. Это do2by5 который использует это. В вашем парадоксе кажется, что вы называете парадоксом, так как вы добавили () на имя. Это неправильно, так как does_halt должен принимать аргумент функции так же, как мой do2by5, Вот как бы я написал это на схеме:

;; this procedure does not halt!
(define (forever)
  (forever))

(define (paradox x)
 (if (halt? paradox) ; see I'm not calling it but passing it
     (forever)
     'im-finished))

Теперь настоящий сок, конечно, halt? и это, конечно, невозможно реализовать и paradox является доказательством того, что вы не можете сделать такую ​​функцию.

Остановка проблемы Tvivia: Многие не понимают, что вы можете сделать halt? для кода конечного размера, находящегося в памяти конечного размера, если ресурсы, которые вы должны исследовать, разумно больше минимальной машины, которая может содержать анализируемую программу. например. В качестве примера здесь приведена одна для всех трехбайтовых программ BrainFuck, сокращенная до завершения по Тьюрингу (например, без , а также .):

(define (bf3halt? x)
  (not (member x '("+[]" "-[]"))))

Для большего примера вы можете запустить программу в состоянии хэширования памяти виртуальной среды и счетчика программ. Если вы когда-нибудь снова столкнетесь с одним и тем же счетчиком памяти и программы, у вас будет бесконечный цикл и вы сможете вернуть false. (теперь вы видите требования к памяти halt? может быть до code size аргумент умножить потребление памяти аргументом при запуске)

Answer 2

Конечно, но вы должны помнить, что теория вычислений является теоретической и работает в бесконечности и физической невозможности.

function paradox1() {
   if (does_halt(paradox2())
       return true;
   else
       return false;
}
function paradox2() {
   if (does_halt(paradox3())
       return true;
   else
       return false;
}
function paradox3() {
   if (does_halt(paradox4())
       return true;
   else
       return false;
}
function paradox4() {
   if (does_halt(paradox5())
       return true;
   else
       return false;
}
etc etc etc _infinitely_

Это действительная программа Turing Machine, которая проясняет, как невозможно определить, что произойдет бесконечно в будущем.