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

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

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

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

Для функции 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 может стоять любое количество аргументов в общем случае.

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

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

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

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

Модель «машины Тьюринга» является не очень удобной в свете десятилетий колоссального практического развития вычислительной техники, которые миновали после создания Тьюрингом его модели. Мы чуть позже рассмотрим отличия моделей и то, зачем нам нужна новая модель. 

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

Что мне приходит в голову: Кроме функций str(), Chr(), Comp() и конкатенации необходима операция присваивания (в том числе и в нужное место строки) и операция перехода к метке при работе программы. А шаги программы можно ставить друг за другом, разделяя точкой с запятой, а последний оператор заканчивается точкой. 

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

Программа должна рассматриваться как строка, в которой можно искать подстроки и делать другие строковые операции. 

Например, в переменной Program находится текст программы, в переменной i_Program – положение «точки исполнения» в строке Program. А результат своей работы программа должна записать в переменную Return. На вход в переменную x подаётся информация, которая представляет собой один вариант из следующих трёх:

1. «Мама мыла раму»

2. «Папа строил баню»

3. Другие варианты

И надо выдать на 1-й вариант: «Маме выдать печеньки»

На 2-й вариант: «Папе выдать пива»

На другие варианты: «Что происходит?»

Вот программа (напоминаю, что «вход» - переменная x, «выход» - переменная Return):

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

mark = str(«[exit_1]» ⋅ «[next_1]» ⋅ «[next_1]», i * 8 + 1, 8);

goto mark;

[next_1];

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

mark = str(«[exit_2]» ⋅ «[exit_3]» ⋅ «[exit_3]», i * 8 + 1, 8);

goto mark;

[exit_1];

Return = «Маме выдать печеньки»;

goto «[end]»;

[exit_2];

Return = «Папе выдать пива»;

goto «[end]»;

[exit_3];

Return = «Что происходит?»;

[end].

Замечу, что в приведённой программе числовые аргументы понимаются как числа в позиционном представлении. С заранее оговоренной «ичностью». Я уже приводил в предыдущей статье аксиомы, которые позволяют понимать числа именно таким образом. Поэтому у нас в теории строк есть возможность сформулировать правила арифметических действий для строкового позиционного представления чисел, для которого верны все аксиомы арифметики.

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

a(i) = b;

И при таком присваивании в строке a все символы, начиная с позиции i включительно и до позиции i + len(b) -1 включительно будут заменены на символы строки b, а остальная часть строки a останется прежней. Если b – пустая строка, то строка a не меняется. В то же время «обычное» присваивание

a = b;

сделает строку a пустой, если пустой является строка b.

Сделаем важную оговорку:

Будем считать, что очистка переменной происходит «моментально». Пусть – за один шаг с момента доступа к началу данной переменной. Как именно происходит такая «очистка» на «физическом» уровне? Она происходит, например, при помощи спец. символа, который всегда стоит в конце строки, которую содержит переменная и который никак не используется в написании программ. А всё, что стоит после этого спец символа – продолжением строки не считается – как и сам этот спец. символ. Тогда для «очистки» переменной нет нужды удалять все символы в ней – а просто можно поставить специальный символ на первое место.

В разделе 4 скажем чуть подробнее о «физической» стороне использованной модели программирования – тогда станет понятней картина в целом и оговорка «с момента доступа к началу переменной».

Тогда пустая строка создаётся неким специальным символом, который стоит на первом месте строки. А строка – это то, что расположено до него (то есть – ничего, пустая строка, потому что позиции ноль в строке нет). 

И будем считать, что «обычное» присваивание переменной некоторого значения занимает не больше времени, чем очистка данной переменной (моментальная) и заполнение этой пустой (после предыдущей очистки) переменной новой строкой в качестве значения. 

Еще пример: Если a = «сядь на пенёк, съешь пирожок», то после операции присваивания

a(16) = «не ешь пирожок»;

Будет верным a = «сядь на пенёк, не ешь пирожок»

А если вместо разобранного присваивания было бы такое присваивание:

a(16) = «не»;

то будет верным a = «сядь на пенёк, неешь пирожок.

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

a(160) = «не»;

то будет верным a = «сядь на пенёк, съешь пирожокне». 

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

a() = «не»;

Если исполнить последнее присваивание вместо предыдущего, то будет верным: a = «сядь на пенёк, съешь пирожокне». 

Результат получился тот же, что был в предыдущем примере с a(160). Можно добиться того же результата конструкций вида:

a(len(a)) = «не»;

Но мы же не запрограммировали функцию len() – мы же сейчас обсуждаем модель работы алгоритмов, а не теорию строк. И «выдумываем» те базовые возможности, которые были бы удобны даже не специалистам в понимании программирования, и в то же время удобны для представления алгоритмов в теории строк. А добавленная нами возможность «дописывать в конец» позволит нам избавиться от операции конкатенации в качестве базовой функции в нашей модели работы алгоритмов – что мы увидим в разделе 3. 

Как видим, «частичное присваивание» не меняет ту часть строки, которая находится вне размеров присваиваемой части. И время, которое тратится на такое присваивание такое же, как если бы неизменный в данном присваивании «хвост» строки был пустым.

А вот присваивание «обычное» делает значение переменной равной тому, что ей присваивается. Например, если бы вместо разобранных присваиваний с той же переменной a проделать «обычное» присваивание:

a = «не ешь пирожок»;

то будет верным a = «не ешь пирожок». 

Для целей большего единообразия (возможности применять одну и ту же конструкцию «частичного присваивания» и для «обычного» присваивания) примем соглашение, что «обычное» присваивание совпадает с присваиванием «частичным», с места 0 (ноль). Например, результат следующих двух присваиваний будет одинаковым, независимо от первоначального значения переменной a:

a = «не ешь пирожок»;

a(0) = «не ешь пирожок»; 

Оператор goto x можно рассматривать просто как поиск find(Program, ChrEnter ⋅ x) нужного текста в строке программы Program – можно считать, например, что метки всегда в квадратных скобках и всегда расположены после перевода строки (обозначено тут как ChrEnter). Тогда находить их можно только на границе строк. Метки не исполняются (как и переводы строки) – то есть, ничего не делают, а пропускаются при работе программы. А после того, как метка найдена в Program, её позиция присваивается переменной i_Program, что вызывает переход к исполнению программы в нужной позиции. Вот так работает команда goto x.

Разумеется, всё это позволяет организовывать и подпрограммы – достаточно присвоить в некую переменную имя метки как «точку возврата». И тогда в подпрограмме (которая тоже вызывается по goto) можно в конце исполнить goto для перехода в нужную «точку возврата». Всякие модернизации в направлении организации стека возвратов и т.п. – тоже легко реализуются.