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 для перехода в нужную «точку возврата». Всякие модернизации в направлении организации стека возвратов и т.п. – тоже легко реализуются.