Oracle exists

Or, a general algorithm for a break problem may exist.
But, as always, there are nuances.
If interested, please under the cat.

Introduction

In 1936, Alan Turing proved that there is no general algorithm that analyzes other algorithms and indicates whether the program will hang or not.

I would like to immediately dot all the words and describe the terms that are used by me so that there is no understanding.

Program hang - the algorithm will work INFINITE the amount of time regardless of the speed of command execution, and parallel calculations. No matter how big a supercomputer is, we would always run an infinite amount of time.

Program execution in a finite time - the algorithm on any machine finishes its calculations no matter how voluminous they are. For example, if the algorithm runs for 300 million years, this does not mean that it is frozen, just for current resources it must be executed for 300 million years and it will ALWAYS be completed.

Now you can continue.

Turing's proof can be described as follows: there is a certain oracle S (algorithm) whose input is given a description of algorithm N and input data X. The program stops and returns 1 if algorithm N does not stop, having received input X.

The program does not stop otherwise, if the algorithm N stops, having received X as an input. If we feed our oracle a description of ourselves, there will be a contradiction and the algorithm will contradict itself. Details can be viewed on the wiki .

The Oracle exists, but he needs a brother

You are not embarrassed by the fact that the oracle should freeze if the algorithm it analyzes stops, here I am very embarrassed with this fact, therefore, for proof, we correct the oracle's conclusion a little. Let the oracle return 1 or 0. So what if you ask, nothing has changed, if we write in pseudocode:

If (оракул(N)==0){
While (true){
}
} 

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

S1 возвращает 0 или 1 но что значат эти 0 или 1 неизвестно, об этом знает только второй оракул.

S2 возвращает 0 или 1 для обозначения данных первого оракула, но не даёт информации о работе алгоритма. 1 означает что у первого оракула 1 будет означать бесконечное выполнение алгоритма, 0 остановка. А вот ноль на оборот у первого оракула 0 будет означать бесконечное выполнение алгоритма, 1 остановка.

Оракулы ВСЕГДА выполняют анализ за конечное время, но с оговоркой. Описание оговорки будет чуть ниже.

Два оракула нужны для того, чтобы алгоритм получив данные от одного оракула не смог узнать о своём будущем, до полного выполнения всей программы. Так как узнав результат своей работы, алгоритм может изменить своё поведение, тем самым опровергнув утверждение оракула.

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

Теперь как это будет выглядеть на псевдокоде:

Запрос к первому оракулу

If (оракул(N)==0){
While(true){
}
}

Запрос к второму оракулу

If (оракул(N)==0){
While(true){
}
}

Оба оракула вернут ноль что будет означать что алгоритм зависнет.

В конце выполненных алгоритмов мы можем взять и соотнести данные тем самым получив ответ.
Но есть еще один нюанс, все входные данные должны быть конечными. Ресурсы машины, также должны быть конечными. Если хоть что-то будет бесконечным, то гарантировать анализ оракулами за конечное время нельзя.

Заключение

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