Проблема остановки (я думаю) — это проблема попытки найти общий алгоритм для определения того, остановится ли конкретная программа в компьютерной системе. Было показано, что общей процедуры для этого не существует (я думаю). Относится ли это к организационным способностям ума? Любая система управления информацией, такая как разум/мозг, должна управлять, когда определенные программы должны «запускаться» или изменяться, и если она не всегда может сказать, когда программа остановится, как система может организовать себя??
Проблема остановки ничего прямо не говорит о сознании. В нем что-то говорится о рекурсивных множествах и рекурсивно перечислимых множествах. Рекурсивно перечислимое множество — это множество целых чисел, которые могут быть сгенерированы (перечислены) машиной Тьюринга. (Мы можем создать машину Тьюринга, которая будет печатать каждый член набора на своей ленте.)
Теорема Тьюринга:
при любом кодировании целых чисел в вычислительных машинах множество пар целых чисел
K знак равно { < я , j > | программа i останавливается при запуске на входе j }
рекурсивно перечислим, а его дополнение
не (К) знак равно { < я , j > | программа i не останавливается при запуске на входе j }
не является.
Неудивительно, что существует много наборов целых чисел (или пар целых чисел), которые не поддаются рекурсивному перечислению. Существует только счетное количество целых чисел (и только счетное количество пар целых чисел), поэтому только счетное количество машин Тьюринга можно закодировать целыми числами. Но множество всех наборов целых чисел ( степень множества целых чисел) несчетно бесконечно. Таким образом, «большинство» наборов целых чисел не являются рекурсивно перечислимыми.
Доказательство Тьюринга основано на диагонализации и похоже на парадокс лжеца .
Давайте посмотрим на набор dontHaltOnItself = { i | программа i не останавливается при запуске на входе i }
Можем ли мы сконструировать машину Тьюринга H, которая останавливается и печатает «accept» для всех i в строке DoesntHaltOnItself, а в противном случае (если i останавливается при запуске i ) работает вечно? Полагаю, что так. Является ли H неостановленным? Предположим, что H находится в состоянии notHaltOnItself. Затем, когда H запускается на входе H, он не останавливается. Но для всех яin notHaltOnItself H должен был остановиться и напечатать «принять». Таким образом, H не должен находиться в состоянии DoesnHaltOnItself. Но это означает, что когда H работает сам с собой, он останавливается. Но когда H запускается в программе, которая останавливается сама по себе, предполагается, что она будет работать вечно. Тоже противоречие. Таким образом, наше предположение о том, что мы можем построить H, неверно. Заметьте, что по сути notHaltOnItself является подмножеством not(K), поэтому not(K) не является рекурсивно перечислимым.
Теорема Тьюринга, как и теорема Гёделя (и процедура диагонализации Кантора), многое говорит нам о пределах логики, теории множеств и математики.
Сообщает ли нам теорема Тьюринга (или теорема Гёделя (или мощность множества множеств)) что-нибудь интересное о человеческом разуме, зависит от совершенно другого набора предположений (например, верите ли вы, что сознание зависит от способности перечислять множества, которые не являются рекурсивно перечислимы.)
Ваш вопрос был конкретно о связи между теоремой Тьюринга и «самоорганизацией». Я не вижу связи между способностью к «самоорганизации» и способностью перечислять множества, которые не являются рекурсивно перечислимыми. Мне даже не очевидно, что самоорганизующаяся система должна иметь возможность перечислять все рекурсивно перечислимые множества (и уж точно не любые неконечные рекурсивно перечислимые множества).
Мауро АЛЛЕГРАНСА
Джозеф Вайсман
Джеймс Кингсбери
Эрик Каплун