Немного программирования — различия между версиями

Материал из synset
Перейти к: навигация, поиск
Строка 7: Строка 7:
 
Рассмотренный язык BASE является достаточно "высокоуровневым" и может быть сведен к ещё более простым элементам. Однако, если бы программисты были ограничены даже перечисленным синтаксисом, их можно было бы только пожалеть. Для повышения выразительности языка вводятся разнообразные расширения обозначений, которые, однако, однозначным образом расшифровываются в терминах базового синтаксиса. Поэтому, перед выполнением программы, её необходимо ''компилировать'', т.е. преобразовать входную строку программы с расширенным алфавитом в другую, с более лаконичным. Например, если в тексте встречается символ "<math>\textstyle \neq</math>" (не равно), то необходима такая "компилляция":
 
Рассмотренный язык BASE является достаточно "высокоуровневым" и может быть сведен к ещё более простым элементам. Однако, если бы программисты были ограничены даже перечисленным синтаксисом, их можно было бы только пожалеть. Для повышения выразительности языка вводятся разнообразные расширения обозначений, которые, однако, однозначным образом расшифровываются в терминах базового синтаксиса. Поэтому, перед выполнением программы, её необходимо ''компилировать'', т.е. преобразовать входную строку программы с расширенным алфавитом в другую, с более лаконичным. Например, если в тексте встречается символ "<math>\textstyle \neq</math>" (не равно), то необходима такая "компилляция":
  
:<center><math>\mathbf{if}(x \neq y)\{\;\EuScript P_1\;\}\;\;\EuScript P_2\;\;\;\;\;\;\;=>\;\;\;\;\;\;\; \mathbf{if}(x = y)\{\; \mathbf{goto}(1);\,\}\;\;\EuScript P_1\;\;\#1;\;\EuScript P_2;</math></center>
+
:<center><math>\mathbf{if}(x \neq y)\{\;\mathcal P_1\;\}\;\;\mathcal P_2\;\;\;\;\;\;\;=>\;\;\;\;\;\;\; \mathbf{if}(x = y)\{\; \mathbf{goto}(1);\,\}\;\;\mathcal P_1\;\;\#1;\;\mathcal P_2;</math></center>
  
На месте букв <math>\textstyle x</math> и <math>\textstyle y</math> могут стоять <math>\textstyle m_i</math> и <math>\textstyle m_j</math> с ''любыми'' индексами <math>\textstyle i</math> и <math>\textstyle j</math>. Стрелка "<math>\textstyle =></math>" обозначает компиляцию исходной строки в новую, "понимаемую" компьютером. Исходный текст подразумевает, что если <math>\textstyle x\neq y</math>, то выполняется <math>\textstyle \EuScript P_1 \EuScript P_2</math>, если же нет (т.е. <math>\textstyle x=y</math>), то выполняется только <math>\textstyle \EuScript P_2</math>. Именно это и происходит в преобразованной программе.
+
На месте букв <math>\textstyle x</math> и <math>\textstyle y</math> могут стоять <math>\textstyle m_i</math> и <math>\textstyle m_j</math> с ''любыми'' индексами <math>\textstyle i</math> и <math>\textstyle j</math>. Стрелка "<math>\textstyle =></math>" обозначает компиляцию исходной строки в новую, "понимаемую" компьютером. Исходный текст подразумевает, что если <math>\textstyle x\neq y</math>, то выполняется <math>\textstyle \mathcal P_1 \mathcal P_2</math>, если же нет (т.е. <math>\textstyle x=y</math>), то выполняется только <math>\textstyle \mathcal P_2</math>. Именно это и происходит в преобразованной программе.
  
 
Аналогично можно ''определить'' инструкции для проведения циклических вычислений. Так, ниже слева приведен исходный программы, которая вычисляет сумму натуральных чисел до числа хранящегося в ячейке <math>\textstyle m_0</math> включительно. Справа от черты, та же функция после компилляции (т.е. приведения в исходный синтаксис):
 
Аналогично можно ''определить'' инструкции для проведения циклических вычислений. Так, ниже слева приведен исходный программы, которая вычисляет сумму натуральных чисел до числа хранящегося в ячейке <math>\textstyle m_0</math> включительно. Справа от черты, та же функция после компилляции (т.е. приведения в исходный синтаксис):
Строка 65: Строка 65:
 
<math>\textstyle \triangleright</math> Базовый язык алгоритмов может быть упрощён. На самом деле, достаточно единственной арифметической функции прибавления единицы (следующее натуральное число) и логического равенства.
 
<math>\textstyle \triangleright</math> Базовый язык алгоритмов может быть упрощён. На самом деле, достаточно единственной арифметической функции прибавления единицы (следующее натуральное число) и логического равенства.
  
\large
+
 
  
 
(<math>\textstyle \lessdot</math> H) Написать при помощи базового синтаксиса программирования функцию сложения двух чисел <math>\textstyle \mathbf{add}(x,y)</math>, используя только функцию <math>\textstyle m_i\leftarrow m_j+1</math>. Рекурсию не применять.
 
(<math>\textstyle \lessdot</math> H) Написать при помощи базового синтаксиса программирования функцию сложения двух чисел <math>\textstyle \mathbf{add}(x,y)</math>, используя только функцию <math>\textstyle m_i\leftarrow m_j+1</math>. Рекурсию не применять.
Строка 73: Строка 73:
 
(<math>\textstyle \lessdot</math> H) Написать функцию <math>\textstyle \mathbf{mult}(x,y)=x*y</math>, не используя рекурсии.
 
(<math>\textstyle \lessdot</math> H) Написать функцию <math>\textstyle \mathbf{mult}(x,y)=x*y</math>, не используя рекурсии.
  
\Large
+
 
  
 
<math>\textstyle \triangleright</math> Программу можно записать при помощи только натуральных чисел. Для этого необходимо воспользоваться низкоуровневым языком программирования ZIPPER. В нём есть только пять команд:
 
<math>\textstyle \triangleright</math> Программу можно записать при помощи только натуральных чисел. Для этого необходимо воспользоваться низкоуровневым языком программирования ZIPPER. В нём есть только пять команд:
Строка 87: Строка 87:
 
:<center><math>Z,2,0,0,\;E,1,2,7,\;I,2,0,0,\;Z,3,0,0,\;Z,4,0,0,\;E,3,4,2,\;R,2,0,0\\</math></center>
 
:<center><math>Z,2,0,0,\;E,1,2,7,\;I,2,0,0,\;Z,3,0,0,\;Z,4,0,0,\;E,3,4,2,\;R,2,0,0\\</math></center>
  
\large
+
 
  
 
(<math>\textstyle \lessdot</math> H) Записать программу для сложения целых чисел от 1 до числа в ячейке <math>\textstyle m_0</math> при помощи языка ZIPPER.
 
(<math>\textstyle \lessdot</math> H) Записать программу для сложения целых чисел от 1 до числа в ячейке <math>\textstyle m_0</math> при помощи языка ZIPPER.
Строка 97: Строка 97:
 
(<math>\textstyle \lessdot</math> H) Какую возможность языка BASE, язык ZIPPER не выражает, и что надо в него добавить?
 
(<math>\textstyle \lessdot</math> H) Какую возможность языка BASE, язык ZIPPER не выражает, и что надо в него добавить?
  
\Large <math>\textstyle \triangleright</math> Первоначально, идеальный компьютер, который придумал Алан Тьюринг имел вид очень низкоуровневого устройства не умеющего даже складывать. Машина Тьюринга является ''автоматом'', который может находится в одном из <math>\textstyle m</math> состояний <math>\textstyle \mathcal S</math>. Например, <math>\textstyle \mathcal S: \{s_1,s_2\}</math> (<math>\textstyle m=2</math>). Существует строка с входными данными, состоящая из символов некоторого алфавита с <math>\textstyle n</math> буквами, например, <math>\textstyle \mathcal A:\{a,b,\_\}</math> (<math>\textstyle n=3</math>), где "<math>\textstyle \_</math>" &mdash; это пустой символ, который окружает исходную строку слева и справа сколь угодно много раз. Задача машины &mdash; переработать данную входную строку в другую (выходную) и остановиться. Для этого она устанавливает указатель (головку машины) на фиксированный символ строки (например, первый), а своё состояние в начальное (например <math>\textstyle s_1</math>) и затем исполняет программу, заданную в виде таблицы:
+
<math>\textstyle \triangleright</math> Первоначально, идеальный компьютер, который придумал Алан Тьюринг имел вид очень низкоуровневого устройства не умеющего даже складывать. Машина Тьюринга является ''автоматом'', который может находится в одном из <math>\textstyle m</math> состояний <math>\textstyle \mathcal S</math>. Например, <math>\textstyle \mathcal S: \{s_1,s_2\}</math> (<math>\textstyle m=2</math>). Существует строка с входными данными, состоящая из символов некоторого алфавита с <math>\textstyle n</math> буквами, например, <math>\textstyle \mathcal A:\{a,b,\_\}</math> (<math>\textstyle n=3</math>), где "<math>\textstyle \_</math>" &mdash; это пустой символ, который окружает исходную строку слева и справа сколь угодно много раз. Задача машины &mdash; переработать данную входную строку в другую (выходную) и остановиться. Для этого она устанавливает указатель (головку машины) на фиксированный символ строки (например, первый), а своё состояние в начальное (например <math>\textstyle s_1</math>) и затем исполняет программу, заданную в виде таблицы:
  
 
:<center><math>\begin{array}{|c|c|c|c|c|c|c|c|c|} \multicolumn{1}{l}{}\\ \hline \_& b & a & b & a & b & \_ & \_\\ \hline \multicolumn{1}{l}{} & \multicolumn{1}{c}{\vartriangle} \\ \end{array} \;\;\;\;\;\;\;\;\;\;\;\; \begin{array}{c|c|c|c|} \multicolumn{1}{c}{} & \multicolumn{1}{c}{a} & \multicolumn{1}{c}{b} & \multicolumn{1}{c}{\_}\\ \cline{2-4} s_1& bs_1R & as_1R & \_ s_2 L \\ \cline{2-4} s_2& bs_2L & as_2L & \_ \bullet R \\ \cline{2-4} \end{array}</math></center>
 
:<center><math>\begin{array}{|c|c|c|c|c|c|c|c|c|} \multicolumn{1}{l}{}\\ \hline \_& b & a & b & a & b & \_ & \_\\ \hline \multicolumn{1}{l}{} & \multicolumn{1}{c}{\vartriangle} \\ \end{array} \;\;\;\;\;\;\;\;\;\;\;\; \begin{array}{c|c|c|c|} \multicolumn{1}{c}{} & \multicolumn{1}{c}{a} & \multicolumn{1}{c}{b} & \multicolumn{1}{c}{\_}\\ \cline{2-4} s_1& bs_1R & as_1R & \_ s_2 L \\ \cline{2-4} s_2& bs_2L & as_2L & \_ \bullet R \\ \cline{2-4} \end{array}</math></center>
Строка 105: Строка 105:
 
При составлении программы для машины Тьюринга (т.е. таблицы переходов) необходимо выбирать свойства каждого состояния, так, чтобы оно решало некоторую элементарную задачу ("перемещаться до пробела" и т.п.). Комбинация таких подзадач-состояний и составляет алгоритм.
 
При составлении программы для машины Тьюринга (т.е. таблицы переходов) необходимо выбирать свойства каждого состояния, так, чтобы оно решало некоторую элементарную задачу ("перемещаться до пробела" и т.п.). Комбинация таких подзадач-состояний и составляет алгоритм.
  
\large
+
 
  
 
(<math>\textstyle \lessdot</math> H) Пользуясь инструкциями в таблице выше, описать последовательные преобразования входной строки "<math>\textstyle babab</math>".
 
(<math>\textstyle \lessdot</math> H) Пользуясь инструкциями в таблице выше, описать последовательные преобразования входной строки "<math>\textstyle babab</math>".
Строка 115: Строка 115:
 
(<math>\textstyle \lessdot</math> H) Рассмотреть алфавит <math>\textstyle \mathcal A: \{0,1,\_\}</math> и написать программу сортировки, переставляющей все нули в начало слова (до пробела), а единицы в конец.
 
(<math>\textstyle \lessdot</math> H) Рассмотреть алфавит <math>\textstyle \mathcal A: \{0,1,\_\}</math> и написать программу сортировки, переставляющей все нули в начало слова (до пробела), а единицы в конец.
  
\large
+
 
  
 
(<math>\textstyle \lessdot</math> H) Написать на языке BASE программу, исполняющую инструкции машины Тьюринга. Размер алфавита и число состояний заданы в ячейках <math>\textstyle m_0</math>, <math>\textstyle m_1</math>. Далее идут записанные в первых <math>\textstyle 3\cdot m_0\cdot m_1</math> ячейках таблица инструкций. Затем входная строка. При попытке сдвинуться влево на первом символе строки, она должна быть сдвинута вправо. Можно использовать любые разумные расширения синтаксиса BASE.
 
(<math>\textstyle \lessdot</math> H) Написать на языке BASE программу, исполняющую инструкции машины Тьюринга. Размер алфавита и число состояний заданы в ячейках <math>\textstyle m_0</math>, <math>\textstyle m_1</math>. Далее идут записанные в первых <math>\textstyle 3\cdot m_0\cdot m_1</math> ячейках таблица инструкций. Затем входная строка. При попытке сдвинуться влево на первом символе строки, она должна быть сдвинута вправо. Можно использовать любые разумные расширения синтаксиса BASE.

Версия 14:15, 29 января 2010

Вычислимые функции и их алгоритмы << Оглавление >> Проблемы остановки и тождественности

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

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

Аналогично можно определить инструкции для проведения циклических вычислений. Так, ниже слева приведен исходный программы, которая вычисляет сумму натуральных чисел до числа хранящегося в ячейке включительно. Справа от черты, та же функция после компилляции (т.е. приведения в исходный синтаксис):

Невозможно разобрать выражение (неизвестная функция «\multicolumn»): {\displaystyle \begin{array}{ll} \multicolumn{2}{l}{m_1\leftarrow 0;\;\;\;m_2\leftarrow 0;} \\ \multicolumn{2}{l}{\mathbf{while}(m_1<m_0)\{ } \\ & m_1\leftarrow m_1+1; \\ \;\;\;& m_2\leftarrow m_2+m_1; \\ \}\\ \multicolumn{2}{l}{\mathbf{return }\;m_2;}\\ \end{array} \;\;\;\;\;\;\;\;\;\;\; \begin{array}{|l}\;\\\;\\\;\\\;\\ \;\\\;\\\;\\\;\\ \end{array} \;\;\;\;\;\;\;\;\;\;\; \begin{array}{ll} \multicolumn{2}{l}{m_1\leftarrow 0;\;\;\;m_2\leftarrow 0;}\\ \multicolumn{2}{l}{\#1;}\\ \multicolumn{2}{l}{\mathbf{if}(m_1<m_0)\{}\\ & m_1\leftarrow m_1+1; \\ \;\;\;& m_2\leftarrow m_2+m_1; \\ \;\;\;& \mathbf{goto}(1); \\ \multicolumn{2}{l}{\}}\\ \multicolumn{2}{l}{\mathbf{return }\;m_2;}\\ \end{array}}

В расширенном синтаксисе считается, что часть программы, находящаяся внутри фигурных скобок, после команды цикла Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle \textstyle \mathbf{while}(условие)} повторяется до тех пор, пока условие срабатывает (в нашем случае, пока счётчик чисел в ячейке меньше, чем число в ). На самом деле первые строки не нужны, так как по договорённости, перед запуском программы все ячейки её памяти обнуляются.

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

Невозможно разобрать выражение (неизвестная функция «\multicolumn»): {\displaystyle \begin{array}{lll} \multicolumn{3}{l}{\mathbf{p}(m_0)\{}\\ \;\;\;& \multicolumn{2}{l}{ m_1\leftarrow 0; }\\ \;\;\;& \multicolumn{2}{l}{ \mathbf{while}(m_1<m_0)\{ }\\ &\;\;\;& \multicolumn{1}{l}{ m_2\leftarrow m_1+1; }\\ &\;\;\;& \multicolumn{1}{l}{ \mathbf{if}(m_2=m_0) \;\mathbf{return}\; m_1;} \\ &\;\;\;& \multicolumn{1}{l}{ m_1\leftarrow m_2; }\\ & \multicolumn{2}{l}{ \} }\\ \multicolumn{3}{l}{\}} \end{array}}

Для читаемости функция названа "", однако необходимо помнить, что это на самом деле что-то типа: "".

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

Напомню, что мы работаем только с целыми неотрицательными числами (0,1,2,....), поэтому приходим к первой (в длинной цепочке ) алгоритмической неприятности. Функция , хотя описывается алгоритмом (она вычислима), определена не для всех значений . В частности, для нуля нет предыдущего значения, и не доберётся до команды return. Если в ячейке находится 0, то условие в круглых скобках цикла while не сработает, и тело цикла (в фигурных скобках) будет пропущено. Вычислитель дойдёт до конца программы функции и остановится, так как команды return там нет, но и текст алгоритма закончился.

Физический компьютер может в этот момент замигать лампочками, перегрузить операционную систему или покрыть небо звёздами. Наш идеальный компьютер просто "зависнет". Мы не можем написать в конце программы, например , так как это уже будет другая функция (не предыдущего числа). Нельзя и вернуть не число, а например строку "NAN", так как в других функциях используется в арифметических вычислениях, да и нет "NAN"-а в нашем синтаксисе. Таким образом: \it вычислять, не значит вычислить. Например, вычислимой будет и такая функция: .

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

Невозможно разобрать выражение (неизвестная функция «\multicolumn»): {\displaystyle \begin{array}{lll} \multicolumn{3}{l}{\mathbf{mult}(x,y)\{}\\ \;\;\;& \multicolumn{2}{l}{ \mathbf{if}(y=0)\{\; \mathbf{return}\; 0; \;\}} \\ \;\;\;& \multicolumn{2}{l}{ \mathbf{if}(y=1)\{\; \mathbf{return}\; x; \;\}} \\ & \multicolumn{2}{l}{ \mathbf{return}\; x+\mathbf{mult}(x,\;\mathbf{p}(y)\,);} \\ \multicolumn{3}{l}{\}} \end{array}}

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

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

Алгоритм вызывает две функции, одна из которых снова "". Функция, которая при своём вычислении использует себя же саму, называется рекурсивной.

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

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

Например, справедлива следующая цепочки формул для , :

Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle \mathbf{mult}(4, 3),\;\;это\;\;4+\mathbf{mult}(4,2),\;\;это\;\;4+(4+\mathbf{mult}(4,1)),\;\;это\;4+(4+4).}

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

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

Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle \mathbf{mult}(4, 3),\;\;это\;\;4+\mathbf{mult}(4,4),\;\;это\;\;4+(4+\mathbf{mult}(4,5)),\;\;\;это\;\;\;...}

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

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

С помощью глобальной памяти можно реализовать не функциональное поведение. Обычная функция, при данном входе, всегда выдаёт один и тот же выход. Автоматом называют вариант, такого же как и функция, ящика со входом и выходом. Однако результат его вычисления может зависеть не только от данного значения входа, но и от всей предыстории вызовов этого автомата. Автоматным поведением обладают очень многие системы. Так, если Вам наступили в транспорте на ногу в первый раз — Вы вежливо поморщитесь, тоже воздействие на второй раз вызовет недовольную гримасу, ну а в третий раз...)

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

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


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

( H) Написать функцию , возвращающую 1, если и 0 в противном случае. Использовать только операцию сравнения .

( H) Написать функцию , не используя рекурсии.


Программу можно записать при помощи только натуральных чисел. Для этого необходимо воспользоваться низкоуровневым языком программирования ZIPPER. В нём есть только пять команд:

Невозможно разобрать выражение (неизвестная функция «\begin{array}»): {\displaystyle \begin{array}{l|l|l} команда &код & описание\\ \hline Z(7) &1, 7, 0, 0 & m_7\leftarrow 0:\;обнулить\;ячеку\;7\\ I(7) &2, 7, 0, 0 & m_7\leftarrow m_7+1:\;увеличить\;значение\;ячейки\;7\\ P(7,5 ) &3, 7, 5, 0 & m_7\leftarrow m_5:\;присвоить\;ячеке\;7\;значение\;ячейки\;5 \\ E(7,5,1)&4, 7, 5, 1 & если\;m_7=m_5\;перейти\;к\;команде\;1\\ R(7) &5, 7, 0, 0 & \mathbf{return}\;m_7\\ \end{array}}

Таким образом, программа состоит из натуральных чисел. Каждая команда является четвёркой, первым числом которой идёт её идентификатор (число от 1 до 5, или для мнемоники буквы , , , , ). Затем следуют три параметра. Если они не существенны, стоит 0. При переходе (команда ) метки не нужны, так как длина команд фиксирована, и достаточен только номер команды. Например программа:

выглядит так (команды нумеруются с единицы):

Невозможно разобрать выражение (синтаксическая ошибка): {\displaystyle Z,2,0,0,\;E,1,2,7,\;I,2,0,0,\;Z,3,0,0,\;Z,4,0,0,\;E,3,4,2,\;R,2,0,0\\}


( H) Записать программу для сложения целых чисел от 1 до числа в ячейке при помощи языка ZIPPER.

( H) Придумать язык команд только с двумя параметрами, а не тремя.

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

( H) Какую возможность языка BASE, язык ZIPPER не выражает, и что надо в него добавить?

 Первоначально, идеальный компьютер, который придумал Алан Тьюринг имел вид очень низкоуровневого устройства не умеющего даже складывать. Машина Тьюринга является автоматом, который может находится в одном из  состояний . Например,  (). Существует строка с входными данными, состоящая из символов некоторого алфавита с  буквами, например,  (), где "" — это пустой символ, который окружает исходную строку слева и справа сколь угодно много раз. Задача машины — переработать данную входную строку в другую (выходную) и остановиться. Для этого она устанавливает указатель (головку машины) на фиксированный символ строки (например, первый), а своё состояние в начальное (например ) и затем исполняет программу, заданную в виде таблицы:
Невозможно разобрать выражение (неизвестная функция «\multicolumn»): {\displaystyle \begin{array}{|c|c|c|c|c|c|c|c|c|} \multicolumn{1}{l}{}\\ \hline \_& b & a & b & a & b & \_ & \_\\ \hline \multicolumn{1}{l}{} & \multicolumn{1}{c}{\vartriangle} \\ \end{array} \;\;\;\;\;\;\;\;\;\;\;\; \begin{array}{c|c|c|c|} \multicolumn{1}{c}{} & \multicolumn{1}{c}{a} & \multicolumn{1}{c}{b} & \multicolumn{1}{c}{\_}\\ \cline{2-4} s_1& bs_1R & as_1R & \_ s_2 L \\ \cline{2-4} s_2& bs_2L & as_2L & \_ \bullet R \\ \cline{2-4} \end{array}}

В таблице по горизонтали перечисленны все буквы алфавита, а по вертикали — все состояния машины. Каждая ячейка содержит инструкцию, что делать, если текущее состояние машины , а её указатель стоит в строке на символе . Каждая инструкция типа состоит из трёх действий: 1) текущий символ в строке заменить на ; 2) сдвинуть указатель по строке влево, если стоит буква , вправо — если ; 3) изменить состояние на , или если стоит точка остановиться. Если буквы нет остаться на месте.

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


( H) Пользуясь инструкциями в таблице выше, описать последовательные преобразования входной строки "".

( H) Рассмотреть алфавит и написать программу для задачи превращения нулей в единицы и наоборот.

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

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


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


Вычислимые функции и их алгоритмы << Оглавление >> Проблемы остановки и тождественности

Истинность и доказуемость - о конструктивной математике, Канторе и Гёделе