WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 | 5 |   ...   | 8 |

Каминский А.В.

АЛГОРИТМИЧЕСКАЯ МОДЕЛЬ МИРА Человек издавна пытается понять, что есть Мир, и осознать свое место в нем. С тех пор, когда Мир представлялся человеку опирающимся на трех слонов, наши знания значительно умножились, а модели мироздания усложнились. Однако, истина по мере приближения к ней отступает, заставляя нас задумываться о ее достижимости и о самой сущности этого понятия.

Вопрос познаваемости Мира определяется его моделью. Научное изучение этого вопроса становится возможным при переносе формализованного в математической логике понятия истины на физический мир.

Примечание: Как известно, истинным высказыванием математики называют замкнутую (не имеющую свободных вхождений переменных) формулу алгебры предикатов, полученную согласно правилам  вывода "modus ponens" из схемы аксиом, принятых "ad hoc". Истина физического мира так же представляет собой логический конструкт, собранный из ряда утверждений, называемых законами природы.

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

Примечание: Речь идет о теореме Геделя о неполноте формальной арифметики и ее усилении теореме Тарского о невыразимости понятия истины.

Для такой модели Мира агностицизм строгое следствие ее свойств. Здесь необходимо рассмотреть подробнее и уточнить, что означает моделирование физического мира исчислением. Учитывая, что исчисление всегда может быть заменено алгоритмом, результатами которого служат объекты, порождаемые исчислением, в дальнейшем мы будем говорить об алгоритмическом описании Мира.

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

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

Примечание: A.M.Turing. On Computable Numbers...Proc.London Math. Soc.,42 (19361937), p. 230265,(В своей знаменитой статье А.М.Тьюринг предложил "машину" весьма простого рода, способную напечатать в соответствующем алфавите разложение любого вычислимого действительного числа. Он пояснил так же каким образом такая машина могла бы вывести все формулы исчисления предикатов.) Алгоритм в обычном понимании представляет собой конечную процедуру обработки конечных слов. Хотя множество его входов может быть счетнобесконечным. Физика дважды уже "спотыкалась" о допущения бесконечности того, что на самом деле не было бесконечным (cскорость света, 1/hобратная постоянной Планка). Д.Гильберт писал "Бесконечное нигде не реализуется, его нет в природе, и оно недопустимо как основа нашего разумного мышления". Кронекер по этому поводу говорил, что Бог создал натуральные числа, а все остальное дело рук человеческих.

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

Глава 1. Алгоритмическая модель 1.1 Обратимые и необратимые алгоритмы.

Предположим, что в основе физического мира лежат элементарные (не имеющие структуры) фундаментальные ячейки, представляющие собой первичную сущность и поэтому требующие введения "ad hoc". Ячейки эти аналогично ячейкам конечного автомата могут быть активны (1) или пассивны (0). Над полем этих ячеек действует алгоритм, который отражает структуру Мира и определяет его развитие. Далее этот алгоритм будем называть Мировым алгоритмом, либо просто Алгоритмом, выделяя первой прописной буквой. Он связывает фундаментальные ячейки в систему.



Если N число фудаментальных ячеек, то число состояний Мира будет 2N. Если строить модель типа машины Тьюринга, то внутренние состояния машины должны быть включены в это число. Для дальнейшего нам понадобится выделить два больших класса алгоритмов.

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

Рассмотрим машину Тьюринга, действующую на алфавите A={0,1} с набором внутренних состояний S={Si}. Напомним, что поведение машины Тьюринга определяется символом напротив считывающей головки и ее внутренним состоянием. При этом считанный знак и внутреннее состояние заменяются новыми, а головка передвигается в направлении D=(R,0,L) (на одну позицию в одном, либо другом направлении или остается неподвижной). Коротко, поведение машины Тьюринга может быть описано тремя функциями с областями значений из A,S, определенными на множестве {A S}. Соответственно программу будем записывать в виде набора строк в формате: {A S} ASD   пример 1. Программа:

  0S1 0S1R   1S1 1S1R описывает "прозрачную" машину Тьюринга, не производящую никаких действий, двигаясь по ленте в любом направлении. R означает движение "печатающей" головки направо, L налево Будем считать, что замена R на L и обратно эквивалентна замене знака времени на противоположный. В качестве следующего примера приведем программу, сдвигающую информацию на ленте на одну позицию вправо:

  пример 2.

  0S1 0S1R   1S1 0S2R   0S2 1S1R   1S2 1S2R Перед тем, как проанализировать работу этих программ, приведем примеры необратимых машин Тьюринга.

пример 3. Программа:

  0S1 0S1R   1S1 0S2R   0S2 1S3R   1S2 1S2R   1S3 1S3R   0S3 0S3R складывает два числа, представленные в единичной системе счисления (алфавит A={1}). И последний пример:

  пример 4.

  0S1 0S1R   1S1 0S1R программа, стирающая информацию с ленты при движении в любом направлении.

  Будем считать, что машина Тьюринга обратима, если при изменении знака времени t t машина возвращается в исходное состояние, проходя через ту же последовательность состояний в обратном порядке. В противном случае машина Тьюринга необратима. Еще раз напомним, что под состоянием следует понимать полное состояние системы, а именно, внутренние состояния в совокупности с информацией на ленте. Из рассмотренных примеров видно, что необратимость возникает вследствие потери информации. Так, машина из примера 4 является простейшей необратимой машиной, необратимость в которой возникает вследствие уничтожения информации на ленте. Необратимость машины из примера 3 имеет более сложное происхождение. В этом случае причиной необратимости является потеря информации о том, из каких слагаемых получается сумма. Следует заметить, что стирание информации с ленты еще не означает потерю этой информации, так как она может быть сохранена во внутренних состояниях машины. Именно это имеет место в примере 2. Здесь стирание единицы всегда сопровождается переходом из состояния S1 в состояние S2. В общем случае каждое следущее состояние машины Тьюринга не содержит информации о предыдущих, поэтому в процессе работы алгоритма она может теряться. Так, например, вход в бесконечный цикл также сопровождается потерей информации. Действительно, в точке входа в цикл невозможно определить предыдущее состояние алгоритма.

Вернемся к примеру 1. Алгоритм описывает движение головки слева направо независимо от встречающихся символов. Этот алгоритм обратим, так как на любом шаге может быть определено предыдущее состояние. Действительно, согласно программе, каждое состояние (определяемое в данном случае положением головки и считываемым знаком) определено однозначно и возникает из состояния, в котором головка расположена на одну позицию левее.

  Пример 5. Программа:

  0S1 0S1R   1S1 1S1L описывает движение головки слева направо до первой встретившейся единицы, после чего машина попадает в бесконечный цикл. Как уже отмечалось, в точке входа в цикл имеет место неоднозначность в определении предыдущего состояния. Действительно, нет средств оределить, произошел ли вход в цикл на предыдущем шаге. Следовательно, эта программа описывает необратимый алгоритм. Обычно, алгоритм понимается, как процедура преобразования слова "А" в слово "В" за конечное число шагов. Но возможны алгоритмы, имеющие начальное или конечное состояния в бесконечности или не имеющие таковых вообще. Рассмотрим алгоритм из "x" в "y", где "x" множество входов а "y" множество выходов. Пусть, A оператор определяющий локальное преобразование информации в алгоритмическом процессе. Пусть, на входе алгоритма имеется состояние F0(x), тогда состояние алгоритмического процесса на iом шаге вычисляется по стандартной схеме рекурсии:





  Fi(x)=A FI1(x)   Состояние через n итераций будет   Y=Fn(x)=A(A(A(A(F0(x))=AnF0(x)   Предположим, что рассматриваемый алгоритм для значений xl и xm входного множества на kом шаге генерирует одно и то же состояние:

  Ak(xl)=Ak(xm)   Заметим, что, так как алгоритм однозначно определяет каждое последующее состояние на основании предыдущего, то и две рассматриваемые рекурсивные последовательности, начинающиеся со значений xl и xm при i>k, сольются в одну. Пусть, теперь A1 обратное преобразование:

  FI1(x)=A1 FI(x)   То есть AA1=1; Очевидно, что для рассматриваемого примера в точке, описываемой состоянием Fk(xl)=Fk(xm), такого оператора не существует, так как переход к предыдущему состоянию неоднозначен. Это позволяет нам дать более строгое понятие обратимости алгоритма:

Алгоритм обратим в точке (на этом шаге вычислений), если наряду с локальным оператором A в этой точке существует обратный ему оператор A1 такой, что AA1=1; и обратно:

Алгоритм необратим, если для него не существует A Сформулируем следующую очевидную теорему:

  Алгоритм A(xy), биективно отражающий множество входов на множество выходов, всегда обратим.

Алгоритм с сурьективным отображением входов на выходы необратим.

  Введем несколько полезных для дальнейшего изложения определений.

Назовем алгоритм открытым, если для элемента из некоторого множества входов "X" за конечное число шагов он генерирует элемент из множества выходов "Y". Может оказаться, что алгоритм не генерирует выходных значений. Это может иметь место в случае попадания в бесконечный цикл, либо отсутствия решений за конечное число итераций. Такой алгоритм имеет входы, но его выходное множество пусто. Назовем его полузакрытым. Такой алгоритм всегда необратим. Третий тип объектов, которые едва ли подходят под традиционное определение алгоритма, будем называть закрытыми алгоритмами. Такие алгоритмы не имеют ни входов ни выходов. Примером такого объекта является зацикленная часть полузакрытого алгоритма. На рис 1. приведены графы рассмотренных типов алгоритмов, иллюстрирующие приведенную выше классификацию.

Характерной особенностью необратимых алгоритмов является наличие "вилок" в графах их состояний. Узлы этих "вилок" связывают 3 или более состояний, из которых только одно состояние лежит в "будущем", тогда как все остальные в "прошлом". Узел связывает эти состояния в структуру "вилки". Каждое состояние (узел) обратимого алгоритма связывает только 2 состояния, одно из которых предыдущее, а другое последующее.

Точки входа "X" и выхода "Y" интуитивно понимаются, как особые состояния, не имеющие предыдущего и последующего состояний соответственно. Не будем рассматривать класс открытых и полуоткрытых алгоритмов в качестве серьезного кандидата на роль космологической модели именно ввиду наличия этих особых состояний (творение и конец Мира), нарушающих общую симметрию и красоту модели, хотя трудно привести более серьезные аргументы. Таким образом, исключая открытые и полуоткрытые алгоритмы, и исключив тем самым из рассмотрения необратимые алгоритмы, мы остановимся на изучении закрытых обратимых алгоритмов. Топологически такой алгоритм представляет собой замкнутую,несамопересекающуюся структуру с конечным числом состояний, каждое из которых связано только с двумя соседними состояниями.

Примечание: Естественно было бы при построении модели физического мира использовать класс необратимых алгоритмов. Это позволило бы достаточно естественно решить проблему энтропии. Однако, как будет ясно из дальнейшего изложения, этот путь ошибочен.

Сформулируем еще одну очевидную теорему:

Pages:     || 2 | 3 | 4 | 5 |   ...   | 8 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.