Автор: Пользователь скрыл имя, 18 Декабря 2011 в 21:15, доклад
Современное формальное определение алгоритма было дано в 30—50-х годы XX века в работах Тьюринга, Поста, Чёрча (тезис Чёрча — Тьюринга), Н. Винера, А. А. Маркова.
Само слово «алгоритм» происходит от имени персидского учёного Абу Абдуллах Мухаммеда ибн Муса аль-Хорезми (алгоритм — аль-Хорезми). Около 825 года он написал сочинение, в котором впервые дал описание придуманной в Индии позиционной десятичной системы счисления. К сожалению, персидский оригинал книги не сохранился. Аль-Хорезми сформулировал правила вычислений в новой системе и, вероятно, впервые использовал цифру 0 для обозначения пропущенной позиции в записи числа (её индийское название арабы перевели как as-sifr или просто sifr, отсюда такие слова, как «цифра» и «шифр»).
Одним из важнейших инструментов теории моделей является теорема компактности, доказанная Мальцевым, которая утверждает, что множество формул первого порядка имеет модель тогда и только тогда, когда модель имеет каждое его конечное подмножество.
Название теоремы связано с тем, что она может быть сформулирована как утверждение о компактности стоуновского пространства.
Из теоремы компактности
следует, что некоторые понятия не являются
выразимыми в логике первого порядка.
Например, понятия конечности или счётнос
Теорема компактности находит применение для конструирования нестандартных моделей классических теорий, например, элементарной арифметики или математического анализа.
Информация о работе История формирования "понятия алгоритмов"