О мат-нотациях и Машинах Тьюринга

Hard

10 min

2.7K

Tutorial

Преамбула

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

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

Немного определений

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

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

Модель - это исполнитель команд. Фактически это любой Язык Программирования (ЯП) от с# до brainfuck :)

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

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

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

Верно также, что на МТ можно построить всякую программу, даже неразрешимую.

Если плюсы полных языков более менее очевидны (универсальные возможности), то плюсы неполных языков - чуть более интересный нюанс. Неполные языки обладают важным свойством - их программы всегда завершаются. Это может быть хорошим, простым, быстрыми и достаточно дешевым решением, если нужно создать ЯП без проблемы останова. Хотя:

а) это может внести новые проблемы, непредусмотренные на ранних этапах;

б) могут быть и другие решения - ручное ограничение Тьюринг-полного языка. Хотя и это не всегда возможно.

Вот список Тьюринг-неполных языков, который мне предоставил человек, более знающий в теме, чем я (не могу оценить корректность, так что не ко мне претензии): Lean4, Idris, Coq, ...

Теперь что касается корректности употребления данных терминов.

Некорректно говорить о Тьюринг-полноте нотации. Ведь нотация - это лишь метод перевода, а не модель. Однако в нотации можно построить модель, и в том числе модель-эквивалент МТ. Тогда модель в данной нотации будет полна по Тьюрингу (см. в конец статьи).

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

Итак, моя нотация

Нотация возникла сама собой в результате работы в Латехе и не только, и, с одной стороны, построена не специально, не имея перед собой задачи. Однако, с другой стороны, нотация представляет собой хорошую, до определенной степени, альтернативу ЯП для математиков (и именно для них!). Простейший пример, чтобы было ясно, о чем идет речь: вместо того, чтобы писать программу с циклом на языке, использовать $\sum$ . Таким образом, код программы можно заменить на формулу в одну строку, а сама строка задается через Латех-код. Чисто гипотетически, можно создать конструктор формул, как это существует в MS-Word.

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

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

Моя нотация отличается тремя особенностями:

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

Конструкция (a=b=c=...)

Идея этого пункта Нотации пришла ко мне еще в школе. Собственно, я активно пользовался им на уроках физики. Я называю этот трюк "математическим деепричастным оборотом" :)

Суть проста. Приведем пример:

$m = \rho V$

$F = mg = \rho Vg = \rho Shg$

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

В моей же нотации это можно записать так:

$F = (m=\rho (V=Sh))g$

Читать (в любом случае) или компилировать (в случае, если ответ не известен) такие выражения следует согласно обратной польской нотации рекурсивно с самого вложенного уровня скобок. Читать можно так: " равно (которое равно $\rho S h$ ), помноженное на ". Если внутри скобок встречается один или более знаков равно, выражение компилируется по порядку с права на лево. (По принципу "...В доме, который построил Джек, который построил дом...")

Итерирование операторов

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

Факториал:

$n! = \prod_{i=2}^{n} n_i$ $(\textit{$i,n\in \mathrm{N}$})$

Бином Ньютона:

$(a+b)^{n} = \sum_{k=a}^{b} C_{n}^{k} a^{n-k}b^{k}$ $(\textit{$k,a,b\in \mathrm{N}$})$

Интеграл:

$\intop_{a}^{b}f(x)dx = F(b) - F(a)$ $(\textit{$a,b\in \mathrm{R}$})$

Законы де Моргана в общей форме:

$\overline{\bigvee_{i=1}^{N}x_{i}}=\bigwedge_{i=1}^{N}\overline{x_{i}}$ $\overline{\bigwedge_{i=1}^{N}x_{i}}=\bigvee_{i=1}^{N}\overline{x_{i}}$ $(\textit{$i,N \in \mathrm{N}$})$

Вероятность для совместных событий $A_{\alpha}$ :

$P(\bigcup_{\alpha=1}^{N}A_{\alpha}) = \sum_{\alpha=1}^{N}(-1)^{\alpha+1}*P(\bigcap_{\beta=1}^{\alpha}A_{\beta})$ $(\textit{$\alpha,\beta, N \in \mathrm{N}$})$

Все эти формулы имеют итерированный оператор. Ниже каждой формулы написано требование по типу для каждого итератора. Так, везде, кроме интеграла, он исключительно натуральный (нуль возможен при желании). К слову, в них же всех итератор может быть не только натуральный, но и $(i\in \mathrm{Z}) = (-\infty\le i\le\infty)$ , как это будет при имитировании МТ в конце статьи.

Подводя общую черту, у итерируемого оператора есть:

1.Итератор

1.1 Верхняя его граница

1.2 Нижняя его граница

Ниже итерируемого оператора в нотации пишется итератор, оператор , $\in$ ,или $\le$ и нижняя граница. Выше итерируемого оператора пишется верхняя граница. Верхняя граница может быть опущена, если множество значений итератора приведено снизу с помощью $\in$ или двойным неравенством.

$(\overset{N}{\underset{i=1}{\bigcup}} = \overset{}{\underset{1\le i\le N}{\bigcup}} = \overset{}{\underset{i\in \{ 1...N \}}{\bigcup}})$

Если итерирование идет сверху вниз, итератор, , или $\ge$ , и верхняя граница пишутся над итерируемым оператором. Так же, если множество значений итератора при итерировании сверху вниз указано при помощи $\in$ или двойным неравенством, нижняя граница может быть опущена.

$(\overset{i=N}{\underset{1}{\bigcup}} = \overset{N\ge i\ge 1}{\underset{}{\bigcup}} = \overset{i\in \{ N...1 \}}{\underset{}{\bigcup}})$

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

Например:

Если - матрица $N\times N$ , и

$M_{stright} = \bigcup_{i=1}^{N} \bigcup_{j=1}^{i}M_{ij}$ $M_{inv} = \bigcup_{i=1}^{N} \bigcup_{i}^{j=N}M_{ij}$

То для матрицы 2х2

$M = \begin{pmatrix} 1 & 2 \\3 & 4 \end{pmatrix}$ $M_{stright} = \begin{pmatrix} 1 & \to & 2\\ & \swarrow &\\ 3 & &\times \end{pmatrix} = \{ \{1, 2\}, \{3\}\}$ $M_{inv} = \begin{pmatrix} 1 & \gets & 2 \\ & \searrow &\\ \times & & 4 \end{pmatrix} = \{ \{2, 1\}, \{4\}\}$

Теперь было бы удобно, чтобы аналогичным образом итерировался любой оператор. Таким образом, в нотации имеем ( - expression, $\times$ - итерируемый оператор):

$\overset{N}{\underset{i=1}{\times}}expr_{i}=\underbrace{expr_{1} \times expr_{2} \times ...\times expr_{N}}_N$

А также возможно итерирование по переменной-счетчику ():

$K^{B}_{A}expr_K(K) = \underbrace{expr_{A}(K_A)\circ \space... \circ \space expr_{B}(K_B)}_{B-A+1}$

Чуть более любопытный пример:

Число, записанное поциферно слева направо.

Здесь цифры считаются с левого края, а разряды - справого. Надстрочная черта обозначает как раз поциферную запись числа.

$\overline{(n)_{N-i+1}}^{1\le i\le N} =$ $=\sum_{i=1}^{N}n_{N-i+1}*10^{i}$

Рекурсия в формуле

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

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

$\{ 2^1 , ... , 2^{n}\}$

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

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

Например, в формуле подведения множества всех унарных чисел

$M=\{1\}$ $M = M\cup\overline{(1)_{i}}^{1\le i\le |M|+1}$

последовательность действий при отладке будет следующая:

$M=\{1\}$ $\Biggl(M=\{1\}\cup\overline{\space1\space}^{(1+1=2)}=$ $=\{1\}\cup\{11\}=\{1,11\}\biggr)$ $\biggl(M=\{1,11\}\cup\overline{\space1\space}^{(2+1=3)}$ $\{1,11\}\cup\{111\}=\{1,11,111\}\biggr)$

Обратите внимание на длину исходной формулы и длину пояснения.

Внимание! Далее начинается опасная часть статьи!

Рекурсивные формулы можно записывать двумя путями:

Рекуррентно ()
Через оператор рекурсии

Рекурсивный оператор пишется на программный лад как оператор и знак справа (например, , $\cup=$ , $\vee=$ ) или два оператора подряд в случае операторов или .

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

Итак, любая рекурсивная формула содержит следующие составляющие:

1.Итерируемый оператор (например, $\bigcup$ )
2.Итератор ()
2.1 Нижняя граница итератора (например, $\bigcup_1$ )

2.2 Верхняя граница итератора (например, $\bigcup^N$ )

3.Оператор рекурсии (например,)
3.1 Итератор оператора рекурсии (например, $\overset{}{\underset{i}{+}}=$ )

3.2 Нижняя граница оператора (например, $\overset{}{\underset{1}{+}}=$ )

3.3 Верхняя граница оператора (например, $\overset{N}{\underset{}{+}}=$ )

Стало быть, на каждом уровне рекурсии обновляется одно из следующего:

Итератор ()
Нижняя граница итератора ( $\bigcup_1$ )
Верхняя граница итератора ( $\bigcup^N$ )
Итератор рекурсивного оператора ( $\overset{}{\underset{i}{+}}=$ )
Нижняя граница этого итератора ( $\overset{}{\underset{1}{+}}=$ )
Верхняя граница этого итератора ( $\overset{N}{\underset{}{+}}=$ )
Что-то еще, за переделами итерируемого или рекурсивного оператора - например, создаваемое формулой множество ( $M= \space...$ )

И обновляться каждое из них может:

раз ( $M=...\overset{N}{\underset{i=1}{+}}=...$ )
раза ( $M=...\overset{N}{\underset{i=1}{+}}=...\overset{N}{\underset{i=1}{+}}=...$ )
...
раз

А также есть еще два последних нюанса:

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

( $M=...\overset{N}{\underset{i=1}{*}}=...\overset{N}{\underset{j=1}{+}}=...$ )
Оператор рекурсии может быть под или над итерированным оператором

( $\overset{}{\underset{...+=...}{\bigcup}}$ или $\overset{...+=...}{\underset{}{\bigcup}}$ )
Или, наоборот, итерированный оператор может быть под или над рекурсивным

( $\overset{}{\underset{\cup}{+}}=$ или $\overset{\cup}{\underset{}{+}}=$ )

При этом, если наличествует оператор, как итерированный, так и рекурсивный, такой оператор сначала отрабатывает полностью как итерированный, и лишь далее - как рекурсивный.

Некоторые примеры

Множество степеней двойки, не больших

$M = \{1\}$ $M = \bigcup_{i = 1}^{1\le(N\in \mathrm{N})} (i\space|\space i+=i) =$ $=\left\{ 2^0 , ... , 2^{n}\le N \right\}$

Резон записывать данную формулу через рекурсию в основном в том, что для модели нет четкого алгоритма, чем именно заполнять . Здесь итерированный оператор - это оператор $\bigcup$ поэлементного объединения, итератор , а оператор рекурсии - .

В данной формуле итератор пробегается от по натуральным числам от до $\infty$ и одновременно увеличивается на свою же величину (то есть, в два раза на каждом уровне рекурсии, можно записать также ). А значит, пробегает не все натуральные значения, - а лишь степени двойки. Что и выходит в результате.

Читать данную формулу следует так:

$M=\{1\}$
$i+=i \Rightarrow i=2$
$M=\left\{ 1 \right\}\cup (i=2)$
$i+=i \Rightarrow i=4$
$M=\left\{ 1;2 \right\}\cup (i=4)$
$i+=i \Rightarrow i=8$
$M=\left\{ 1;2;4 \right\}\cup (i=8)$

Другой пример:

Ряд чисел Фибоначчи, не больших :

$F = \{1\}$ $F=\bigcup_{i = 1}^{1\le(N\in \mathrm{N})} (i\space|\space i+=F_{i-1})$

Аналогично предыдущему примеру, итерируемый оператор - $\bigcup$ , итератор , и оператор рекурсии - . Разница с предыдущим примером здесь в том, что итератор наращивается предыдущем элементом ряда, а не удваивается.

Пример последний:

Множество всех строк треугольника Паскаля:

$P = \{\{1\}\}$ $P=\space (\bigcup_{k=0}^{|P|}=) \space C_{k}^{|P|+1}$

Этот пример особо интересен тем, что итерируемый оператор( $\cup=$ ) является рекурсивным, и обновляется как создаваемое множество (объект за пределами операторов), так вместе с тем и верхняя граница оператора - так как этой границей выбрана мощность .

Здесь итерируемый оператор - $\bigcup$ , рекурсивный оператор - $\cup=$ , итератор и верхняя граница .

Порядок чтения и исполнения формулы таков:

$P = \{\{ 1 \}\}$
$k\in \{0,1\}$
$P \cup= C_0^2=1 \Rightarrow P = \{ 1\}$ (срабатывает $\bigcup=$ как итерированный оператор, обновляется первое и )
$P \cup= C_1^2=1 \Rightarrow P = \{ 1, 1\}$ (срабатывает $\bigcup=$ как итерированный оператор, обновляется первое и )
$P \cup= (P=\{1,1\}) \Rightarrow P = \{ 1,\{ 1, 1\}\}$ (срабатывает $\bigcup=$ как рекурсивный оператор, обновляется второе, более правое )
$0\le k\le 2$
$P \cup= C_0^2=1 \Rightarrow P = \{ 1\}$ (срабатывает $\bigcup=$ как итерированный оператор, обновляется первое и )
$P \cup= C_1^2=1 \Rightarrow P = \{ 1, 2\}$ (срабатывает $\bigcup=$ как итерированный оператор, обновляется первое и )
$P \cup= C_2^2=1 \Rightarrow P = \{ 1, 2 , 1\}$ (срабатывает $\bigcup=$ как итерированный оператор, обновляется первое и )
$P \cup= (P=\{1,2,1\}) \Rightarrow P = \{ 1,\{ 1, 1\} \{ 1, 2 , 1\}\}$ (срабатывает $\bigcup=$ как рекурсивный оператор, обновляется второе справа )
$0\le k\le 3$

Построение эквивалента МТ

Пусть множество - алфавит МТ, - множество состояний МТ, и (Tape) - лента МТ, бесконечная в обе стороны:

$T = \bigcup_{i\in \mathrm{Z}}(\alpha_{i}\in A)$ $R = (q\in Q)\times (\alpha\in A)\to \{q,\alpha,\overrightarrow{v\space}\}$

(Rules) - таблица $|Q| \times |A|$ , каждая ячейка которой содержит три переменные: следующее состояние , записываемый символ $\alpha$ и вектор сдвига (в некоторых аналогах построения МТ модуль вектора $|\overrightarrow{v\space}|$ может быть ). Важно, что, если некоторые ячейки таблицы остаются пустыми, данная модель МТ, построенная на нотации, может выдать ошибку, так как её не будет ясно, как обрабатывать что-то, кроме. $\{q,\alpha,\overrightarrow{v\space}\}$ . Посему, стоит предусмотрительно заполнить все ячейки изначально соответственно, например, $\{\emptyset,\emptyset,\overrightarrow{0\space}\}$ .

Выбираем исходное правило МТ.

$T_{i} = r_{\alpha}\left|\left \{ \begin{aligned} i +&=r_{\overrightarrow{v\space}}\\ r &= R(r_q,r_{\alpha}) \end{aligned} \right.\right.$

Записываем в -тую ячейку ленты символ текущего правила, обновляем итератор , а также текущее правило .

Итог

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

Однако еще и еще раз обращу внимание: нотация подходит не для всех! Да, многим из вас наверняка проще написать код, чем мучиться с формулой, - я лишь привел пример, как это можно делать в том числе.

Tags:

Hubs: