dmitgu (dmitgu) wrote,
dmitgu
dmitgu

Category:

5.2. Теорема о построении алгоритма, применяемого к себе.

к Оглавлению

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

В процессе доказательства мы использовали произвольный алгоритм с одним аргументом B(X). Из него мы построили композицию B(diag(X)). И после того, как передали в качестве значения X программный код данного алгоритма для обработки самому алгоритму, мы получили алгоритм G(). Интересно то, что после такой подстановки в аргумент X, результат выражения diag(X) будет в точности равен программному коду алгоритма G().

Нам в данной работе далее будет интересно совсем не то, что алгоритм B(X) получает в X текст такого же алгоритма G(), которому он равен. Нам будет интересно следующее следствие леммы о диагонализации:

Теорема о построении алгоритма, применяемого к себе

На базе произвольного алгоритма с одним аргументом B(X) всегда можно построить такой алгоритм G(), что этот алгоритм G() получает в переменную X свой собственный программный код и работает с ним так же, как алгоритм B(X) работает с аргументом X.

Метод построения алгоритма G() на базе алгоритма В(X) чрезвычайно прост:

B(diag(«B(diag(x))»))

А теперь разберём практический пример – напишем программу, которая возвращает свой собственный программный код.

Самый доступный способ программирования для офисных работников – воспользоваться языком VBA в MS Words.

За основу берем оператор, который вставляет в документ значение из переменной х и завершает работу программы:

Selection.InsertAfter x: End Sub

Это та часть, в которой происходит работа со значением переменной x. Для простоты будем считать передачей аргумента операцию присваивания переменной соответствующего значения.

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

x = "Sub dolly(): x =" + Chr(34) + #Исходный_программный_код_в_виде_строки + Chr(34) + ": " + #Исходный_программный_код:

Всё просто – мы присваиваем «внешнему» x исходный программный код, но добавляем к этому тексту (перед ним) программный код присваивания «внутреннему» x того, что получили изначально во «внешнюю» переменную x (исходный программный код). Помимо операции присваивания нам надо поставить и инструкцию начало программы – "Sub dolly():", а операция присваивания требует заключать символы текста в кавычки. Всё это и проделано – пока схематически.

Теперь разберём #Исходный_программный_код_в_виде_строки.

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

x = "Текст1 без кавычек" + "Текст2 без кавычек" + … + Chr(34) + …

Где Chr(34) – как раз добавляют кавычки в текст. То есть, нам надо преобразовать исходное значение «внешнего» x в подобное выражение. И там, где в исходном значении стоят кавычки между Текст1 и Текст2, нам надо разрывать текст, добавляя кавычки программным образом:

x = "Текст1 без кавычек" + Chr(34) + "Текст2 без кавычек" + …

Поэтому #Исходный_программный_код_в_виде_строки можно получить так из исходной «внешней» переменной x:

Replace(x, Chr(34), Chr(34) + " + Chr(34) + " + Chr(34))

Этот кусочек программы заменяет в переменной x знак кавычек

<до кавычек>"<после кавычек>

на следующее:

<до кавычек>" + Chr(34) + "<после кавычек>

У знака кавычек есть смысл в программном коде как ограничитель строк, поэтому в значение переменной они не попадают. А вот Chr(34) генерирует кавычки и они становятся частью значения.

После этого перепишем абзац:

x = "Sub dolly(): x =" + Chr(34) + #Исходный_программный_код_в_виде_строки + Chr(34) + ": " + #Исходный_программный_код:"

Таким образом:

x = "Sub dolly(): x  =" + Chr(34) + Replace(x, Chr(34), Chr(34) + " + Chr(34) + " + Chr(34)) + Chr(34) + ": " + x:

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

x = "Sub dolly(): x  =" + Chr(34) + Replace(x, Chr(34), Chr(34) + " + Chr(34) + " + Chr(34)) + Chr(34) + ": " + x: Selection.InsertAfter x: End Sub

Теперь в соответствии с порядком действий из леммы о диагонализации нам надо присвоить этот программный код переменной x и выполнить его – применительно к изменённой переменной x.

Но для операции присваивания надо сделать ту же модификацию с данным программным кодом, что мы делали ранее с переменной x. Для того, чтобы получить код присваивания переменной x воспользуемся программой string_let_code. Это программа, которая по значению переменной (например, x) формирует тот программный код, который должен стоять справа в операторе присваивания (например, x), чтобы переменной присвоилось именно данное значение.

Sub string_let_code()

Dim x

x = InputBox("Введите значение для переменной " + _

  "и в текст будет выведен код, который надо будет написать" + _

  "справа от знака присваивания")

x = Replace(x, Chr(34), Chr(34) + " + Chr(34) + " + Chr(34))

x = Chr(34) + x + Chr(34)

Selection.InsertAfter x

End Sub

Предварительно скопируйте в «карман» предыдущий результат, запустите написанную только что программу,  введите по её запросу текст из «кармана» и программа выдаст в текущий документ в текущее положение каретки программный код для присваивания. Вот он:

"x = " + Chr(34) + "Sub dolly(): x  =" + Chr(34) + " + Chr(34) + Replace(x, Chr(34), Chr(34) + " + Chr(34) + " + Chr(34) + " + Chr(34) + " + Chr(34)) + Chr(34) + " + Chr(34) + ": " + Chr(34) + " + x:  Selection.InsertAfter x: End Sub"

Теперь делаем на базе полученного результата операцию присваивания (с инструкцией начала программы) и добавляем ранее полученный код (тот, который мы подставляли в строку запроса при запуске программы string_let_code):

Sub dolly(): x = "x = " + Chr(34) + "Sub dolly(): x  =" + Chr(34) + " + Chr(34) + Replace(x, Chr(34), Chr(34) + " + Chr(34) + " + Chr(34) + " + Chr(34) + " + Chr(34)) + Chr(34) + " + Chr(34) + ": " + Chr(34) + " + x:  Selection.InsertAfter x: End Sub": x = "Sub dolly(): x  =" + Chr(34) + Replace(x, Chr(34), Chr(34) + " + Chr(34) + " + Chr(34)) + Chr(34) + ": " + x:  Selection.InsertAfter x: End Sub

Запустите построенную программу, и она выдаст свой собственный программный код.


Tags: NP≠P дискуссии, ЖЖвЖЖ математика
Subscribe

  • Post a new comment

    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.
  • 0 comments