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

Материал из synset
Перейти к: навигация, поиск
 
(не показаны 2 промежуточные версии этого же участника)
Строка 27: Строка 27:
 
Напомню, что мы работаем только с целыми неотрицательными числами (0,1,2,....), поэтому приходим к первой (в длинной цепочке <math>\textstyle \ddot\smile</math>) алгоритмической неприятности. Функция <math>\textstyle \mathbf{p}(x)</math>, хотя описывается алгоритмом (она вычислима), определена не для всех значений <math>\textstyle x</math>. В частности, для нуля нет предыдущего значения, и <math>\textstyle \mathbf{p}(0)</math> не доберётся до команды '''return'''. Если в ячейке <math>\textstyle m_0</math> находится 0, то условие в круглых скобках цикла '''while''' не сработает, и тело цикла (в фигурных скобках) будет пропущено. Вычислитель дойдёт до конца программы функции и остановится, так как команды '''return''' там нет, но и текст алгоритма закончился.
 
Напомню, что мы работаем только с целыми неотрицательными числами (0,1,2,....), поэтому приходим к первой (в длинной цепочке <math>\textstyle \ddot\smile</math>) алгоритмической неприятности. Функция <math>\textstyle \mathbf{p}(x)</math>, хотя описывается алгоритмом (она вычислима), определена не для всех значений <math>\textstyle x</math>. В частности, для нуля нет предыдущего значения, и <math>\textstyle \mathbf{p}(0)</math> не доберётся до команды '''return'''. Если в ячейке <math>\textstyle m_0</math> находится 0, то условие в круглых скобках цикла '''while''' не сработает, и тело цикла (в фигурных скобках) будет пропущено. Вычислитель дойдёт до конца программы функции и остановится, так как команды '''return''' там нет, но и текст алгоритма закончился.
  
−
Физический компьютер может в этот момент замигать лампочками, перегрузить операционную систему или покрыть небо звёздами. Наш идеальный компьютер просто "зависнет". Мы не можем написать в конце программы, например <math>\textstyle \mathbf{return}\;0;</math>, так как это уже будет другая функция (не предыдущего числа). Нельзя и вернуть не число, а например строку "NAN", так как в других функциях <math>\textstyle \mathbf{p}(m_0)</math> используется в арифметических вычислениях, да и нет "NAN"-а в нашем синтаксисе. Таким образом: \it вычислять, не значит вычислить. Например, вычислимой будет и такая функция: <math>\textstyle \mathbf{f}(m_0)\{\;\mathbf{while}(1=1)\{\}\;\}</math>.
+
Физический компьютер может в этот момент замигать лампочками, перегрузить операционную систему или покрыть небо звёздами. Наш идеальный компьютер просто "зависнет". Мы не можем написать в конце программы, например <math>\textstyle \mathbf{return}\;0;</math>, так как это уже будет другая функция (не предыдущего числа). Нельзя и вернуть не число, а например строку "NAN", так как в других функциях <math>\textstyle \mathbf{p}(m_0)</math> используется в арифметических вычислениях, да и нет "NAN"-а в нашем синтаксисе. Таким образом: ''вычислять, не значит вычислить''. Например, вычислимой будет и такая функция: <math>\textstyle \mathbf{f}(m_0)\{\;\mathbf{while}(1=1)\{\}\;\}</math>.
  
 
<math>\textstyle \bullet</math> Определим теперь ещё одну функцию <math>\textstyle \mathbf{mult}(x,y)</math> умножения двух целых чисел. Для целей дальнейшего анализа мы снова выберем не самый эффективный способ. Однако, он проиллюстрирует важную концепцию программирования &mdash; ''рекурсию'':
 
<math>\textstyle \bullet</math> Определим теперь ещё одну функцию <math>\textstyle \mathbf{mult}(x,y)</math> умножения двух целых чисел. Для целей дальнейшего анализа мы снова выберем не самый эффективный способ. Однако, он проиллюстрирует важную концепцию программирования &mdash; ''рекурсию'':
Строка 81: Строка 81:
 
выглядит так (команды нумеруются с единицы):
 
выглядит так (команды нумеруются с единицы):
  
−
:<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>
  
 
(<math>\textstyle \lessdot</math> H) Записать программу для сложения целых чисел от 1 до числа в ячейке <math>\textstyle m_0</math> при помощи языка ZIPPER.
 
(<math>\textstyle \lessdot</math> H) Записать программу для сложения целых чисел от 1 до числа в ячейке <math>\textstyle m_0</math> при помощи языка ZIPPER.
Строка 91: Строка 95:
 
(<math>\textstyle \lessdot</math> H) Какую возможность языка BASE, язык ZIPPER не выражает, и что надо в него добавить?
 
(<math>\textstyle \lessdot</math> H) Какую возможность языка BASE, язык ZIPPER не выражает, и что надо в него добавить?
  
−
<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>[[File:logic7.png]]</center>
  
 
В таблице по горизонтали перечисленны все буквы алфавита, а по вертикали &mdash; все состояния машины. Каждая ячейка <math>\textstyle \left\langle s_i, a_j\right\rangle </math> содержит инструкцию, что делать, если текущее состояние машины <math>\textstyle s_i</math>, а её указатель стоит в строке на символе <math>\textstyle a_j</math>. Каждая инструкция типа <math>\textstyle a_ks_pL</math> состоит из трёх действий: 1) текущий символ в строке заменить на <math>\textstyle a_k</math>; 2) сдвинуть указатель по строке влево, если стоит буква <math>\textstyle L</math>, вправо &mdash; если <math>\textstyle R</math>; 3) изменить состояние на <math>\textstyle s_p</math>, или если стоит точка остановиться. Если буквы нет остаться на месте.
 
В таблице по горизонтали перечисленны все буквы алфавита, а по вертикали &mdash; все состояния машины. Каждая ячейка <math>\textstyle \left\langle s_i, a_j\right\rangle </math> содержит инструкцию, что делать, если текущее состояние машины <math>\textstyle s_i</math>, а её указатель стоит в строке на символе <math>\textstyle a_j</math>. Каждая инструкция типа <math>\textstyle a_ks_pL</math> состоит из трёх действий: 1) текущий символ в строке заменить на <math>\textstyle a_k</math>; 2) сдвинуть указатель по строке влево, если стоит буква <math>\textstyle L</math>, вправо &mdash; если <math>\textstyle R</math>; 3) изменить состояние на <math>\textstyle s_p</math>, или если стоит точка остановиться. Если буквы нет остаться на месте.

Текущая версия на 16:32, 29 августа 2010

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

Рассмотренный язык BASE является достаточно "высокоуровневым" и может быть сведен к ещё более простым элементам. Однако, если бы программисты были ограничены даже перечисленным синтаксисом, их можно было бы только пожалеть. Для повышения выразительности языка вводятся разнообразные расширения обозначений, которые, однако, однозначным образом расшифровываются в терминах базового синтаксиса. Поэтому, перед выполнением программы, её необходимо компилировать, т.е. преобразовать входную строку программы с расширенным алфавитом в другую, с более лаконичным. Например, если в тексте встречается символ "Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \neq} " (не равно), то необходима такая "компилляция":

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \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;}

На месте букв Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle x} и Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle y} могут стоять Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle m_i} и Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle m_j} с любыми индексами Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle i} и Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle j} . Стрелка "Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle =>} " обозначает компиляцию исходной строки в новую, "понимаемую" компьютером. Исходный текст подразумевает, что если Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle x\neq y} , то выполняется Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal P_1 \mathcal P_2} , если же нет (т.е. Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle x=y} ), то выполняется только Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal P_2} . Именно это и происходит в преобразованной программе.

Аналогично можно определить инструкции для проведения циклических вычислений. Так, ниже слева приведен исходный программы, которая вычисляет сумму натуральных чисел до числа хранящегося в ячейке Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle m_0} включительно. Справа от черты, та же функция после компилляции (т.е. приведения в исходный синтаксис):

Logic4.png

В расширенном синтаксисе считается, что часть программы, находящаяся внутри фигурных скобок, после команды цикла Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{while}(условие)} повторяется до тех пор, пока условие срабатывает (в нашем случае, пока счётчик чисел в ячейке Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle m_1} меньше, чем число в Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle m_0} ). На самом деле первые строки не нужны, так как по договорённости, перед запуском программы все ячейки её памяти обнуляются.

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \bullet} Расширение синтаксиса, требующее переделки компиллятора (а это тоже алгоритм!), — не единственный способ усиливать выразительность языка. Например, в базовом синтаксисе нет функции получения предыдущего целого числа (т.е. вычитания единицы). Поэтому можно добавить функцию проводящую такие вычисления, и в других функциях её вызывать. Приведём, например, такой вариант:

Logic5.png

Для читаемости функция названа "Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{p}} ", однако необходимо помнить, что это на самом деле что-то типа: "Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle f_{137}} ".

В Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{p}(m_0)} происходит перебор всех чисел начиная с нуля (переменная Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle m_1} ) до тех пор, пока следующее после Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle m_1} число (Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle m_2} ) не окажется равным входному аргументу Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle m_0} . Этот алгоритм назвать быстрым сложно, но нас сейчас это не должно заботить.

Напомню, что мы работаем только с целыми неотрицательными числами (0,1,2,....), поэтому приходим к первой (в длинной цепочке Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \ddot\smile} ) алгоритмической неприятности. Функция Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{p}(x)} , хотя описывается алгоритмом (она вычислима), определена не для всех значений Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle x} . В частности, для нуля нет предыдущего значения, и Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{p}(0)} не доберётся до команды return. Если в ячейке Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle m_0} находится 0, то условие в круглых скобках цикла while не сработает, и тело цикла (в фигурных скобках) будет пропущено. Вычислитель дойдёт до конца программы функции и остановится, так как команды return там нет, но и текст алгоритма закончился.

Физический компьютер может в этот момент замигать лампочками, перегрузить операционную систему или покрыть небо звёздами. Наш идеальный компьютер просто "зависнет". Мы не можем написать в конце программы, например Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{return}\;0;} , так как это уже будет другая функция (не предыдущего числа). Нельзя и вернуть не число, а например строку "NAN", так как в других функциях Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{p}(m_0)} используется в арифметических вычислениях, да и нет "NAN"-а в нашем синтаксисе. Таким образом: вычислять, не значит вычислить. Например, вычислимой будет и такая функция: Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{f}(m_0)\{\;\mathbf{while}(1=1)\{\}\;\}} .

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \bullet} Определим теперь ещё одну функцию Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{mult}(x,y)} умножения двух целых чисел. Для целей дальнейшего анализа мы снова выберем не самый эффективный способ. Однако, он проиллюстрирует важную концепцию программирования — рекурсию:

Logic6.png

Для повышения читаемости, мы снова вместо номера функции пишем имя "Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{mult}} ", а вместо входных ячеек памяти Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle m_0} и Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle m_1} переменные Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle x} и Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle y} . Кроме этого несколько расширен синтаксис, и в один приём производится вычисление двух функций "Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{p}} ", "Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{mult}} ", и затем выполняется сложение. В исходном синтаксисе третий Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{return}} должен был бы выглядеть так:

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle m_2\leftarrow \mathbf{p}(m_1);\;\;\;m_3\leftarrow \mathbf{mult}(m_0, m_2);\;\;\;m_2\leftarrow m_2+m_3;\;\;\;\;\mathbf{return}\;m_2;}

Поэтому в записи Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle x+\mathbf{mult}\bigl(x,\mathbf{p}(y)\bigr)} сначала происходит определение первого аргумента функции "Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{mult}} " (это просто число Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle x} ), затем вычисляется функция Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{p}(y)} и её значение помещается во второй аргумент "Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{mult}} ", и только после этого происходит её вычисление. В дальнейшем предполагается, что подобные выражения всегда вычисляются слева направо, хотя понятно, что при помощи ячеек памяти можно реализовать любой порядок вычисления аргументов функции.

Алгоритм Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{mult}(x,y)} вызывает две функции, одна из которых снова "Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{mult}} ". Функция, которая при своём вычислении использует себя же саму, называется рекурсивной.

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

В функции Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{mult}(x,y)} происходит следующее. Если Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle y=0} , то её результат равен 0 , а если Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle y=1} , то Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle x} . Если же Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle y} больше единицы, то мы пользуемся "очевидной" арифметической формулой Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle x*y=x+(x*(y-1))} . При каждом вызове Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{mult}(x,\mathbf{p}(y))} значение второго аргумента уменьшается, поэтому рано или поздно сработает вторая строка алгоритма.

Например, справедлива следующая цепочки формул для Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle x=4} , Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle y=3} :

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \mathbf{mult}(4, 3),\;\;это\;\;4+\mathbf{mult}(4,2),\;\;это\;\;4+(4+\mathbf{mult}(4,1)),\;\;это\;4+(4+4).}

Ответ на каждое "это" производится отдельным вычислителем. Понятно, что такие действия приведут к результату только если цепочка рекурсивных вызовов когда-либо закончится. Например, если в приведенной выше программе Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{mult}(x,y)} убрать первые два return, то функция никогда не выдаст результата. При этом будет порождено, вообще говоря, конечное число вычислителей. Однако, последний из них внутри функции Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{p}(0)} остановится не достигнув return, и сделает самую первую функцию не определённой.

Ещё хуже будет ситуация, если в алгоритме заменить "Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{mult}(x,\mathbf{p}(y))} ", например на Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{mult}(x,y+1)} . Мы получим бесконечную цепочку:

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \mathbf{mult}(4, 3),\;\;это\;\;4+\mathbf{mult}(4,4),\;\;это\;\;4+(4+\mathbf{mult}(4,5)),\;\;\;это\;\;\;...}

Теперь компьютер не только не получит значение функции, но и будет порождать всё новые вычислители и их память. Для реального компьютера, создающего цепочку таких "вычислителей", рано или поздно закончатся ресурсы, и он "умрёт". Идеальный компьютер будет работать бесконечно долго, а следовательно подобная функция не определена ни при каких Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle x>1} (при Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle x=0} и Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle x=1} сработают первые две строчки), и является частично вычислимой или просто частичной.

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \bullet} Заканчивая расширения синтаксиса описания алгоритмов при помощи функций, введём ещё глобальную память Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal G = \{g_0, g_1, g_2,...\}} . Как и для памяти каждого вычислителя — это множество упорядоченных неотрицательных целых чисел. К ним может обращаться любой вычислитель, перемещающийся по некоторой функции. Другими словами, в тексте программ функций могут встречаться как Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle m_i} , так и Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle g_i} . После создания или уничтожения вычислителей, память Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal G} сохраняется. Таким образом, это общая память которую можно изменять из любой функции.

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

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \bullet} Рассмотрим несколько задач, решение которых может быть найдено в приложении "Помощь" под соответствующим номером.

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \triangleright} Базовый язык алгоритмов может быть упрощён. На самом деле, достаточно единственной арифметической функции прибавления единицы (следующее натуральное число) и логического равенства.

(Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \lessdot} H) Написать при помощи базового синтаксиса программирования функцию сложения двух чисел Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{add}(x,y)} , используя только функцию Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle m_i\leftarrow m_j+1} . Рекурсию не применять.

(Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \lessdot} H) Написать функцию Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{lt}(x,y)} , возвращающую 1, если Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle x<y} и 0 в противном случае. Использовать только операцию сравнения Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle x=y} .

(Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \lessdot} H) Написать функцию Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{mult}(x,y)=x*y} , не используя рекурсии.

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \triangleright} Программу можно записать при помощи только натуральных чисел. Для этого необходимо воспользоваться низкоуровневым языком программирования ZIPPER. В нём есть только пять команд:

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\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}}

Таким образом, программа состоит из Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle 4\cdot n} натуральных чисел. Каждая команда является четвёркой, первым числом которой идёт её идентификатор (число от 1 до 5, или для мнемоники буквы Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle Z} , Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle I} , Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle P} , Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle E} , Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle R} ). Затем следуют три параметра. Если они не существенны, стоит 0. При переходе (команда Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle E} ) метки не нужны, так как длина команд фиксирована, и достаточен только номер команды. Например программа:

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle m_2\leftarrow 0;\;\;\#1;\;\;\mathbf{if}(m_1=m_2)\;\{\,\mathbf{return}\;m_2;\,\}\;\;m_2\leftarrow m_2+1;\;\;\mathbf{goto}(1);}

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

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\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 }

(Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \lessdot} H) Записать программу для сложения целых чисел от 1 до числа в ячейке Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle m_0} при помощи языка ZIPPER.

(Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \lessdot} H) Придумать язык команд только с двумя параметрами, а не тремя.

(Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \lessdot} H) На базовом языке BASE написать алгоритм выполнения программы на языке ZIPPER. На входе функции, в памяти содержится набор чисел — инструкций.

(Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \lessdot} H) Какую возможность языка BASE, язык ZIPPER не выражает, и что надо в него добавить?

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \triangleright} Первоначально, идеальный компьютер, который придумал Алан Тьюринг имел вид очень низкоуровневого устройства не умеющего даже складывать. Машина Тьюринга является автоматом, который может находится в одном из Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle m} состояний Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal S} . Например, Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal S: \{s_1,s_2\}} (Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle m=2} ). Существует строка с входными данными, состоящая из символов некоторого алфавита с Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle n} буквами, например, Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal A:\{a,b,\_\}} (Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle n=3} ), где "Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \_} " — это пустой символ, который окружает исходную строку слева и справа сколь угодно много раз. Задача машины — переработать данную входную строку в другую (выходную) и остановиться. Для этого она устанавливает указатель (головку машины) на фиксированный символ строки (например, первый), а своё состояние в начальное (например Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle s_1} ) и затем исполняет программу, заданную в виде таблицы:

Logic7.png

В таблице по горизонтали перечисленны все буквы алфавита, а по вертикали — все состояния машины. Каждая ячейка Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \left\langle s_i, a_j\right\rangle } содержит инструкцию, что делать, если текущее состояние машины Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle s_i} , а её указатель стоит в строке на символе Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle a_j} . Каждая инструкция типа Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle a_ks_pL} состоит из трёх действий: 1) текущий символ в строке заменить на Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle a_k} ; 2) сдвинуть указатель по строке влево, если стоит буква Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle L} , вправо — если Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle R} ; 3) изменить состояние на Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle s_p} , или если стоит точка остановиться. Если буквы нет остаться на месте.

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

(Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \lessdot} H) Пользуясь инструкциями в таблице выше, описать последовательные преобразования входной строки "Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle babab} ".

(Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \lessdot} H) Рассмотреть алфавит Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal A: \{0,1,\_\}} и написать программу для задачи превращения нулей в единицы и наоборот.

(Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \lessdot} H) Рассмотреть алфавит Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal A: \{1,\_\}} и написать программу сложения двух натуральных чисел, записанных в виде последовательностей единиц с пробелом между ними (т.е. пробел убрать, сдвинув второе число влево, объединив единицы чисел.)

(Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \lessdot} H) Рассмотреть алфавит Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathcal A: \{0,1,\_\}} и написать программу сортировки, переставляющей все нули в начало слова (до пробела), а единицы в конец.

(Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \lessdot} H) Написать на языке BASE программу, исполняющую инструкции машины Тьюринга. Размер алфавита и число состояний заданы в ячейках Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle m_0} , Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle m_1} . Далее идут записанные в первых Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle 3\cdot m_0\cdot m_1} ячейках таблица инструкций. Затем входная строка. При попытке сдвинуться влево на первом символе строки, она должна быть сдвинута вправо. Можно использовать любые разумные расширения синтаксиса BASE.


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

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