dmitgu

Category:

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

Error

default userpic

Your reply will be screened

Your IP address will be recorded 

When you submit the form an invisible reCAPTCHA check will be performed.
You must follow the Privacy Policy and Google Terms of use.