Что именно является проблемой остановки?
Всякий раз, когда люди спрашивают о проблеме остановки, связанной с программированием, люди отвечают: "Если вы просто добавите один цикл, вы получите программу остановки и, следовательно, не сможете автоматизировать задачу ".
Имеет смысл. Если ваша программа имеет бесконечный цикл, то, когда ваша программа работает, у вас нет возможности узнать, продолжает ли программа обрабатывать ввод или она просто бесконечно зацикливается.
Но кое-что из этого кажется нелогичным. Что, если бы я писал программу решения проблем, которая принимает исходный код. rascher@localhost$ ./haltingSolver source.c
Если мой код (source.c) выглядит так:
for (;;) { /* infinite loop */ }
Похоже, моей программе было бы довольно легко это увидеть. "Посмотрите на цикл и посмотрите на условие. Если условие основано только на литералах, а не на переменных, то вы всегда знаете результат цикла. Если есть переменные (например, while (x < 10)), посмотрите, эти переменные когда-либо изменяются. Если нет, то вы всегда знаете результат цикла ".
Конечно, эти проверки не будут тривиальными (вычисление арифметики указателей и т. Д.), Но это не представляется невозможным. например:
int x = 0
while (x < 10) {}
может быть обнаружен. наряду с - хотя и не тривиально
int x = 0
while (x < 10)
{
x++;
if (x == 10)
{
x = 0
}
}
А как насчет ввода пользователя? Это кикер, это то, что делает программу непредсказуемой.
int x = 0;
while (x < 10)
{
scanf("%d", &x); /* ignoring infinite scanf loop oddities */
}
Теперь моя программа может сказать: "Если пользователь введет 10 или больше, программа остановится. На всех других входах она снова зациклится".
Это означает, что даже при сотнях входных данных можно перечислить условия, при которых программа остановится. Действительно, когда я пишу программу, я всегда проверяю, кто-то может ее прекратить! Я не говорю, что полученный список условий создать тривиально, но для меня это не кажется невозможным. Вы можете получить ввод от пользователя, использовать его для вычисления индексов указателей и т. Д. - но это только добавляет к числу условий, гарантирующих завершение программы, не делает невозможным их перечисление.
Так в чем же проблема остановки? Что я не понимаю в идее, что мы не можем написать задачу для обнаружения бесконечных циклов? Или почему "петли" такой часто цитируемый пример?
ОБНОВИТЬ
Итак, позвольте мне немного изменить вопрос: в чем заключается проблема с остановкой применительно к компьютерам? И тогда я отвечу на некоторые комментарии:
Многие люди говорят, что программа должна быть в состоянии справиться с "любым произвольным вводом". Но в компьютерах нет никакого произвольного ввода. Если я введу только один байт данных, то у меня будет только 2^8 возможных входов. Итак, в качестве примера:
int c = getchar()
switch (c) {
case 'q':
/* quit the program */
}
Внезапно, я только что учел все возможности. Если c имеет битовый шаблон 0x71, он делает одну вещь. Для всех других шаблонов он делает что-то еще. Даже программа, которая принимает произвольный ввод строки, никогда не бывает действительно "произвольной", так как ресурсы конечны, что означает, что хотя теория "произвольной" применима... она не совсем однозначна с практикой.
Другой пример, на который ссылаются люди:
while (n != 1)
if (n & 1 == 1)
n = 3 * n + 1;
else
n /= 2;
Если n - 32-разрядное целое число... тогда я могу визуально сказать вам, остановится ли это.
Я думаю, что это редактирование ничего не требует, но самый убедительный пример, который я видел, это:
Предположим, что у вас есть магическая программа / метод, чтобы определить, что программа останавливается.
public bool DeterminesHalt(string filename, string[] args){
//runs whatever program you tell it do, passing any args
//returns true if the program halts, false if it doesn't
}
Теперь допустим, что мы пишем небольшой фрагмент кода, такой как...
public static void Main(string[] args){
string filename = Console.ReadLine(); //read in file to run from user
if(DeterminesHalt(filename, args))
for(;;);
else
return;
}
Таким образом, для этого примера мы можем написать программу, полностью противоположную нашей магической методике остановки. Если мы каким-то образом определим, что данная программа остановится, мы просто запрыгнем в бесконечный цикл; в противном случае, если мы определим, что программа находится в бесконечном цикле, мы завершаем программу.
С другой стороны, если вы намеренно пишете программу, которая содержит бесконечный цикл... "решение проблемы остановки" - это спорный вопрос, не так ли?
26 ответов
РЕДАКТИРОВАТЬ (намного позже, чем оригинальный ответ): MarkCC из Good Math, Bad Math недавно написал отличное обсуждение проблемы остановки с конкретными примерами.
Проблема остановки - это в основном формальный способ узнать, можете ли вы сказать, остановится ли произвольная программа в конечном итоге.
Другими словами, можете ли вы написать программу, называемую оракулом остановки, HaltingOracle(программа, ввод), который возвращает true, если программа (ввод) в конечном итоге остановится, и который возвращает false, если не будет?
Ответ: нет, вы не можете.
В ответ на вопросы о том, является ли вклад в проблему Остановки релевантным или красная сельдь: Да, вклад важен. Кроме того, кажется, что существует некоторая путаница в том, что я вижу, что "бесконечное" используется там, где "произвольное" более правильно.
Практический пример: представьте, что вы работаете в позиции QA, и вам нужно написать программу проверки остановки (она же оракул), которая подтвердит это для любой произвольной программы, написанной группой разработчиков (D), и для любого произвольного ввода, предоставленного конечным пользователем. -пользователь (I), программа D в конечном итоге остановится, когда будет введен ввод I.
Голос менеджера Cue: "Хо-хо, эти глупые пользователи, давайте удостоверимся, что независимо от того, какой мусор они печатают, наши серверные задачи никогда не окажутся в бесконечном цикле. Сделайте так, код обезьяна!"
Это похоже на отличную идею, верно? Вы не хотите, чтобы ваш сервер зависал, верно?
Что говорит вам проблема остановки, так это то, что перед вами стоит неразрешимая задача. Вместо этого, в этом конкретном случае, вам нужно планировать задачи, которые выполняются после определенного порогового времени, и быть готовыми к их отмене.
Марк использует код вместо ввода, чтобы проиллюстрировать проблему:
def Deciever(i):
oracle = i[0]
in = i[1]
if oracle(Deceiver, i):
while True:
continue
else:
return i
В моем обсуждении в комментариях я пошел путем злонамеренного манипулирования вводом, чтобы вызвать неразрешимую проблему. Пример Марка гораздо более элегантен, он использует оракула, чтобы победить себя:
Таким образом, входные данные для Deceiver на самом деле представляют собой список из двух элементов: первый представляет собой предложенный оракул-остановитель. Второй - еще один вход. Что делает остановившийся убийца, так это спрашивает Оракула: "Как вы думаете, я остановлюсь для ввода i?". Если оракул говорит: "Да, ты остановишься", тогда программа перейдет в бесконечный цикл. Если оракул говорит "Нет, ты не остановишься", тогда он останавливается. Поэтому независимо от того, что говорит оракул, это неправильно.
Иными словами, без мошенничества, переформатирования входных данных, исчисляемых / неисчисляемых бесконечностей или каких- либо других отвлекающих факторов, Марк написал фрагмент кода, который может победить любую остановившуюся программу оракула. Вы не можете написать oracle что отвечает на вопрос о том, Deceiver когда-либо останавливается
Оригинальный ответ:
Из великой Википедии:
В теории вычислимости проблема остановки - это проблема решения, которая может быть сформулирована следующим образом: с учетом описания программы и конечного ввода решить, будет ли программа завершена или будет работать вечно с учетом этого ввода.
Алан Тьюринг доказал в 1936 году, что общего алгоритма для решения проблемы остановки для всех возможных пар ввода программы не может быть. Мы говорим, что проблема остановки неразрешима на машинах Тьюринга. Copeland (2004) приписывает актуальную проблему остановки термина Мартину Дэвису.
Одним из критических моментов является то, что вы не можете контролировать ни программу, ни ввод. Вы передали их, и это зависит от вас, чтобы ответить на вопрос.
Отметим также, что машины Тьюринга являются основой для эффективных моделей вычислимости. Иными словами, все, что вы делаете на современных компьютерных языках, может быть сопоставлено с этими архетипическими машинами Тьюринга. В результате, проблема остановки неразрешима на любом полезном современном языке.
Чтобы решить проблему остановки, вам нужно разработать алгоритм, который мог бы определить, останавливается ли любая произвольная программа для любого произвольного ввода, а не только относительно простых случаев в ваших примерах.
Вот простое объяснение доказательства того, что проблема остановки неразрешима.
Предположим, у вас есть программа H, которая вычисляет, останавливается ли программа. H принимает два параметра, первый - описание программы, P, а второй - вход, I. H возвращает true, если P останавливается на входе I, и false в противном случае.
Теперь напишите программу, p2, которая принимает в качестве входных данных описание другой программы, p3. p2 вызывает H(p3, p3), затем зацикливается, если H возвращает true и останавливается в противном случае.
Что происходит, когда мы запускаем p2(p2)?
Он должен зацикливаться и останавливаться одновременно, вызывая взрыв вселенной.
Это было избито до смерти так хорошо, что на самом деле есть поэтическое доказательство, написанное в стиле Льюиса Кэрролла доктора Сьюза Джеффри Пуллумом (он знаменитой " Языковой журнал").
Прикольные вещи. Вот вкус:
Вот трюк, который я буду использовать - и это просто сделать.
Я определю процедуру, которую я назову Q,
который будет использовать предсказания P о прекращении успеха
разбудить ужасный логический беспорядок....
Независимо от того, как P может работать, Q будет черпать это:
Q использует вывод P, чтобы P выглядел глупо.
Что бы P ни говорил, оно не может предсказать Q:
P прав, когда это неправильно, и ложь, когда это правда!
В википедии есть хорошее доказательство проблемы остановки.
Чтобы проиллюстрировать, почему недостаточно просто применить некоторую технику к циклам, рассмотрим следующую программу (псевдокод):
int main()
{
//Unbounded length integer
Number i = 3;
while(true)
{
//example: GetUniquePositiveDivisiors(6) = [1, 2, 3], ...(5) = 1, ...(10) = 1, 2, 5, etc.
Number[] divisiors = GetUniquePositiveDivisiors(i);
Number sum = 0;
foreach(Number divisor in divisiors) sum += divisor;
if(sum == i) break;
i+=2;
}
}
Можете ли вы придумать подход, который вернет true, если этот код остановится, и false в противном случае?
Если случайно вы серьезно боретесь за медаль Филдса, представьте код выше для этих проблем.
"Если вы просто добавите один цикл, у вас есть программа остановки и, следовательно, вы не можете автоматизировать задачу"
Похоже на кого-то, кто обобщает применение проблемы остановки. Есть множество определенных циклов, которые вы можете доказать, что они прерываются. Существует исследование, которое может выполнять проверку завершения для широких классов программ. Например, в Coq вы ограничены программами, которые вы можете прекратить. У Microsoft есть исследовательский проект под названием Terminator, который использует различные приближения, чтобы доказать, что программы будут прекращены.
Но помните, что проблема остановки не только в игрушечных примерах. Ни один из них не решает общую "проблему остановки", потому что они не работают для каждой программы.
Проблема в том, что проблема остановки говорит о том, что существуют программы, о которых вы не можете знать, завершатся ли они без их запуска, а это значит, что вы никогда не сможете решить, останавливаются ли они.
Пример программы, которая может или не может остановить (в Haskell):
collatz 1 = ()
collatz !n | odd n = collatz (3 * n + 1)
| otherwise = collatz (n `div` 2)
или в чем-то более доступном:
while (n != 1)
if (n & 1 == 1)
n = 3 * n + 1;
else
n /= 2;
При каждом целом числе>= 1 остановится ли эта программа? Ну, это сработало до сих пор, но нет теоремы, которая говорит, что она остановится для каждого целого числа. У нас есть гипотеза из-за Лотара Коллатца, которая восходит к 1937 году, но она не доказана.
В отношении подпункта "люди отвечают:" Если вы просто добавите один цикл, у вас есть программа остановки и, следовательно, вы не можете автоматизировать задачу "", я добавлю эту деталь:
Посты, в которых говорится, что вы не можете алгоритмически вычислить, остановится ли произвольная программа, абсолютно верны для машины Тьюринга.
Дело в том, что не все программы требуют машин Тьюринга. Это программы, которые могут быть вычислены на концептуально "более слабой" машине - например, регулярные выражения могут быть полностью реализованы конечным автоматом, который всегда останавливается при вводе. Разве это не мило?
Держу пари, что когда люди говорят "добавить один цикл", они пытаются выразить идею о том, что, когда программа достаточно сложна, она требует машины Тьюринга, и, таким образом, применяется проблема остановки (как идея).
Это может быть немного касательно вопроса, но я считаю, что, учитывая эту деталь в вопросе, на это стоило указать.:)
Отличным примером Тьюринга был самоссылочный - предположим, что есть программа, которая может проверить другую и определить, остановится она или нет. Вставьте программу проверки остановки самостоятельно, в программу проверки остановки - что она должна делать?
Вот программа, которую проблема остановки никогда не сможет решить.
Предположим, что у вас есть магическая программа / метод, чтобы определить, что программа останавливается.
public bool DeterminesHalt(string filename, string[] args){
//runs whatever program you tell it do, passing any args
//returns true if the program halts, false if it doesn't
}
Теперь допустим, что мы пишем небольшой фрагмент кода, такой как...
public static void Main(string[] args){
string filename = Console.ReadLine(); //read in file to run from user
if(DeterminesHalt(filename, args))
for(;;);
else
return;
}
Таким образом, для этого примера мы можем написать программу, полностью противоположную нашей магической методике остановки. Если мы каким-то образом определим, что данная программа остановится, мы просто запрыгнем в бесконечный цикл; в противном случае, если мы определим, что программа находится в бесконечном цикле, мы завершаем программу.
Независимо от того, сколько проверок ввода вы делаете, нет никакого возможного решения, чтобы определить, останавливается ли КАЖДАЯ программа, написанная или нет.
Уже есть много хороших ответов, но я не видел, чтобы кто-нибудь обращал внимание на тот факт, что в некотором роде сочетания теории и практичности проблема остановки действительно разрешима.
Итак, прежде всего, проблема остановки - это в основном задача написания программы, которая берет любую произвольную вторую программу и определяет, остановится ли вторичная программа на произвольном вводе. Итак, вы говорите: "Да, эта программа остановится на этом входе" или "Нет, не будет". И на самом деле, это неразрешимо в общем случае (другие люди, кажется, уже предоставили доказательства этого) на машине Тьюринга. Реальная проблема заключается в том, что вы можете как-то узнать, собирается ли что-то останавливаться, запустив его (просто подождите, пока оно не остановится), но вы не можете в действительности выяснить, не остановится ли что-нибудь, запустив это (вы просто продолжай ждать вечно).
Это проблема на машине Тьюринга, которая по определению имеет бесконечное количество памяти и, следовательно, бесконечно много состояний. Однако наши компьютеры имеют только ограниченный объем памяти. На компьютере всего несколько битов. Таким образом, если вы можете каким-то образом отслеживать все предыдущие состояния (битовые конфигурации), которые вы видели во время работы программы, вы можете гарантировать, что ваша программа проверки никогда не войдет в бесконечный цикл. Если вторичная программа в конце концов останавливается, вы говорите: "Да, эта программа остановится на этом входе". Если вы видите одну и ту же битовую конфигурацию дважды, прежде чем она остановится, вы знаете "Нет, это не будет". Вероятно, не имеет большого технического значения, но приятно знать, что во многих случаях действительно "сложные" проблемы, с которыми мы сталкиваемся, сложнее в теории, чем на практике.
Пока много интересных конкретных примеров / аналогий. Если вы хотите углубиться в историю, есть хорошая книга Чарльза Петцольда об оригинальной статье Тьюринга "Аннотированная Тьюринг".
В связанном, в некотором роде, вене, есть действительно опрятное эссе в сети, Кто может назвать большее число? который наносит на машины Тьюринга и функции Аккермана.
Доказательство с другой точки зрения
Предположим, у нас есть процессор с инструкциями вроде mov, add, jmp, но без in или out. И у нас есть память. В отличие от других процессоров, у этого есть другой регистр, называемый paraReg. Этот регистр похож на файл, мы можем перемещать в него неограниченное количество контента, получать его размер, искать его в середине, удалять из него часть контента, что делается с помощью некоторых дополнительных инструкций.
Прежде чем мы начнем, давайте определимся с некоторыми словами. Программа представляет собой набор инструкций, который представляет собой строку. Перед запуском программы мы очищаем все регистры и память до нуля, кроме paraReg, который содержит параметр (строку), а затем помещаем программу в ячейку памяти и устанавливаем нулевой регистр ip. Процесс - это когда программа запущена.
Теперь проблема остановки может быть сформулирована так: для любой программы, называемой proObj(если она принимает параметр para0, мы добавляем в первую строку инструкцию: mov paraReg, para0), есть ли программа, которая принимает proObj в качестве параметр и может решить, будет ли proObj остановлен, когда proObj начнет работать с параметром paraReg, установленным на ноль?
Предположим, мы получили такую программу, которая называется p1. Затем мы можем создать другую программу с именем p2, которая принимает параметр para0. Через p1 мы можем сказать, остановится ли программа, содержимое которой para0, параметр para0 которой равен para0, или нет.(Мы делаем это таким образом. Создайте программу, первая строка которой - [mov paraReg, para0], остальное - para0. Назовите эту программу pro0. Затем мы устанавливаем paraReg в pro0 и вызываем p1.) Если она остановится, мы позволим p2 войти в бесконечный цикл, в противном случае мы позволим p2 остановиться.
Если мы поместим p2 в paraReg и запустим p2, процесс остановится или нет? Если он останавливается из определения p2, мы знаем, что когда мы помещаем p2 в paraReg и запускаем p2, он не должен останавливаться; Точно так же, если он не останавливается, мы знаем, что если положить p2 в paraReg и запустить p2, он должен остановиться. Тогда мы можем сказать, что нет p2 и нет p1.
Это вариант проблемы остановки собаки, за исключением программ вместо собак и остановки вместо лая.
Вот быстрое и относительно простое доказательство:
Предположим, ваш друг говорит вам, что он это сделал: у него есть программа (называемая
function P() {
while (Halts(P)) { /* loop */ }
}
Если это правда, то цикл повторяется навсегда. Но если
Это не значит, что они не могли приблизиться, поскольку большинство распространенных программ намного проще - им просто нужно сказать «не знаю» в более сложных случаях. Постоянно ведутся всевозможные исследования для решения наиболее распространенных случаев и, в первую очередь, для обеспечения того, чтобы вы избегали написания этих сложных программ. Однако придумать полезные ограничения для слишком сложных программ ... далеко не так просто.
Источник: я помню, как изначально видел это доказательство в другом месте, но это по сути то же самое, что доказательство Кристофера Стрейчи, показанное в статье в Википедии здесь , и похоже на ответ Ахокера выше.
Вы перечислили несколько простых случаев.
Теперь подумайте о всех остальных случаях.
Существует бесконечное количество возможных сценариев, вам придется перечислить их все.
Если, конечно, вы не могли бы обобщить это.
Вот где возникает проблема остановки. Как вы ее обобщаете?
От Программирования Жемчуга, Джоном Бентли
4.6 Проблемы
5. Докажите, что эта программа завершает работу, когда ее вход x является положительным целым числом.
while x != 1 do
if even(x)
x = x/2
else
x = 3*x +1
Точное определение проблемы заключается в том, что вам нужно написать программу, которая выполняет следующие действия: - принимает произвольную программу - определяет, останавливается ли программа при любом произвольном конечном вводе в программу
Тем не менее, это действительно высокая планка. Существует много частичных решений проблемы остановки, но нет общего решения. Что еще хуже, даже найти программы, которые частично решают проблему остановки, как известно, трудно:
BBC h2g2 статья о проблеме остановки
Если вы действительно решили проблему остановки, то вам нужно работать на таких сайтах, как rentacoder.com. Несколько месяцев назад на одном из них было сообщение от пользователя ATuring, предложившего контракт для решения проблемы остановки.:)
Вот моя попытка, отнеситесь к ней с недоверием.
Проблема с остановкой: можно ли создать программу, которая могла бы сказать, остановится ли произвольная программа на произвольном вводе?
Назовем такую программу
Теперь предположим эти две программы:
program_1 (input){
loop forever
}
а также
program_2 (input){
halt
}
Для
Мы могли сказать это, просто посмотрев на их исходный код и не выполняя программы.
Всегда ли можно найти исходный код и проанализировать управляющие структуры, чтобы определить, остановится ли программа при вводе?
Чтобы ответить на этот вопрос, возьмите следующую программу:
program_3 (input) {
...func definition...
result = func(input)
if result = 12345
then loop forever
else halt
}
Предположим, что это функция, которая отображает целое число в целое число. А также предположим, что у func нет закрытой формы. Например, это может быть функция, возвращающая входное простое число в последовательности простых чисел.
Теперь у нас будут проблемы. Чтобы проанализировать его исходный код, нужно сказать, что
Это отвечает на наш вопрос. Нет, не всегда можно посмотреть исходный код и сказать, как программа будет себя вести. Может быть для некоторых программ, но не для всех.
Итак, как вы думаете, что они могут что-то сказать о. Он должен выполнить / смоделировать программу на входе, чтобы увидеть, что вернется.
Но предположим, что if имеет следующее определение:
func (input){
...definition of prime(k): return k-th prime number...
result = prime(input)
i = prime(input - 1)
j = prime(input - 2)
if(i mod j = 5)
then loop forever
else return result
}
Сейчас
Это, наконец, решает проблему остановки. Нет, мы не можем создать
Еще один пример. Я недавно столкнулся с чем-то, называемым градом чисел. Эти числа образуют последовательность с этими правилами
f(n) is odd - f(n+1) = 3*f(n)+1
f(n) is even - f(n+1) = f(n)/2
В настоящее время предполагается, что все начальные точки в конечном итоге достигнут 1, а затем повторяются 4,2,1,4,2,1,4,2,1... Однако этому нет никаких доказательств. Так что сейчас единственный способ определить, заканчивается ли число при подаче в последовательность града, - это фактически вычислить его, пока вы не достигнете 1.
Это ключ к пониманию проблемы остановки. Насколько я понимаю, вы не можете точно знать, что программа остановится / не остановится, если вы действительно не запустите ее. Таким образом, любая программа, которую вы пишете, которая может дать вам ответ наверняка на проблему остановки, должна была бы фактически запустить программу.
Я бы предложил прочитать это: http://en.wikipedia.org/wiki/Halting_problem, особенно http://en.wikipedia.org/wiki/Halting_problem, чтобы понять, почему эту проблему нельзя решить в алгоритмический способ.
Значение проблемы остановки не заключается в важности самой проблемы; напротив, автоматизированное тестирование будет мало практического применения в разработке программного обеспечения (доказательство того, что остановка программы не доказывает, что оно является правильным, и в любом случае гипотетический алгоритм обеспечивает доказательство только для данного конечного ввода, тогда как в реальной жизни разработчик программного обеспечения будет более заинтересован в тестировании для всех возможных конечных входов).
Скорее проблема остановки была одной из первых, которая оказалась неразрешимой, что означает, что не существует алгоритма, который бы работал в общем случае. Другими словами, Тьюринг доказал более 70 лет назад, что есть некоторые проблемы, которые компьютеры не могут решить - не только потому, что правильный алгоритм еще не найден, но и потому, что такой алгоритм не может существовать логически.
Предположим, что вы пишете алгоритм, который может проверять любой произвольный фрагмент кода и сообщать, останавливается ли он.
Теперь дай свой алгоритм самому проверить.
Возможно, вам будет полезно рассмотреть историю парня, который косит газон любого, кто не косит свой собственный газон, и спросить себя, действительно ли он косит свой собственный газон.
Изучите эту программу:
for (x= 1; ; x++)
for (y= 1; y <= x; y++)
z= pow(x * x * x + y * y * y, 1./3.)
if (z == int(z))
stop;
Это остановится? Может ли компилятор предсказать, остановится ли он?
[Обратите внимание, что этот пример не доказывает невозможность проблемы остановки]
Решение: H обнаруживает H внутри H+ и игнорирует вывод H+ и принимает вывод самого себя H. Таким образом, проблема саморекламы решается путем обнаружения самореференции, таким образом, проблема остановки сводится к проблеме сокращения самопознания lol :)
В этом есть смысл, цикл - это форма саморекламы, которая ссылается на свою собственную отправную точку.
Теперь "мошенническая" машина Алана Тьюринга делает то же самое: она обращается к себе, изменяет вывод и принимает это как своего рода проваленное доказательство.
Теперь ваша задача - доказать, что Алан неправ, и написать компьютерную программу, которая может свести любую программу к базовым «аксиомам» и тому подобному ... и деконструировать, возможно, даже обнаружив любой вид самореференции, но, возможно, также полностью машинную / программную самореференцию на не позволяйте обманщику, подобному Алану, ввести в заблуждение и обмануть вашу машину! ;)
Возможно, такая машина может даже стать самосознательной, возможно, есть ссылка на самосознание :)