dmitgu.livejournal - Как же устроен мир?

. К оглавлению . Показать весь текст .

Оглавление 

0. Введение

1. Понятие о модели работы алгоритмов и их представимости в теории

2. Условности языков программирования высокого уровня и факты «низкого» уровня

3. Запись алгоритмов в «каноническом» виде

4. «Физика» используемой модели алгоритмов. Сравнение с машиной Тьюринга

0. Введение 

В первой статье «Программа Гильберта-1 для теории алгоритмов: теория слов (строк)» были сформулирована необходимость проведения программы Гильберта в теории алгоритмов, и была создана (на уровне аксиом) теория строк. Строки – это то, с чем работают математики в теории алгоритмов:

Вместо термина «строки» (термин программистов) математики обычно используют термин «слово» для «языка», например. Строки – это то, что записано на ленте машины Тьюринга, например. Строки («слова») – это «цепочки символов» в самых разных применениях теории алгоритмов.

В данной (2-й) статье будет построена модель работы алгоритмов, отличающаяся от машины Тьюринга. Это позволит проще формализовать понятие алгоритма в рамках теории строк – что будет сделано в следующей (3-й) статье, после данной. 

. К оглавлению . Показать весь текст .

В теории Пеано (и арифметике) «представимы» всякие функции. Но подобная «представимость» никак не может устроить нас в теории алгоритмов. 

Итак, насчёт «представимости» в арифметике и в общем случае: 

Для функции f(x), которая при значении аргумента x возвращаете результат y (f(x) = y) мы внутри теории используем логическую формулу F(x, y), которая истинна (имеется её доказательство в теории) для любых правильных значений i, j (где i, j являются уже не переменными, а конкретными значениями – какими -то числами, если речь про арифметику – 5 и 121, например) на месте x, y соответственно.:

Если f(i) = j, то ⊢ F(i, j). Где значок «⊢» обозначает тут выводимость данной формулы с данными значениями аргументов в рассматриваемой нами теории.

А если значения i, j не соответствуют такому равенству, то должно быть доказано его отрицание:

Если f(i) ≠ j, то ⊢ ~F(i, j). 

Вот если для функции f(x) имеется такое соответствие с формулой F(x, y) в теории, то говорят, что функция f(x) представима в данной теории формулой F(x, y). На месте x может стоять любое количество аргументов в общем случае.

Никакой представимости для алгоритмов, получающих, работающих и возвращающих строки, в арифметике – нет. Потому, что в арифметика нет строк. 

. К оглавлению . Показать весь текст .

Тут можно углубляться в нюансы – например, арифметические действия нужно всё же определить как подпрограммы через строковые операции, а не считать, что они готовые функции для строк типа «1678». И можно построить предыдущую программу, не обращаясь к арифметическим операциям, а используя: 

i = Comp(«Мама мыла раму», x);

Для получения меток так:

mark = «[next_1_» ⋅ i ⋅ «]»;

И метки [next_1_1], [next_1_2] ставить рядом в программе – чтоб они приводили к одному и тому же переходу. А для случая:

i = Comp(«Папа строил баню», x);

генерировать уже метки [next_2_0], [next_2_1], [next_2_2].

Перепишем программу уже без использования арифметических операций:

. К оглавлению . Показать весь текст .

Мы увидели, что на самом деле «окончательный» текст программы (после его «компиляции» с «языка среднего уровня» - который использует композиции и приоритеты операций в строках программы, например) мы получили такой программный текст, где каждая строка содержит не больше 2 операций. И самый сложный случай, когда:

1. Есть операция присваивания, и есть та функция, которая даёт значение для этого присваивания. Притом данная функция – одна из «базовых» (из ограниченного набора), без всяких «композиций» нескольких операций. 

Второй по сложности случай:

2. Оператор goto – который тоже аналог операции присваивания – только присваивания нужного адреса той «переменной», которая указывает на точку исполнения программы. А после оператора goto расположена или переменная, или константа, которая содержит метку, обозначающую нужный адрес.

И последние, самые простые случаи:

3. Оператор метки – который в процессе работы просто пропускается, не вызывая никаких изменений в какой-либо переменной или месте исполнения программы, кроме перехода к исполнению следующей за данной меткой операции в программе. И последний простой случай – оператор остановки «.».

Перечислим все варианты строк программы (с указанием конкретных операторов), которые могут быть в тексте нашей программы в «откомпилированном» виде. Будем считать, что программный текст, составленный по нижеследующим правилам записан в «каноническом» виде.

. К оглавлению . Показать весь текст .

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

Во-первых, не одна «лента», а множество «полулент» Тьюринга, которые все своим началом сходятся в одной точке к «процессору». Это – строки (и числа, которые представлены в виде строк). Каждой переменной соответствует своя «полулента» Тьюринга, начало которой соответствует 1-му символу данной строки (если строка не пустая).

Во-вторых, в данной модели нет «тележки», которая может как угодно долго «блуждать» вдали от начальной точки. 

Чтобы получить информацию из нужного места строки – надо каждый раз «дойти» до нужного места строки, забрать нужную информацию и доставить её обратно к «процессору». 

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

Чем дальше от начала строки находятся нужные нам символы – тем дольше (прямо пропорционально дольше) до них добираться. Добираемся мы с целью чтения этих данных или замены этих данных на нужные данные.