Игра Жизнь. Её связь с машиной Тьюринга

 

Игра жизнь

• Место действия этой игры — «вселенная» — это размеченная на клетки поверхность или плоскость — безграничная, ограниченная, или замкнутая. (В пределе — бесконечная плоскость).
• Каждая клетка на этой поверхности может находиться в двух состояниях: быть "живой" или быть "мёртвой" (пустой). Клетка имеет восемь соседей (окружающих клеток).
• Распределение живых клеток в начале игры называется первым поколением. Каждое следующее поколение рассчитывается на основе предыдущего по таким правилам:
• пустая (мёртвая) клетка, рядом с которой ровно три живые клетки, оживает;
• если у живой клетки есть две или три живые соседки, то эта клетка продолжает жить; в противном случае (если соседей меньше двух или больше трёх) клетка умирает (от «одиночества» или от «перенаселённости»).
• Игра прекращается, если на поле не останется ни одной "живой" клетки, или если при очередном шаге ни одна из клеток не меняет своего состояния (складывается стабильная конфигурация).

 

Джон Конвей заинтересовался проблемой, предложенной в 1940-х годах известным математиком Джоном фон Нейманом, который пытался создать гипотетическую машину, которая может воспроизводить сама себя. Джону фон Нейману удалось создать математическую модель такой машины с очень сложными правилами. Конвей попытался упростить идеи, предложенные Нейманом, и в конце концов ему удалось создать правила, которые стали правилами игры «Жизнь». Впервые описание этой игры было опубликовано в октябрьском выпуске (1970) журнала Scientific American, в рубрике «Математические игры» Мартина Гарднера (Martin Gardner).

 

К настоящему времени более-менее сложилась следующая классификация фигур:

Планерное ружьё Госпера (англ.) — первая бесконечно растущая фигура

• Устойчивые фигуры: фигуры, которые остаются неизменными
• Периодические фигуры: фигуры, у которых состояние повторяется через некоторое число поколений
• Двигающиеся фигуры: фигуры, у которых состояние повторяется, но с некоторым смещением
• Ружья: фигуры, у которых состояние повторяется, но дополнительно появляется двигающаяся фигура
• Паровозы: двигающиеся фигуры, которые оставляют за собой следы в виде устойчивых или периодических фигур
• Пожиратели: устойчивые фигуры, которые могут пережить столкновения с некоторыми двигающимися фигурами
• Сорняки (паразиты)^{[ источник не указан 293 дня ]}: фигуры, которые при столкновении с некоторыми фигурами дублируются.

Райский сад

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

 

 

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

 

Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: q_ia_j→q_i1a_j1d_k (если головка находится в состоянии q_i, а в обозреваемой ячейке записана буква a_j, то головка переходит в состояние q_i1, в ячейку вместо a_j записывается a_j1, головка делает движение d_k, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (N)). Для каждой возможной конфигурации <q_i, a_j> имеется ровно одно правило. Правил нет только для заключительного состояния, попав в которое машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.

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

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

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

 

 

Билет 9 вопрос 1

OrCAD — пакет компьютерных программ, предназначенный для автоматизации проектирования электроники. Используется в основном для создания электронных версий печатных плат для производства печатных плат, а также для производства электронных схем и их моделирования.

Название OrCAD произведено от слов Or egon и CAD.

Продукты серии OrCAD принадлежат компании Cadence Design Systems. Последняя версия OrCAD имеет возможность по созданию и поддержке базы данных доступных интегральных схем. База данных может быть обновлена путём скачивания пакетов производителей компонентов, таких как Texas Instruments.

В составе пакета следующие модули:

§ Capture — редактор принципиальных схем,

§ Capture CIS Option — менеджер библиотек Active Parts,

§ PSpice Analog Digital — пакет аналого-цифрового моделирования,

§ PSpice Аdvanced Аnalysis — пакет параметрической оптимизации,

§ PSpice SLPS option — интерфейс связи с пакетом Matlab,

§ PCB Designer — редактор топологий печатных плат,

§ SPECCTRA for OrCAD — программа автоматической и интерактивной трассировки,

§ Signal Explorer — модуль анализа целостности сигналов и перекрестных искажений.

Билет 10 вопрос 1

В целом проектирование БИС в среде Cadence, реализуемое сегодня на платформе Virtuoso, включает этапы, изображенные на рисунке 2.4.

• системное проектирование – построение модели системы на высоком уровне абстракции с использованием языков программирования C/C++ и SystemC, разбиение на программные и аппаратные модули, исследование параметров системы, получение спецификаций (набора требуемых параметров) на программные и аппаратные блоки;

• аппаратное проектирование и верификация – разработка на основе спецификации поведенческих моделей отдельных блоков системы с использованием языков Verilog/VHDL, реализация проекта в базисе библиотек производителя ИС, проверка программно-аппаратной реализации на соответствие спецификациям, полученным на системном уровне;

 

 

Рисунок 2.4- Этапы проектирования БИС в среде Cadence

 

• физическое прототипирование – предварительное размещение элементов, оценка потребляемой мощности, планирование шин питания и иерархии тактовых сигналов, качественная оценка возможных искажений сигнала;

• проектирование и верификация топологии кристалла – разработка топологии заказных блоков, трассировка на уровне ячеек, проверка правил проектирования топологии, экстракция паразитных параметров.

 

 

Билет 11 вопрос 1

Казёнов страница 102

 

 

Билет 12 вопрос 1

ЕСТЬ И В КАЗЁНОВЕ

Билет 12 вопрос 2

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

Формальное определение

n-местным (n-арным) отношением, заданным на множествах , называется подмножество прямого произведения этих множеств.

Иногда понятие отношения определяется только для частного случая для отношения R. Тогда факт принадлежности n -ки этому отношению можно записать как:

.

Арность

§ Одноместные отношения соответствуют свойствам или атрибутам.

§ Двуместные отношения называют бинарными и обычно записывают инфиксной записью: x R y. Примерами множеств с введёнными на них бинарными отношениями являются графы и частично упорядоченные множества.

§ Трёхместные отношения называют тернарными.

Примеры

§ Отношение равенства на множестве вещественных чисел — бинарное отношение, обозначаемое символом «=». Ему принадлежат все пары вида , и только они.

§ Отношение эквивалентности на произвольном множестве M — бинарное отношение, обычно обозначаемое символом «~». Состоит из пар вида , где x и y принадлежат одному классу эквивалентности, и только из них.

§ Отношение делимости на множестве натуральных чисел — бинарное отношение, обычно обозначаемое символом «|». Состоит из пар вида , где x делит y нацело.

Отношения и предикаты

Отношение также может быть задано предикатом на n -й декартовой степени множества M: n -ка принадлежит отношению тогда и только тогда, когда предикат на ней возвращает значение 1 (или «истинно»). Таким образом, можно дать альтернативное определение отношения: если задано отображение , то отношением R называется прообраз единицы в f. Такое определение бывает полезно в информатике и математической логике.

Предикаты, которые формируются из отношений, заданных в соответствии с основным определением (когда множества в прямом произведении различны), используются в многосортном исчислении предикатов.^[1]

Операции с отношениями

Система отношений, сформированная на одном и том же прямом произведении множеств, изоморфна алгебре множеств и допускает применение теоретико-множественных операций и проверок включения одного отношения в другое. Элементами множеств в этом случае являются кортежи элементов (n -ки).

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

В математике бинарным отношением называется подмножество декартова произведения двух множеств. В частности, бинарным отношением на множестве называется непустое множество упорядоченных пар элементов этого множества.

Бинарные отношения могут обладать различными свойствами, такими как

§ Рефлексивность: .

§ Антирефлексивность (иррефлексивность): .

§ Симметричность: .

§ Антисимметричность: .

§ Транзитивность: .

§ Асимметричность: . Асимметричность эквивалентна одновременной антирефлексивности и антисимметричности отношения.

Виды отношений

§ Рефлексивное транзитивное отношение называется отношением квазипорядка.

§ Рефлексивное симметричное транзитивное отношение называется отношением эквивалентности.

§ Рефлексивное антисимметричное транзитивное отношение называется отношением (частичного) порядка.

§ Антирефлексивное антисимметричное транзитивное отношение называется отношением строгого порядка.

§ Полное антисимметричное транзитивное отношение называется отношением линейного порядка.

§ Антирефлексивное асимметричное отношение называется отношением доминирования.

 

Операции над отношениями:

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

Часто вместо объединения, пересечения и дополнения отношений говорят об их дизъюнкции, конъюнкции и отрицании.

Например, , , то есть объединение отношения строгого порядка с отношением равенства совпадает с отношением нестрого порядка, а их пересечение пусто.

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

Если , то обратным отношением называется отношение R ^{− 1}, определённое на паре B, A и состоящее из тех пар (b, a), для которых . Например, < ^{− 1} = >.

Пусть теперь , . Произведением отношений R, S называется отношение такое, что

Если , и , то произведение отношений не определено. Если же отношения рассматривать определённые на каком-то множестве A, то такой ситуации не возникает.

Например, рассмотрим отношение строгого порядка < определённого на множестве натуральных чисел. Несложно заметить, что

Бинарные отношения R и S называются перестановочными, если RS = SR. Несложно заметить, что для любого бинарного отношения R, определённого на A, RI_A = I_AR, где символом I_A обозначено равенство, определённое на A. Однако равенство RR ^{− 1} = I не всегда справедливо.

Имеют место следующие тождества:

§ R (ST) = (RS) T,

§ (RS) ^{− 1} = S ^{− 1} R ^{− 1},

§ ,

§ ,

§ ,

§ ,

§ .

Отметим, что аналоги последних двух тождеств для не имеют места.

Некоторые свойства отношения можно определить, используя операции над отношениями:

§ Рефлексивность: ,

§ Симметричность: ,

§ Транзитивность: .