dmitgu

Category:

Программа Гильберта-2 для теории алгоритмов: модель работы алгоритмов

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

Оглавление 

0. Введение

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

2. Условности языков программирования высокого уровня и факты «низкого» уровня

3. Запись алгоритмов в «каноническом» виде

4. «Физика» используемой модели алгоритмов. Сравнение с машиной Тьюринга

0. Введение 

В первой статье «Программа Гильберта-1 для теории алгоритмов: теория слов (строк)» были сформулирована необходимость проведения программы Гильберта в теории алгоритмов, и была создана (на уровне аксиом) теория строк. Строки – это то, с чем работают математики в теории алгоритмов:

Вместо термина «строки» (термин программистов) математики обычно используют термин «слово» для «языка», например. Строки – это то, что записано на ленте машины Тьюринга, например. Строки («слова») – это «цепочки символов» в самых разных применениях теории алгоритмов.

В данной (2-й) статье будет построена модель работы алгоритмов, отличающаяся от машины Тьюринга. Это позволит проще формализовать понятие алгоритма в рамках теории строк – что будет сделано в следующей (3-й) статье, после данной. 

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

В первой статье была сформулирована необходимая теория строк, во второй статье (данной) будет построена модель работы алгоритмов, в третьей (следующей) – будет формализовано понятие алгоритма средствами теории строк. 

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.