Новая модель процесса вычислений: обобщение концепции машины Тьюринга icon

Новая модель процесса вычислений: обобщение концепции машины Тьюринга


Смотрите также:
Название Оптический компьютер с голографической памятью...
История развития вычислительных систем достаточно коротка и...
Лекция 4
Алгоритмы и машины Тьюринга Основы алгоритмов...
«Информатика»
Приказ № от года проект перспективного развития школы на основе инициативы «Наша новая школа»...
Программа дисциплины по кафедре «Строительные и дорожные машины» дорожные машины...
05. 13. 15 Вычислительные машины, комплексы и компьютерные сети...
Лекция 14 (15). Размер задач и сложность алгоритмов. Временная и пространственная сложность...
Лекция Введение...
Отчет шмо учителей математики и информатики...
Программа дисциплины по кафедре «Строительные и дорожные машины» дорожно-строительные материалы...



Загрузка...
скачать
УДК 519.712; 519.68

Новая модель процесса вычислений:

обобщение концепции машины Тьюринга

О.Н.Граничин, И.А.Жувикина

Санкт-Петербургский государственный университет


Аннотация: В статье предлагается обобщение концепции классической схемы машины Тьюринга. В новой концепции обобщаются традиционные понятия “лента” и “ячейка памяти”'. В частности, ``ячейка памяти'' представляет собой постоянно функционирующую модель какой-то динамической системы. “Естественная” эволюция ячеек в некоторые моменты времени прерывается “скачками”. Рассматриваемая модель позволяет, например, описывать системы с изменяющейся структурой пространства состояний. Стандартная машина Тьюринга оказывается предельным случаем предлагаемой.


1. Введение

Машина Тьюринга (МТ) - это абстрактное вычислительное устройство, которое было предложено в 1936г. английским математиком А.Тьюрингом [1] в качестве математической модели для описания алгоритмов. Первоначально концепция МТ развивалась с целью ответа на вопрос: можно ли для любого математического утверждения указать конечную последовательность инструкций, которые могли бы выполняться механически одна за другой любым человеком или вычислительным устройством, и в итоге выяснить, истинно это утверждение или ложно. Машина Тьюринга является дискретным вычислительным устройством, изменяющим свои характеристики в определенные моменты времени. Хотя и доказано, что поставленная проблема в общем случае неразрешима, но применение МТ вышло далеко за пределы первоначальной постановки. По существу именно работы Тьюринга положили начало математической теории вычислений. Машина Тьюринга сыграла и продолжает играть важную роль в теории информатики, а вычислимость при помощи машины Тьюринга стала признанным определением процедуры.

В том же самом 1936г. А.Черчем [2] была высказана гипотеза, что любой процесс, который интуитивно мог бы быть назван процедурой, реализуем машиной Тьюринга. Эту гипотезу стали называть тезисом Черча-Тьюринга и обычно формулируют одним из эквивалентных способов [3]:

  • любое эффективное вычисление может быть проведено с помощью МТ.

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

  • Физическая формулировка принципа Черча-Тьюринга: любая конечно реализуемая физическая система может быть достаточно точно смоделирована с помощью универсальной модели компьютера, оперирующего конечными средствами.

    На практике этот набор конечных средств сводится, как правило, к множеству двоичных символов {0,1}, а конечная реализуемость оказывается эквивалентной конечному числу тактов (моментов переключений).

    Д. Дойч [4] предложил модифицировать тезис Черча-Тьюринга следующим образом:

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

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

Хорошо известно, что компьютеры становятся все миниатюрнее и миниатюрнее. Когда-то предполагали, что более мощные машины будут требовать больше места под периферию, память и т.д. Это предположение оказалось неверным. В 1965г. Г.Мур [5] сформулировал действующее и сейчас правило (впоследствии названное законом Мура), согласно которому производительность вычислительных систем удваивается каждые восемнадцать месяцев. Г.Мур вывел свой эмпирический закон, построив зависимость числа транзисторов в интегральной микросхеме от времени. Как следствие, из этого закона можно вывести темпы миниатюризации отдельного транзистора. Развитие цифровых электронных технологий приводит к тому, что размер элементарного вычислительного устройства приближается к размеру молекулы или даже атома. На таком уровне законы классической физики перестают работать и начинают действовать квантовые законы, которые для многих важных динамических задач еще не описаны теоретически. Увеличение быстродействия вычислительных устройств и уменьшение их геометрических размеров с неизбежностью приводит к необходимости операций с переходными процессами.

Вместе с этим физики обратили внимание на важность квантовой механики для информатики и на “экспоненциальное” преимущество квантовых компьютеров над классическими. Р.Фейнман [6] обосновал невозможность представления результатов квантовой механики на классическом универсальном вычислительном устройстве даже с использованием вероятностных алгоритмов. Это связано с тем, что число элементарных операций такого вычислительного устройства будет расти экспоненциально с ростом числа степеней свободы системы. Именно поэтому для точного моделирования квантовых систем Фейнман предложил теоретическую модель квантового компьютера. В информатике в рамках теории сложности алгоритмов получен целый ряд результатов, обосновывающих теоретическую невозможность эффективного решения многих значимых с практической точки зрения задач, в частности, связанных с моделированием естественных процессов в живой и неживой природе. Это означает, что при попытке описания интересующего нас процесса с заданной точностью при помощи машины Тьюринга ее алфавиты состояний и памяти и/или время функционирования оказываются недопустимо велики. Одними из первых с этими теоретическими трудностями столкнулись разработчики систем автоматического управления, которые ведут исследования на стыке информатики и той или иной конкретной научной дисциплины (физики, биологии, химии и т.п.).

В то же время реализации целого ряда современных методов теории автоматического управления не укладываются в рамки дискретной модели. Один из возможных способов ее обобщения - это использование так называемых “гибридных систем”', свойства которых активно изучаются в последнее время. В практике автоматического управления оказалась плодотворной идея релейного регулирования, заключающаяся в переключении системы управления с одного “скользящего”' режима на другой. В последнее десятилетие в системах управления активно внедряется нейросетевой подход. Часто говорят об использовании в управляющих контурах нейрокомпьютеров [7]. Но работа перечисленных устройств не описывается полностью классической схемой машины Тьюринга. Одним из вариантов расширения тезиса Черча-Тьюринга является введение нового понятия вычислительного устройства, в котором вычисления строятся не на традиционных алгоритмах, а на моделях. В [8] уже используются подобные подходы, которые опираются на модели параллельных высокоэффективных вычислений. Следующий естественный шаг - обобщение на модели динамических систем.

Основным (и наиболее спорным с современной точки зрения) понятием дискретной схемы машины Тьюринга является понятие “такт”. Его глубокий противоречивый смысл был замечен еще древними греками. Одна из возможных эквивалентных его формулировок представляет собой знаменитый парадокс Зенона об Ахиллесе и черепахе. В рамках классической теории множеств он выступает в качестве неразрешимости проблемы континуума в рамках аксиоматики Френкеля-Цермело. По мнению современных толкователей Зенон на самом деле стремился доказать, что “логика и здравый смысл несовместимы” и что строгие логические умозаключения неприменимы в реальной жизни.

В [9] предлагается и обосновывается новая абстрактная концепция вычислительного устройства, включающая в себя все перечисленные выше новые подходы. Во многом авторы постарались сохранить традиционный формализм описания классической машины Тьюринга. Новая концепция принципиально отличается от классической включением ``непрерывности'' эволюции и переосмыслением понятий “лента”' и “ячейка памяти”. Если в классическом подходе ячейки памяти используются для хранения дискретной информации и их изменение возможно только в тех случаях, когда указатель ленты показывает на нее, то в новой концепции “ячейка памяти” представляет собой постоянно функционирующую модель какой-то динамической системы (может быть, и достаточно сложной), а “лента” - некоторый “мостик” для задания или переопределения параметров эволюции состояния “ячейки”. Очевидно, что классическая ячейка памяти для хранения “бита” является частным случаем такого обобщения.

В любых современных вычислительных устройствах хранение информации основано на тех или иных физических принципах, только эволюция состояния ячейки во время хранения более простая - сохраняется постоянной какая-то физическая характеристика. Другими словами, традиционную информатику можно сравнить с арифметикой, она оперирует цифрами - значениями ячеек памяти (или, более точно – арифметикой конечных двоичных дробей). Предлагаемая модель вычислений позволит перейти в информатике от “арифметики” к “функциональному анализу”, исследующему процессы эволюции информации внутри новых “ячеек”.

В 60-е годы прошлого века на фоне бурного прогресса электроники в области развития технологий производства сверхбольших интегральных схем (СБИС) кибернетики обещали со дня на день дать решение задачи создания ``искусственного интеллекта''. Однако наступившее вскоре разочарование было связано с практической неразрешенностью вопроса о возможности его создания. Более того, многие современные исследования показывают бесперспективность работ в этом направлении с использованием классической машины Тьюринга. В некотором смысле можно говорить о дискредитации самого термина “искусственный интеллект”. Вероятнее всего существенного прогресса в понимании точной постановки и путей решения задачи создания искусственного интеллекта не удастся достичь без переосмысления традиционного ответа на вопрос: что же такое процесс вычислений и что такое результат вычисления?

^ 2. Вычислимость и вычислимый объект

К настоящему времени накоплено достаточное количество примеров, доказывающих иллюзорность убеждения в том, что решение сложной динамической задачи с наперед заданной точностью можно получить, используя классическую машину Тьюринга [10]. В астрономии законы, управляющие движением небесных тел хорошо известны – это закон тяготения Ньютона или уточняющие его уравнения Эйнштейна. Казалось бы, чем более точно мы задаем начальные условия – положения и скорости небесных тел в начальный момент времени и чем мельче делаем шаг по времени при машинном интегрировании уравнений движений, тем точнее мы можем предсказывать поведение системы в будущем. Однако, на этом пути до сих пор не удается ответить даже на фундаментальный вопрос об устойчивости Солнечной системы на больших временах. Это означает, что даже малая неизбежная неточность начальных данных делает поведение системы непредсказуемым: видимая простота уравнений движения, тем не менее, скрывает их неинтегрируемость, любая малая неточность в начальных условиях очень сильно влияет на последующую эволюцию.

Другой пример из биологии показывает, что даже точное задание начальных условий отнюдь не гарантирует решения динамической задачи. Как известно, экспоненциальный характер изменения численности популяции какого-либо биологического вида при постоянном коэффициенте ее прироста справедлив лишь при отсутствии пределов роста популяции (например, при неограниченном запасе пищи и отсутствии внешних врагов). При наличии пределов роста численность популяции через лет при начальном значении удовлетворяет следующему уравнению (процесс Ферхюльста)

,

где - константа, связанная с коэффициентом прироста популяции за год. Оказывается, что поведение системы, подчиняющейся такому уравнению, предсказуемо лишь при малых значениях величины . При численность популяции начинает периодически осциллировать между двумя значениями 0 и 1. При дальнейшем росте величины характер поведения численности популяции усложняется. Сначала начинаются колебания численности между четырьмя характерными значениями с удвоенным периодом, далее – количество значений, между которыми происходят колебания численности популяции, удваивается вместе с удвоением периода колебания. Наконец, при процесс перестает быть периодическим – происходят перескоки численности между бесконечно большим количеством значений. Таким образом, предсказание поведения системы оказывается невозможным, несмотря на полную ее детерминированность и определенность начальных условий. Поведения носит хаотический характер, т.е. не существует способа предсказать развитие системы на длительное время. Причиной этого является нелинейность уравнения, описывающего процесс Ферхюльста.

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

В последние десятилетия этот подход вызвал непреодолимые трудности при описании конкретных природных систем, а именно, т.н. «сложных систем». К ним относятся, в частности, материальные среды, имеющие сложную, в некотором смысле патологическую, морфологию – пористые, ветвящиеся, чешуйчатые, коллоидные среды и т.п. В качестве конкретных принципиальных трудностей, возникающих при их описании, упомянем расходимость термодинамического давления в очень мелких порах, невозможность найти площадь сильно развитой поверхности геля: чем мельче берется масштаб измерения, тем больше получается искомая величина. Аналогичные трудности возникают при измерении длины береговой линии или определении объема облака. Такие системы получили названия фракталов [10], они являются промежуточными объектами между точкой и линией, линией и поверхностью, поверхностью и объемом. В [11] обсуждаются трудности формального описания динамических «переходных» процессов в системах, возникающих при быстром изменении «внешних» условий. Обычные подходы к описанию таких неравновесных процессов неэффективны, поскольку сама структура пространства состояний зависит от времени. Многие экспериментальные наблюдения за протеканием неравновесных процессов подтверждает зарождение в системе новых структур мезоскопического (промежуточного между микро и макро) масштаба, которые в значительной степени и определяют динамическое изменение типа формальной модели. Примерами такого рода структурообразования могут служить: кластеризация в потоках концентрированных дисперсных смесей, образование многомасштабных вихревых структур в турбулентных течениях жидкости и пластических течениях твердых материалов при импульсном нагружении, а также иерархии структур в живых системах. В настоящее время известно, что синергетические процессы формирования динамических структур мезоскопического масштаба в открытых термодинамических системах связаны с возникновением информационно-управленческой обратной связи, внутреннего управления, которое вместе с внешним управлением через наложенные на систему граничные условия и приводит к дискретизации пространства и времени неравновесной системы. При этом физическими носителями информации являются элементы динамических структур.

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

В предлагаемом далее новом подходе считается, что сложность вычислимого объекта должна быть эквивалентна сложности изучаемого реального объекта и адекватно отражать его свойства. Для перечисленных выше материальных сред это будет способность течь, изменять форму, сжиматься – растягиваться, дробиться – сливаться. Для этого необходимо использовать математическую модель материальной среды, основанную на более слабых, по сравнению с требованием быть системой изолированных точек или жордановой областью, требованиях. А именно, моделирующее множество должно быть замкнутым (т.е. содержать все свои предельные точки) и плотным в себе (т.е. каждая его точка должна быть предельной). Совместное выполнение этих свойств эквивалентно свойству быть совершенным множеством. Существует много типов совершенных множеств, среди которых есть регулярные, поддающиеся формальному построению и описанию, [12]. Некоторые из совершенных множеств имеют свойства в строго определенном смысле близкие к свойствам множеств изолированных точек, а некоторые – к свойствам жордановых областей. В промежуточных случаях они хорошо отражают свойства фракталов и являются измеримыми в смысле p-меры Хаусдорфа [13]. Перспективность применения понятия размерности Хаусдорфа обусловлена тем, что эта размерность, рассматриваемая как текущая непрерывная переменная, может быть характеристикой, описывающей эволюцию сложной системы как целого, включая диссипацию энергии [14-16], в то время как топологическая размерность Урысона–Менгера в процессе изменения реальной системы, как правило, остается постоянной [13, 17-19].

Более того, требует обобщение и само понятие вычислимости. Сначала проиллюстрируем это рядом примеров.

Пример 1. Корень квадратный из 2. По определению, v2 равен длине диагонали единичного квадрата. Считаем, что это число вычислено, если построен единичный квадрат. Будем говорить, что сложность числа v2 равна сложности единичного квадрата. Единичный квадрат назовем вычислительным примитивом для v2 и арифметически связанных с ним иррациональных чисел.

Пример 2. Число π. Вспомним его определение – отношение длины любой окружности к ее диаметру. Будем считать, что число π вычислено, если построена единичная окружность. Сложность числа π равна сложности единичной окружности. Единичная окружность есть вычислительный примитив для чисел, арифметически связанных с числом π.

Пример 3. Измерение снежинки. Снежинка представляет собой вписанный в окружность радиуса 1 сантиметр фрактал с заданной морфологией и хаусдорфовой размерности 5/2 с шестью лучами.

В качестве размера снежинки принимаем величину . Ôðàêòàë äàííîé ðàçìåðíîñòè è ìîðôîëîãèè ÿâëÿåòñÿ âû÷èñëèòåëüíûì ïðèìèòèâîì äëÿ èçìåðåíèÿ ñíåæèíêè. Ìàòåìàòè÷åñêèé àíàëèç ïðèãîäíûé äëÿ îïèñàíèÿ îáúåêòîâ ñ íåöåëîé ðàçìåðíîñòüþ, íà÷èíàÿ ñ ðàáîò

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


^ 3. Обобщенная модель машины Тьюринга

Следуя [9], будем рассматривать обобщенную машину Тьюринга как некоторую структуру, в которой – обобщенное множество состояний МТ; - текущее состояние; - состояние в начальный момент времени; - лента (память); - множество состояний памяти; - текущее содержимое памяти: ; - начальное содержимое памяти; терминальное множество , где – множество всевозможных наборов состояний и памяти; множество задания программы, причем ; - программа; оператор эволюции состояний и памяти.

Алгоритм работы обобщенной МТ описывается следующим образом: в любой момент времени , если набор из состояния и памяти МТ попадает в терминальное множество , то машина останавливается, если , то в эволюции обобщенной МТ происходит «скачок»: , в остальных случаях состояние и память обобщенной МТ «естественно» (например, непрерывно) эволюционируют, и этот процесс определяется оператором . Другими словами, изменения состояния и памяти обобщенной МТ происходят как в гибридных системах. Обычно они эволюционируют согласно некоторому закону, а в определенные моменты времени, задаваемые достижением некоторых подмножеств пространства , происходят скачкообразные изменения состояния и памяти.

Покажем, как в обобщенном виде можно записать классическую МТ , у которой - конечный алфавит состояний классической МТ; - лента (набор положений головки чтения/записи соответствующих рабочим ячейкам памяти); вторая компонента состояния соответствует номеру текущей рабочей ячейки памяти (положению головки чтения/записи); - номер начальной ячейки памяти; - конечный алфавит состояний памяти; , ; программа - это отображение, определенное для пар : (состояние, значение памяти в рабочей ячейке); - тождественный оператор; алгоритм работы: на каждом такте, если , то машина останавливается, если , то состояние МТ меняется на , а содержимое памяти в рабочей ячейке либо изменяется на , если , либо остается прежним при . В последнем случае вместо изменения содержимого памяти происходит сдвиг влево или вправо текущей рабочей ячейки: . В качестве пространства состояний можно выбрать: , при этом третья компонента соответствует доли времени внутри такта длиной ;; множества и те же; терминальное множество ; аналогично можно определить ; при этом программа обобщенной МТ на задается по правилу: ; оператор равномерно изменяет , и является тождественным для остальных компонент.

Заметим, что можно было бы момент останова машины определять только значением состояния, но введенное более общее правило, очевидно, включает в себя и этот случай. В новой модели исключено понятие рабочей ячейки, т.е. изменение состояния может зависеть от содержимого всей памяти в данный момент, а содержимое памяти может меняться одновременно на всем пространстве . Разделение описания процесса изменения состояния и памяти на две составляющие: программу и эволюцию , на первый взгляд, может показаться искусственным. На самом деле, вводя такое разделение, хочется сразу же размежевать “принудительные” изменения, обычно вносимые в систему извне, задаваемые кем-то “осознанно”, и те “естественные” процессы, которые происходят в определенной физической (или биологической) системе в силу законов природы.

Важным обобщением классической МТ является вычислительная схема, которую можно назвать «набор моделей». Пусть - это множество машин Тьюринга без программы (набор моделей), т.е. мы считаем, что каждая ячейка памяти представляет собой отдельное устройство (квантовый или аналоговый компьютер, нейронная сеть, некоторая динамическая система), решающее свою собственную задачу. Таких устройств может быть конечное или бесконечное число. Заметим, что обычную ячейку памяти с целыми значениями тоже можно считать машиной Тьюринга с одной ячейкой памяти и тождественной эволюцией. В отличие от классической МТ в наборе моделей изменение состояния памяти может происходить непрерывно и параллельно во всех ячейках.

Другим обобщением машины Тьюринга может быть вероятностное задание отображений и , что позволит реализовывать с помощью новой модели динамические системы, не описываемые детерминированными законами, а также стохастические гибридные системы, вероятностные автоматы, системы со стохастическим управлением и т.п. Кроме того, в [11] показан пример эффективности использования рандомизированных программных воздействий на систему в условиях динамически изменяющейся структуры пространства состояний. Рандомизация позволяет частично устранить влияние на работу системы систематических погрешностей [20,21], которые практически неизбежны при изменяющейся со временем модели динамической системы.


4. Выводы

Предложенная новая модель вычислений позволяет описывать если не все, то подавляющее большинство процессов, происходящих в реальном мире, а также работу всевозможных существующих и будущих вычислительных устройств, включая аналоговые и биокомпьютеры, нейрокомпьютеры, квантовые компьютеры и т.д. Особенностью предлагаемого подхода является отказ от редукции сложности в процессе вычисления. Сложность вычислимого объекта должна быть эквивалентна сложности вычисляемого. Таким образом, понятие вычислительной сложности правильнее рассматривать относительно выбранной системы базисных эволюционных примитивов, а не относительно традиционно рассматриваемых битовых преобразований {0,1}. Квантовые и нейрокомпьютеры обещают сильно изменить представления о вычислительной мощности современных вычислительных устройств. Увеличение вычислительной мощности, возможное за счет использования новых моделей вычислений, основывающихся на физических явлениях, позволяет предположить, что в будущем новые компьютеры смогут решать задачи, невыполнимые для обычных компьютеров.


Список литературы[1] Turing, A.M., 1936-7. “On Computable Numbers, With an Application to the Entscheidungsproblem”, Proceedings of the London Mathematical Society, (2) 42, pp. 230-265; correction ibid. 43, pp. 544-546 (1937).

[2] Church, A., 1936. “A note on the Entscheidung problem”, Journal of Symbolic Logic, 1, pp. 56-68.

[3] Copeland, J.B. “The Church-Turing Thesis”. NeuroQuantology,. 2004, (2), pp.101-115

[4] Deutsch, D. 1985. “Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer”. Proceedings of the Royal Society, Series A, 400, pp. 97-117.

[5] Moore, H., Electronics. 38. 1965. 8. April 19.

[6] Feynman, R., “Modeling of physics on computers” International Journal of Theoretical Physics. 21. 1982. 6/7.

[7] Терехов В.А., Тюкин И.Ю. “Синтез адаптивных нейросетевых регуляторов нелинейных динамических объектов”. В сб. “Стохастическая оптимизация в информатике”, под ред. О.Н.Граничина. Изд-во С.-Петерб. ун-та. 2005, с. 222-256.

[8] Нариньяни А.С. “Модель или алгоритм: новая парадигма информационных технологий”. Российский НИИ ИИ. 2004.

[9] Владимирович А.Г., Граничин О.Н. “Обобщение концепции машины Тьюринга”. В сб. трудов конф. «УИТ-2005». 2005, т. 2, с.-.

[10] Пайтген Х.-О., Рихтер П.Х. “Красота фракталов. Образы комплексных динамических систем.” Москва: Мир, 1993, 176 с.

[11] Granichin O.N., Khantuleva T.A. “Hybrid systems and randomized

measuring in nonequilibrium processes”. Differential Equation and Control Processes. (3). 2004. Electronic J. N P23275 at 07.03.97.

[12] Жувикина И.А. “Анализ сложных материальных систем на основе Р-меры Хаусдорфа”. Проблемы управления безопасностью сложных систем. Материалы VII ìåæä. êîíô. Ì., 1999, ñ.31-33.

[13] Hausdorff, F. “Dimnsion und ausseres”. Math. Ann. 1919, 79.

[14] Zhuvikina, I.A., “Evolutions of mesostructures: from microscopics to hydrodynamics”. Proc. of the 2nd International Arctic seminar, Physics and Mathematcs, Murmansk, 1997, pp. 127-132

[15] Zhuvikina, I.A., “Hausdorff dimentionality as bridging the gap between the domains of discretness and of continuity”. Proc. of the 3rd International Arctic seminar, ^ Physics and Mathematcs, Murmansk,, 1998, pp. 143-147.

[16] Zhuvikina, I.A., “Additive variables, p-densities and the conservation laws”. Proc. of the 3rd International Arctic seminar, Physics and Mathematcs, Murmansk, 1998, pp. 148-152.

[17] Толстов Г.П. Мера и интеграл. М.: Наука, 1976, 392 с.

[18] Hurewics, W. , Wallman, H., Dimension theory, 1941.

[19] Самко С.Г., Килбас А.А., Маричев О.И. “Интегралы и производные дробных порядков и некоторые их приложения”. Минск: Наука и техника, 1987, 688 с.

[20] Граничин О.Н., Поляк Б.Т. “Рандомизированные алгоритмы оценивания и оптимизации при почти произвольных помехах”. М.:Íàóêà, 2003. 291ñ.

[21] Granichin O.N. “Linear regression and filtering under nonstandard assumptions (Arbitrary noise)”. Trans. on AC, 2004, Vol. 49, Oct. (10), pp. 1830-1835.

^ New computational model based on evolution primitives:

generalization of the Turing machine concepts

O.N.Granichin, I.A.Zhuvikina

St. Petersburg State University


Abstract: À generalization of the Turing machine concepts based on evolution primitives is proposed. The new concept extends the classical terms: “tape” and “cell”. In particularly, the new “cell” is a functioning dynamical system. The natural evolution is broken by “jumps” sometimes. The considered model allows one to describe dynamical systems in phase spaces with changing structures. The classical Turing machine is a particular case of the proposed one.

^ Сведения об авторах:

1. Граничин Олег Николаевич,

1961 г.р., доктор физ.-мат. наук, доцент, профессор кафедры системного программирования математико-механического факультета СПбГУ.

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

Сл. адрес: 199034, С.-Петербург, Университетская наб. д.7/9, тел. 428-71-09.

Дом. адрес: 199226, С.-Петербург, Новосмоленская наб. д.8, кв. 105, тел. 323-01-99.

2. Жувикина Ирина Алексеевна,

1960 г.р., кандидат физ.-мат. наук, гл. специалист УНИ СПбГУ.

Научные интересы: статистическая физика, теория сложных систем.

Сл. адрес: 199034, С.-Петербург, Университетская наб. д.7/9, тел. 328-94-95.

Дом. адрес: 197372, С.-Петербург, Комендантский пр., д.20, корп.3, кв. 15, тел. 349-23-47.




Скачать 191.81 Kb.
оставить комментарий
Дата29.09.2011
Размер191.81 Kb.
ТипДокументы, Образовательные материалы
Добавить документ в свой блог или на сайт

Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх