Программа Гильберта-2 для теории алгоритмов: модель работы алгоритмов
. К оглавлению . Показать весь текст .
Оглавление
1. Понятие о модели работы алгоритмов и их представимости в теории
2. Условности языков программирования высокого уровня и факты «низкого» уровня
3. Запись алгоритмов в «каноническом» виде
4. «Физика» используемой модели алгоритмов. Сравнение с машиной Тьюринга
0. Введение
В первой статье «Программа Гильберта-1 для теории алгоритмов: теория слов (строк)» были сформулирована необходимость проведения программы Гильберта в теории алгоритмов, и была создана (на уровне аксиом) теория строк. Строки – это то, с чем работают математики в теории алгоритмов:
Вместо термина «строки» (термин программистов) математики обычно используют термин «слово» для «языка», например. Строки – это то, что записано на ленте машины Тьюринга, например. Строки («слова») – это «цепочки символов» в самых разных применениях теории алгоритмов.
В данной (2-й) статье будет построена модель работы алгоритмов, отличающаяся от машины Тьюринга. Это позволит проще формализовать понятие алгоритма в рамках теории строк – что будет сделано в следующей (3-й) статье, после данной.
После того, как будет формализовано понятие алгоритма, откроется возможность в рамках теории строк исследовать и алгоритмы, и саму теорию строк средствами, аналогичными алгоритмам. А это, в свою очередь, позволит формализовать понятие «сложность» - потому что «сложность» - понимается как сложность с точки зрения алгоритмов. Но пока не формализовано понятие алгоритма в рамках теории – невозможно в рамках теории выразить и само понятие «сложность с точки зрения алгоритмов».
В первой статье была сформулирована необходимая теория строк, во второй статье (данной) будет построена модель работы алгоритмов, в третьей (следующей) – будет формализовано понятие алгоритма средствами теории строк.
