Автор: Mark Burgin
Автор перевода: Е. А. Корнеева
Источник (англ.): Triadic Automata and Machines as Information Transformers
Анотация: Алгоритмы и абстрактные автоматы (абстрактные машины) используются для описания, моделирования, исследования и улучшения компьютеров, сотовых телефонов, компьютерных сетей, таких как Интернет, и процессов в них. Традиционные модели систем обработки информации – абстрактные автоматы – нацелены на выполнение преобразований данных. Эти преобразования выполняются их аппаратным обеспечением (абстрактными устройствами) и управляются их программным обеспечением (программами), оба из которых остаются неизменными в течение всего вычислительного процесса. Однако на физических компьютерах их программное обеспечение также изменяется с помощью специальных инструментов, таких как интерпретаторы, компиляторы, оптимизаторы и переводчики. Кроме того, люди меняют аппаратное обеспечение своих компьютеров, увеличивая объем внешней памяти. Более того, Аппаратное обеспечение компьютерных сетей непрерывно изменяется – добавляются новые компьютеры и другие устройства, в то время как другие компьютеры и другие устройства отключаются. Чтобы лучше представить эти особенности компьютеров и компьютерных сетей, мы вводим и изучаем более полную модель вычислений, которая называется триадическим автоматом или машиной. В отличие от традиционных моделей вычислений, триадные автоматы (машина) выполняют вычислительные процессы, преобразующие не только данные, но также оборудование и программы, управляющие преобразованием данных. Кроме того, мы продолжаем развивать таксономию классов автоматов и машин, а также отдельных автоматов и машин в соответствии с информацией, которую они производят. мы вводим и изучаем более полную модель вычислений, которая называется триадным автоматом или машиной. В отличие от традиционных моделей вычислений, триадные автоматы (машина) выполняют вычислительные процессы, преобразующие не только данные, но также оборудование и программы, управляющие преобразованием данных. Кроме того, мы продолжаем развивать таксономию классов автоматов и машин, а также отдельных автоматов и машин в соответствии с производимой ими информацией. мы вводим и изучаем более полную модель вычислений, которая называется триадным автоматом или машиной. В отличие от традиционных моделей вычислений, триадные автоматы (машина) выполняют вычислительные процессы, преобразующие не только данные, но также оборудование и программы, управляющие преобразованием данных. Кроме того, мы продолжаем развивать таксономию классов автоматов и машин, а также отдельных автоматов и машин в соответствии с производимой ими информацией.
Ключевые слова: Информация; автомат; машина; оборудование; программное обеспечение; модификация; процесс; индуктивный; рекурсивный; суперрекурсивный; эквивалентность
Хорошо известно, что компьютеры обрабатывают информацию. В то же время они также являются контейнерами или носителями информации. Вот почему так важно изучать свойства компьютеров и компьютерных сетей с информационной точки зрения. Чтобы сделать это эффективно, исследователям нужны адекватные модели компьютеров и компьютерных сетей. Многие свойства компьютеров, компьютерных сетей и вычислений хорошо представлены в обычных моделях автоматов и алгоритмов. Однако есть еще объекты, требующие новых моделей.
Традиционно вычисление рассматривается как преобразование данных, которое изменяет информацию, содержащуюся в данных, и создает новую информацию. В то же время у компьютеров и компьютерных сетей были важные черты, которые отсутствовали в традиционных моделях. Например, большинство этих моделей не имеют систем ввода и вывода. Отсутствие этих систем долгое время не позволяло находить и формализовать индуктивные вычисления.
Другие игнорируемые характеристики относятся к аппаратным и программным преобразованиям, которые происходят в компьютерах и компьютерных сетях. Фактически, в физических компьютерах их программы изменяются с помощью специальных программных инструментов, таких как интерпретаторы, компиляторы, оптимизаторы и переводчики. Кроме того, используя внешнюю память, люди меняют аппаратное обеспечение своих компьютеров. Аппаратное обеспечение компьютерных сетей постоянно меняется – добавляются новые компьютеры и другие устройства, в то время как другие компьютеры и другие устройства отключаются.
Целью данной статьи является построение моделей вычислений, отражающих эти характеристики физических систем обработки информации, и изучение их свойств.
Необходимо отметить, что в нашем исследовании мы проводим различие между автоматами, которые работают автономно, и машинами, в которых может участвовать человек.
Глядя на историю теоретической информатики, мы можем увидеть, что в простейшей форме аппаратная модификация присутствовала в моделях вычислений с самого начала. В самом деле, чтобы сохранить ограниченность своей памяти, машина Тьюринга должна была модифицировать свое оборудование или, точнее, свою память в процессе вычислений, потому что в общем случае длина используемой ленты могла стать больше любого числа, как длина количество вычисленных слов увеличилось. Для этого машина Тьюринга должна была добавлять на свою ленту новые ячейки, т. е. Менялась память.
Это свойство машин Тьюринга существенно увеличивает их мощность, потому что с конечной лентой (памятью) такая машина была бы эквивалентна конечному автомату, т. е. Не более мощно в вычислительном отношении.
Таким естественным образом модификация оборудования возникла в самом начале теории вычислений. Однако первой моделью, в которой аппаратное обеспечение существенно менялось в процессе вычислений, была машина модификации аппаратного обеспечения. Такая машина представляет собой совокупность блоков, каждый из которых является конечным преобразователем с несколькими входами, и систему произвольных связей между блоками. Эти соединения могут быть изменены во время вычислений, и новые блоки могут быть активированы по мере выполнения вычислений.
Еще более существенная модификация программного обеспечения выполняется в индуктивных машинах Тьюринга, память которых в основном создается специальным агентом в виде машины Тьюринга или другой индуктивной машины Тьюринга. Рассматривая этот агент как компонент основной машины, мы получаем абстрактный автомат с самомодификацией аппаратного обеспечения, поскольку память является частью аппаратного обеспечения машины.
Хотя физические компьютеры также выполняют операции со своими программами, используя специальные программные инструменты, такие как интерпретаторы, компиляторы, оптимизаторы и переводчики, концепция модификации программного обеспечения в абстрактных автоматах пришла в информатику намного позже. Идея такой модификации для увеличения мощности вычислений принадлежит Стивену Клини, который сформулировал гипотезу о том, что алгоритмы, изменяющие свои программы во время вычислений, могут оказаться более мощными, чем машины Тьюринга.
Чтобы проверить эту гипотезу, Марк Бургин построил рефлексивные машины Тьюринга. Это была первая теоретическая модель алгоритмов, изменяющих свои программы в процессе вычислений. Используя эту модель, Бургин доказал, что класс рефлексивных машин Тьюринга вычислительно эквивалентен классу машин Тьюринга, т. е. Оба класса абстрактных машин имеют одинаковую вычислительную мощность. Таким образом, гипотеза Клини была опровергнута, но в то же время было доказано, что рефлексивные машины Тьюринга могут быть существенно более эффективными, чем машины Тьюринга. А именно, соответствующая рефлексивная машина Тьюринга может эффективно превзойти любую машину Тьюринга, которая вычисляет ту же функцию.
Более общая модель автоматов, модифицирующих свое программное обеспечение – симметричные машины Тьюринга или S–машины – была позже предложена Марцином Шредером. Понятие симметричной индуктивной машины Тьюринга было введено в.
Есть также направления в компьютерном программировании, такие как рефлексивное программирование или метапрограммирование, которые позволяют наблюдать и изменять компьютерные программы во время выполнения.
Здесь мы синтезируем аппаратную и программную модификацию в одной теоретической модели триадного автомата или триадной машины, которая обрабатывает и изменяет не только данные (информационное ПО), но также собственно программное и аппаратное обеспечение. Таким образом, в общем случае триадный автомат (триадический автомат) способен преобразовывать все три своих основных компонента.
Таким образом, триадные автоматы (триадические машины) преобразуют информацию трех типов, потому что аппаратное обеспечение автомата (машины) является физическим контейнером (носителем) информации, его программное обеспечение – контейнером текстовой информации (носителем), а информационное ПО – контейнером символической информации (носителем).
Эта статья имеет следующую структуру. Во втором разделе, после введения, мы рассматриваем отношения между алгоритмами, автоматами и машинами. В третьем разделе мы обсуждаем внутреннюю структуру абстрактных автоматов, которая состоит из аппаратного, программного и информационного обеспечения, которые можно рассматривать как данные, обрабатываемые этим автоматом. В четвертом разделе мы вводим и формально описываем понятие триадного автомата. В пятом разделе мы изучаем динамику триадных автоматов и машин. В заключение мы обобщаем полученные результаты и предлагаем направления будущих исследований.
Не будет преувеличением сказать, что основные концепции информатики – это алгоритмы, автоматы, машины и вычисления. Тем не менее, нет единогласно принятых определений этих важных понятий. Поэтому в этом разделе мы анализируем эти понятия, разъясняем отношения между ними и предлагаем неформальные определения этих понятий в контексте обработки информации.
Определение 1. Алгоритм – это конструктивное конечное описание множества процессов, направленных на решение некоторой проблемы, с точными определениями его входа и результата.
Здесь конструктивность означает, что все описанные операции понятны, исполнимы и конечны. Есть разные типы, категории, виды, формы и классы алгоритмов. Рассмотрим некоторые из них. Согласно описанной в структуризации мира, люди используют следующие типы алгоритмов:
Эта классификация отражает уровни символизма в представлениях алгоритмов.
Также существуют уровни алгоритмов, отражающие степени явного описания вычислительных процессов алгоритмами. Для простоты мы описываем эти уровни для алгоритмов, которые имеют форму системы инструкций или правил.
Алгоритмы первого уровня содержат только инструкции (правила) преобразования данных.
Алгоритмы второго уровня содержат инструкции (правила) для преобразования данных и инструкции (или метаправила), которые описывают, как применять инструкции (правила) преобразования данных.
Например, в конечных автоматах инструкции (правила), определяющие, как выбрать подходящий переход, являются инструкциями выполнения (или метаправилами).
Обратите внимание, что метаправила выбора инструкций могут существенно влиять на функционирование систем, в которых они используются.
Алгоритмы третьего уровня содержат инструкции (правила) для преобразования данных, инструкции выполнения (метаправила) первого уровня, которые описывают, как применять инструкции (правила) преобразования данных, и инструкции выполнения (метаправила) второго уровня, которые описывают, как выполнять применять инструкции выполнения (метаправила) первого уровня.
Можно продолжить эту конструкцию, рассматривая алгоритмы любого уровня n.
Алгоритмы используются для управления и управления работой автоматов и машин, которые являются системными устройствами. Поэтому вначале рассмотрим общее понятие устройства.
Определение 2. Устройство – это структура, которая выполняет действия и генерирует процессы.
Есть разные типы, категории, виды и классы устройств. Рассмотрим некоторые из них.
Согласно описанной в структуризации мира, люди используют следующие типы устройств:
Важно понимать, что приборами являются только инструментальные алгоритмы. Два других класса – текстовые и числовые алгоритмы – не являются устройствами, поскольку сами не выполняют действий. Например, машина Тьюринга – это устройство, а частичная рекурсивная функция – это не устройство.
Алгоритмы, которые не являются устройствами, требуют для выполнения устройств или людей.
По своему происхождению люди создают и используют следующие классы устройств:
Люди конструируют и используют самые разные искусственные устройства – компьютеры, автомобили, самолеты, сотовые телефоны, корабли и так далее. В то же время люди используют и разные природные приспособления. Система солнечных часов является примером такого устройства. Он состоит из трех подсистем: Солнца, Земли и самих солнечных часов.
По классификации естественных систем существуют следующие виды устройств:
В некотором обобщенном смысле все живые существа можно рассматривать как одушевленные устройства. Солнечная система – пример неодушевленного устройства.
Автоматы и машины – важные частные случаи устройств.
Определение 3. Автомат – это устройство, которое автономно выполняет действия, предписанные алгоритмом, при подаче соответствующего входного сигнала.
Функционирование автоматов контролируется алгоритмами.
Подобно устройствам в целом, существует три основных класса автоматов:
По сути, к автоматам применимы все классификации устройств.
Очень часто люди относятся к теоретическим автоматам и машинам как к одному классу объектов. Например, машины Тьюринга считаются самым популярным классом абстрактных автоматов. Однако в нашем исследовании мы проводим различие между автоматами и машинами.
Определение 4. Машина – это такое устройство, которое при соответствующем вводе выполняет действия, предписанные алгоритмом, который может включать участие людей.
Например, сотовые телефоны – это машины, а часы – это автоматы.
Обратите внимание, что согласно этим определениям любой автомат является машиной, но неверно, что любая машина является автоматом.
По сути, все классификации устройств порождают соответствующие классы автоматов и машин, потому что автоматы и машины являются устройствами. Чтобы избежать повторения, мы не рассматриваем те типы, категории, виды и классы автоматов и машинную классификацию, которые вызваны классификациями устройств. В то же время существуют классификации автоматов и машин, обусловленные классификацией алгоритмов. В качестве примера можно взять следующую классификацию.
Согласно классификации алгоритмов, управляющих автоматами, в информатике используются следующие категории автоматов:
Устройства в целом и автоматы и машины в частности могут выполнять различные функции и генерировать разнообразные процессы. Здесь нас интересует обработка информации в виде вычислений.
Хотя вычисления пронизывают современное общество, единогласно принятого определения вычислений не существует. В то же время существует множество различных определений и описаний, некоторые из которых мы рассматриваем здесь.
После того, как машина Тьюринга была принята как высшая модель алгоритмов, вычисления были интерпретированы как то, что делает машина Тьюринга. Когда стало ясно, что вычисления могут выходить за рамки машин Тьюринга, появилась противоположная тенденция, согласно которой предполагалось, что любая система в природе или обществе является вычислительной. Такой подход называется панкомпутационизмом.
Как объясняется в, существует три основных уровня общности в понимании феномена вычислений:
На верхнем уровне вычисление воспринимается как любое преобразование информации и / или информационного представления.
На среднем уровне вычисление представляет собой дискретный процесс преобразования информации и / или представления информации.
На нижнем уровне вычисление распознается как дискретный процесс символьного преобразования информации и / или символьного представления информации.
Здесь мы применяем инженерный подход к вычислениям, согласно которому вычисление – это процесс, выполняемый устройствами обработки информации. Кроме того, далее мы рассматриваем только вычислительные автоматы и машины.
Мы ввели концепции триадных автоматов и машин. Получены взаимосвязи между различными типами триадных автоматов и машин и их свойства. Кроме того, мы усовершенствовали таксономию классов автоматов и машин, а также отдельных автоматов и машин. Все это открывает новые направления для дальнейших исследований.
Индуктивные машины Тьюринга образуют мощный класс алгоритмов. Таким образом, формализация и исследование триадических индуктивных машин Тьюринга является мотивирующей проблемой для будущих исследований. Можно изучить ту же проблему для периодических машин Тьюринга, которые неразрывно связаны с индуктивными машинами Тьюринга.
Структурные машины обеспечивают чрезвычайно гибкую модель вычислений. Было бы интересно представить и изучить триадные структурные машины.
Было бы также интересно формализовать триадные клеточные автоматы, триадические индуктивные клеточные автоматы и триадные нейронные сети и изучить их свойства.
Традиционные рекурсивные и суперрекурсивные модели автоматов и алгоритмов используются для развития алгоритмической теории информации. Таким образом, важным направлением будущих исследований является развитие триадической теории информации на основе триадических автоматов.