Абстрактная модель невычислимости
Кто ищет, вынужден блуждать.
Иоганн Вольфганг Гёте
Мы, как будто согласились с тем, что абстрактной моделью вычислимости является машина Тьюринга, а сами говорим больше о невычислимости. Закономерен вопрос – что является абстрактной моделью невычислимости? Тоже машина Тьюринга? Но для невычислимых проблем машины Тьюринга не существует. Как же быть? Может быть, «изобрести» некую «машину Немо»? Я думаю, что необходимости ждать появления творца «машины невычислимости» нет, ибо далеко не все еще «вычерпано» из существа машины Тьюринга. В самом деле, глядя на таблицу любой машины Тьюринга, нетрудно сообразить, что на самом деле не всякая, «наобум» заполненная символами таблица являет собой «машину», которая решает какую-то задачу.
Известный американский кибернетик М.Минский (его имя мы уже упоминали) в одной из своих работ писал, что можно «сочинить» множество «машин Тьюринга», которые ничего не делают, или делают совсем не то, что нужно. Под этим он понимал, что произвольно заполненная таблица может соответствовать «сочиненной машине», выполняющей с лентой всевозможные «выкрутасы». Перечислим, следуя за М.Минским, некоторые из них. Головка машины никуда не двигается и, следовательно, информация на ленте машины не изменяется (машина ничего не вычисляет). Головка может на ленте стереть всю исходную информацию. Головка может сместиться в самый левый или самый край ленты и там остаться. Образно выражаясь, если бы лента имела бесконечную длину, то головка стремилась бы уйти в «левую» или «правую» бесконечность. Головка никогда не останавливается, «выписывая» на ограниченном участке ленты бесконечные циклы. Наверное, можно придумать еще какие-то «несуразности». Дело не в этом, а в том – как называть такую испорченную машину Тьюринга. А так и будем называть – «испорченная машина Тьюринга». Можно ИМТ, хотя, разумеется, такого, официально признанного термина, нет. Может быть, ИМТ и является абстрактной моделью невычислимости? Попробуем разобраться.
С этого места текста я должен прибегнуть к ряду терминов и знаний, взятых из научной дисциплины, имеющей название теория автоматов. Читатель не знакомый с этой теорией и не желающий с ней знакомиться (самые элементарные сведения этой теории я здесь все-таки изложу) может весь дальнейший материал этого раздела пропустить без ущерба для понимания дальнейших частей книги. Помещаю же я соображения по поводу ИМТ и кое-чего из теории автоматов исключительно ради дополнительной строгости обоснования предлагаемой мной идеи о сущности человеческого сознания.
Для начала – сведения, самые, что самые ни на есть про автоматы элементарнейшие. И не про автоматы вообще, а про абстрактное представление автомата (так будет проще говорить об ИМТ). Вспомним вполне исправную машину Тьюринга, инвертирующую двоичный код. Нетрудно вообразить (а воображать не нужно, ибо такие автоматы на самом деле являются одной из составных частей любого компьютера) устройство из электронных элементов, на вход которого подается электрический потенциал, скажем, 1 вольт (логическая единица), а на выходе снимается потенциал 0 вольт (логический нуль). И наоборот – логический нуль (0 вольт) на выходе преобразуется в логическую единицу (1 вольт).
Прежде чем изготавливать такой автомат, как это принято говорить в среде соответствующих специалистов, «в железе», удобно принцип его функционирования записать в форме двух таблиц (можно – и одной, но на подобную «мелочь» отвлекаться не будем). Таблицы имеют название – таблица переходов и таблица выходов. Для нашей задачи инвертирования двоичного кода названные две таблицы изображены ниже.
Таблица выходов инвертора
|
|
q0 |
q1 |
|
0 |
1 |
0 |
|
1 |
0 |
1 |
|
l |
l |
l |
Таблица переходов инвертора
|
|
q0 |
q1 |
|
0 |
q0 |
q1 |
|
1 |
q0 |
q1 |
|
l |
q1 |
q2 |
Таблицам следует дать некоторое пояснение. В таблице выходов ясно – находясь в состоянии q0, наш автомат 0 преобразует в 1, 1 – в 0. Находясь в состоянии q1, автомат входную информацию не изменяет. Если же на вход автомата никакой информации не поступает, то автомат и на выходе никакой информации нет. В таблица переходов автомата при выбранной нами интерпретации ни на входной 0, ни на входную 1 состояние автомата не изменяется, а когда на вход автомата ничего не подается, он оказывается в состоянии останова (q2). Можно, конечно, выбрать иную интерпретацию перехода от машины Тьюринга к абстрактному автомату, но нас устраивает и такая.
В теории автоматов часто принято изображать работу автомата в виде так называемого графа. Граф работы нашего инвертора представлен на рис. 1.
Рис.1 Граф инвертора
Из рассмотрения рисунка мы тоже, как из анализа таблиц выхода и перехода инвертора, видим, что при входных сигналах 0, 1 он «исправно» пребывает в состояниях q0 или q1, когда же на вход ничего не подается, он останавливается (q2).
Итак, об автоматах мы немного пояснили, а теперь вопрос – зачем нам понадобилось от машины Тьюринга переходить к абстрактному автомату? Ответ на вопрос в том, что абстрактный автомат несколько «ближе» к реальному (не абстрактному) устройству, чем машина Тьюринга. Поэтому по «поведению» автомата удобнее смотреть на эту самую невычислимость. Здесь – мостик к мозгу, конечно, очень шаткий. Мы уже достаточно часто упоминали о невычислимости сознания, значит, это как-то связано с невычислимостью мозга. Разумеется, мозг – не автомат, но все-таки, что бы могло происходить там, в мозге, чтобы проявлять, так интересную нам невычислимость? Читатель понимает, что никаких данных о физиологических процессах в мозге мы таким путем не получим – лишь кое-что о далеко неясных еще принципах преобразования информации в мозге. Тут, как ни странно, нам придется из машины Тьюринга делать ИМТ, т.е. ломать машину Тьюринга, а далее – смотреть, что же ломается в соответствующем этой ИМТ абстрактном автомате. Но перед этим следует разобраться, какие «поломки» (хотя бы кратко) сознания нам известны. Потерпим, так как об этом – в следующем разделе.
