Алгоритмические числа это: Общие сведения о системах счисления

Общие сведения о системах счисления

Видеоурок: Общие сведения о системах счисления.

Система счисления — это знаковая система, в которой приняты определённые правила записи чисел.

Цифры —
знаки, при помощи которых записываются числа,.

Алфавит системы счисления — совокупность цифр.

Примеры:

Египетская система счисления

Древнеславянская система счисления

Вавилонская система счисления

Узловые числа  обозначаются
цифрами  —  0 1 2 3 4 5 6 7 8 9

Алгоритмические числа  получаются в
результате каких-либо операций из узловых чисел  — 4*100+5*10+8=458

Унарная система счисления

Простейшая и самая древняя система — так называемая унарная система счисления.

В ней для записи любых чисел используется всего один символ — палочка, узелок, зарубка, камушек.

 Примеры:

Непозиционная система счисления

Система счисления называется непозиционной, если количественный эквивалент (количественное значение) цифры в
числе не зависит от её положения в записи числа.

Здесь алгоритмические числа получаются путём сложения и вычитания узловых чисел с учётом следующего
правила:

 каждый меньший знак, поставленный справа от большего, прибавляется к его значению, а каждый меньший знак,
поставленный слева от большего, вычитается из него.

Позиционная система счисления

Система счисления называется позиционной, если количественный эквивалент цифры в числе зависит от её
положения в записи числа.

Основание позиционной системы счисления равно количеству цифр, составляющих её алфавит.

Алфавит десятичной системы составляют цифры 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

Десятичная система счисления

Цифры 1234567890 сложились в Индии около 400 г. н. э.

Арабы стали пользоваться подобной нумерацией около 800 г. н. э.

Примерно в 1200 г. н. э. эту нумерацию начали применять в Европе.

Основная формула

В позиционной системе счисления с основанием q любое число может быть представлено в виде:

Aq =±(a_n–1´q^n–1+
a_n–2
´ q^n–2+…+ a₀

´ q⁰+
a_–1´q^–1+…+ a_–m´
q^–m)

Здесь:

А — число;

q — основание системы
счисления;

a_i — цифры,
принадлежащие алфавиту данной системы счисления;

n — количество целых разрядов
числа;

m — количество дробных разрядов
числа;

qⁱ — «вес» i-го
разряда.

Такая запись числа называется развёрнутой формой записи.

Развёрнутая форма

Aq =±(a_n–1

´ q^n–1+
a_n–2
´ q^n–2+…+
a₀
´ q⁰+
a_–1
´ q^–1+…+
a_–m
´ q^–m)  

Примеры записи чисел в
развёрнутой форме:

2012=2´10³
+0´10²
+1´10¹
+2´10⁰

0,125=1´10^-1
+2´10^-2
+5´10^–3

14351,1=1´10⁴
+4´10³
+3´10²
+5´10¹
+1´10⁰
+1´10^–1

§ 1.1. Системы счисления

Информатика. 8 класса. Босова Л.Л. Оглавление

Ключевые слова:

• система счисления
• цифра
• алфавит
• позиционная система счисления
• основание
• развёрнутая форма записи числа
• свёрнутая форма записи числа
• двоичная система счисления
• восьмеричная система счисления
• шестнадцатеричная система счисления

1.1.1. Общие сведения о системах счисления

Система счисления — это знаковая система, в которой приняты определённые правила записи чисел. Знаки, с помощью которых записываются числа (рис. 1.1), называются цифрами, а их совокупность — алфавитом системы счисления.

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

Пример 1. У вавилонян узловыми являлись числа 1, 10, 60; в римской системе счисления узловые числа — это 1, 5, 10, 50, 100, 500 и 1000, обозначаемые соответственно I, V, X, L, С, D, М.

Рис. 1.1. Знаки, используемые для записи чисел в различных системах счисления

Системы счисления различаются выбором узловых чисел и способами образования алгоритмических чисел. Можно выделить следующие виды систем счисления:

• 1) унарная система;
• 2) непозиционные системы;
• 3) позиционные системы.

Простейшая и самая древняя система — так называемая унарная система счисления. В ней для записи любых чисел используется всего один символ — палочка, узелок, зарубка, камушек. Длина записи числа при таком кодировании прямо связана с его величиной, что роднит этот способ с геометрическим представлением чисел в виде отрезков. Именно унарная система лежит в фундаменте арифметики, и именно она до сих пор вводит первоклассников в мир счёта. Унарную систему ещё называют системой бирок.

Система счисления называется непозиционной, если количественный эквивалент (количественное значение) цифры в числе не зависит от её положения в записи числа.

Пример 2. В древнеегипетской системе счисления числа 1, 2, 3, 4, 10, 13, 40 обозначались соответственно следующим образом:

Те же числа в римской системе счисления обозначаются так: I, II, III, IV, X, XIII, XL. Здесь алгоритмические числа получаются путём сложения и вычитания узловых чисел с учётом следующего правила: каждый меньший знак, поставленный справа от большего, прибавляется к его значению, а каждый меньший знак, поставленный слева от большего, вычитается из него.

Система счисления называется позиционной, если количественный эквивалент цифры зависит от её положения (позиции) в записи числа.Основание позиционной системы счисления равно количеству цифр, составляющих её алфавит.

Десятичная система

Десятичная система записи чисел, которой мы привыкли пользоваться в повседневной жизни, с которой мы знакомы с детства, в которой производим все наши вычисления, — пример позиционной системы счисления. Алфавит десятичной системы составляют цифры 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Алгоритмические числа образуются в ней следующим образом: значения цифр умножаются на «веса» соответствующих разрядов, и все полученные значения складываются. Это отчётливо прослеживается в числительных русского языка, например: «три-ста пять-десят семь».

Основанием позиционной системы счисления может служить любое натуральное число q > 1. Алфавитом произвольной позиционной системы счисления с основанием q служат числа 0, 1, …, q—1, каждое из которых может быть записано с помощью одного уникального символа; младшей цифрой всегда является 0.

Основные достоинства любой позиционной системы счисления — простота выполнения арифметических операций и ограниченное количество символов, необходимых для записи любых чисел.

В позиционной системе счисления с основанием q любое число может быть представлено в виде:

• А_q = ± (а_n-1 • q^n-1 + а_n-2 • q^n-2 + … + а₀ • q⁰ + а_-1 • q^-1 + … + а_-m • q^-m).      (1)

Здесь:

• А — число;
• q — основание системы счисления;
• а_i — цифры, принадлежащие алфавиту данной системы счисления;
• n — количество целых разрядов числа;
• m — количество дробных разрядов числа;
• qⁱ — «вес» i-го разряда.

Запись числа по формуле (1) называется развёрнутой формой записиСвёрнутной формой записи числа называется его представление в виде¹ ± a_n-1a_n-2…a₁a₀,a_-1…a_-m.¹ Далее будут рассматриваться только положительные целые числа.

Пример 3. Рассмотрим десятичное число 14351,1. Его свёрнутая форма записи настолько привычна, что мы не замечаем, как в уме переходим к развёрнутой записи, умножая цифры числа на «веса» разрядов и складывая полученные произведения:

• 1 • 10⁴ + 4 • 10³ + 3 • 10² + 5 • 10¹ + 1 • 10⁰ + 1 • 10^-1.

1.1.2. Двоичная система счисления

Двоичной системой счисления называется позиционная система счисления с основанием 2. Для записи чисел в двоичной системе счисления используются только две цифры: 0 и 1.

На основании формулы (1) для целых двоичных чисел можно записать:

• а_n-1а_n-2…а₁а₀ = a_n-1 • 2^n-1 + а_n-2 • 2^n-2 +…+ а₀ • 20. (1′)

Например:

• 10011₂ = 1 • 2⁴ + 0 • 2³ + 0 • 2² + 1 • 2¹ + 1 • 2⁰ = 2⁴ + 2¹ + 2⁰ = 19₁₀.

Такая форма записи «подсказывает» правило перевода натуральных двоичных чисел в десятичную систему счисления: необходимо вычислить сумму степеней двойки, соответствующих единицам в свёрнутой форме записи двоичного числа.

Получим правило перевода целых десятичных чисел в двоичную систему счисления из формулы (1′).

Разделим а_n-1 • 2^n-1 + а_n-2 • 2^n-2 + … + а₀ • 2⁰ на 2. Частное будет равно а_n-1 • 2^n-2 + … + а₁, а остаток будет равен а₀.

Полученное частное опять разделим на 2, остаток от деления будет равен а₁.

Если продолжить этот процесс деления, то на n-м шаге получим набор цифр:

• а₀, а₁, а₂, … а_n-1,.

которые входят в двоичное представление исходного числа и совпадают с остатками при его последовательном делении на 2.

Таким образом, для перевода целого десятичного числа в двоичную систему счисления нужно последовательно выполнять деление данного числа и получаемых целых частных на 2 до тех пор, пока не получим частное, равное нулю. Исходное число в двоичной системе счисления составляется последовательной записью полученных остатков, начиная с последнего.

Пример 4. Переведём десятичное число 11 в двоичную систему счисления. Рассмотренную выше последовательность действий (алгоритм перевода) можно изобразить так:

Выписывая остатки от деления в направлении, указанном стрелкой, получим: 11₁₀ = 1011₂.

Пример 5. Если десятичное число достаточно большое, то более удобен следующий способ записи рассмотренного выше алгоритма:

1.1.3. Восьмеричная система счисления

Восьмеричной системой счисления называется позиционная система счисления с основанием 8. Для записи чисел в восьмеричной системе счисления используются цифры: 0, 1,2, 3, 4, 5, 6, 7.

На основании формулы (1) для целого восьмеричного числа можно записать:

• а_n-1а_n-2…а₁а₀ = а_n-1 • 8^n-1 + а_n-2 • 8^n-2 + … + а₀ • 8⁰.    (1″)

Например: 1063₈ = 1 • 8³ + 0 • 8² + 6 • 8¹ + 3 • 8⁰ = 563₁₀.

Таким образом, для перевода целого восьмеричного числа в десятичную систему счисления следует перейти к его развёрнутой записи и вычислить значение получившегося выражения.

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

Пример 6. Переведём десятичное число 103 в восьмеричную систему счисления.

103₁₀ = 147₈

1.1.4. Шестнадцатеричная система счисления

Основание: q = 16.

Алфавит: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, А, В, С, D, Е, F.

Здесь только десять цифр из шестнадцати имеют общепринятое обозначение 0,…, 9. Для записи цифр с десятичными количественными эквивалентами 10, 11, 12, 13, 14, 15 обычно используются первые пять букв латинского алфавита.

Таким образом, запись 3AF₁₆ означает:

• 3AF₁₆ = 3 • 16² + 10 • 16¹ + 15 • 16⁰ = 768 + 160 + 15 = 943₁₀.

Пример 7. Переведём десятичное число 154 в шестнадцатеричную систему счисления.

154₁₀ = 9А₁₆

1.1.5. Правило перевода целых десятичных чисел в систему счисления с основанием q

Для перевода целого десятичного числа в систему счисления с основанием q следует:

• 1) последовательно выполнять деление данного числа и получаемых целых частных на основание новой системы счисления до тех пор, пока не получим частное, равное нулю;
• 2) полученные остатки, являющиеся цифрами числа в новой системе счисления, привести в соответствие с алфавитом новой системы счисления;
• 3) составить число в новой системе счисления, записывая его, начиная с последнего полученного остатка.

Представим таблицу соответствия десятичных, двоичных, восьмеричных и шестнадцатеричных чисел от 0 до 2010.

В Единой коллекции цифровых образовательных ресурсов (http://sc.edu.ru/) размещена интерактивная анимация «Преобразование десятичного числа в другую систему счисления» (135050). С её помощью можно понаблюдать за переводом произвольного целого числа от 0 до 512 в позиционную систему счисления, ос

Система счисления. Позиционная система счисления.

Задумывались ли вы над тем, почему при сложении тех или иных чисел получается строго определённое число? А почему мы обходимся всего десятью цифрами? Странные вопросы… Дело в том, что мы привыкли проводить вычисления, используя всего одну и ту же систему счисления. Однако это было так не всегда.

Системой счисления принято называть знаковую систему, в которой были приняты определённые правила записи чисел. Знаки, с помощью которых записывают числа, мы называем цифрами, а их совокупность — алфавитом системы счисления.

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

В Древнем Вавилоне узловыми числами выступали 1,10,60;

Системы счисления отличаются друг от друга выбором узловых чисел и способами образования алгоритмических чисел. В информатике выделяют такие виды систем счисления, как:

• унарная система;
• непозиционная система;
• позиционная система.

Унарная система

В самой древней и простой унарной системе счисления, для записи любых чисел использовался всего лишь один символ — в виде зарубки, выемки, узелка или камушка.

Чем больше зарубок — тем больше число. По сути, эта система является основой любого счёта. Унарная система, по-другому, ещё называется системой бирок.

Если вы думаете, что не пользуетесь этой системой счисления, тогда не считайте на пальцах!

Непозиционная система счисления

Для такой системы счисления количественный эквивалент (количественное значение) цифры в числе не зависит от её положения в записи числа.

Примерно в III тысячелетии до н.э. древние египтяне разработали десятичную непозиционную систему счисления, в которой для обозначения узловых чисел 1, 10, 100 использовались символы – иероглифы.

В большинстве непозиционных систем счисления новые числа образуются путём сложения узловых чисел.

Каноническим примером непозиционной системы счисления всегда приводится римская система счисления. В качестве узловых цифр здесь применялись заглавные буквы латинского алфавита:

I = 1,
V = 5,
X = 10,
L = 50,
C = 100,
D = 500,
M = 1000

Например, II = 1 + 1 = 2
здесь символ I обозначает единицу независимо от места в числе.

Однако римская система не может быть полностью непозиционной, так как меньшая цифра, которая стоящая слева перед большей, должна вычитаться из неё:

IV = 4, в то время как:
VI = 6

Непозиционной системой счисления являлась и кириллическая система счисления — система счисления, применяемая на территории Древней Руси до XVIII века, основанная на алфавитной записи чисел с использованием кириллицы.

Позиционная система счисления

В позиционной системе счисления, количественный эквивалент цифры как раз зависит от её положения в записи числа. Основание позиционной системы счисления соответствует количеству цифр, которые составляют её алфавит.

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

Алфавитом десятичной системы являются цифры от 0 до 9. Образование чисел в ней происходит следующим образом: значения цифр умножаются на их «веса» соответствующих разрядов, а затем все полученные значения складываются.

Числительными русского языка, такое значением хорошо отражается, к примеру: «пять-сот семь-десят два».

Основанием позиционной системы счисления является любое натуральное число q>1. Алфавитом произвольной позиционной системы счисления с основанием q служат числа 0,1,…,q−1, каждое из которых записывается при помощи одного уникального символа; младшей цифрой всегда выступает 0.

Основными преимуществами любой позиционной системы счисления являются простота выполнения арифметических операций и небольшое количество символов, используемых в записи чисел.

Представление числа в позиционной системе счисления

В позиционной системе счисления с основанием q всякое число может быть представлено по формуле (развёрнутая форма записи):

A_q=±(a_n−1⋅qⁿ⁻¹+a_n−2⋅qⁿ⁻²+…+a₀⋅q⁰+a₋₁⋅q⁻¹+…+a_−m⋅q^−m).

где:

А — число;

q — основание системы счисления;

a_i — цифры, принадлежащие алфавиту данной системы счисления;

n — количество целых разрядов числа;

m — количество дробных разрядов числа;

q_i — «вес» i-го разряда.

Свёрнутой формой записи числа называется его представление в виде:

±a_n−1a_n−2…a₁a₀…a_−m

в качестве примера, возьмём десятичное число 21466,12. Его свёрнутая форма записи настолько привычна, что мы не замечаем, как в уме мы переходим сразу к развёрнутой записи, умножая цифры числа на «веса» разрядов и суммируя все полученные перемножения:

2⋅10⁴+1⋅10³+4⋅10²+6⋅10¹+6⋅10⁰+1⋅10⁻¹+2⋅10⁻².

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

Кодирование информации Двоичная система счисления

Лекция №8.Алгоритмические системы

Вопросы:

1. Машины Тьюринга.

2. Нормальные алгоритмы Маркова.

3. Операторные системы алгоритмизации.

В
теории алгоритмов большое внимание
уделяется общим способам задания
алгоритмов, характеризующимися свойством
универсальности,
т.е. таким способам, которые позволяют
задать алгоритм, эквивалентный любому
наперед заданному алгоритму.
Общий способ задания алгоритмов
называется алгоритмической системой.
При описании алгоритмических систем
используются специальные формализованные
средства, которые можно разделить на
два типа, условно называемые «алгебраические»
и «геометрические».

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

К
перовому направлению относятся –
рекурсивные функции, машины Тьюринга,
операторные системы Ван-Хао, А.А. Ляпунова,
логические схемы алгоритмов Ю.И. Янова
и др. Ко второму направлению относятся
– представления нормальных алгоритмов
А.А. Маркова в виде граф-схем предложенных
Л.А. Калужниным, блок схемный метод
алгоритмизации и др.
В
1936—-1937 гг.
независимо друг от друга и почти
одновременно с работами А.Черча и С.
Клини было дано
определение понятия алгоритма американским
и английским математиками Э. Постом и
А.Тьюрингом. Их подход базируется на
определении специальных абстрактных
(т. е. существующих не реально, а лишь в
воображении) автоматов
(машин). Основная
мысль при этом заключалась в том, что
алгоритмические процессы — это процессы,
которые может совершать подходяще
устроенная «машина». В соответствии с
этим ими с помощью точных математических
терминов были описаны классы машин,
способные осуществить или имитировать
все алгоритмические процессы, когда-либо
описываемые математиками.

Машины
Тьюринга
Машины,
введенные Постом и Тьюрингом, отличались
не очень существенно и в дальнейшем
стали называться машинами Тьюринга.
В
общем случае такая машина состоит из
следующих частей (рис. 8.1)

Состав машины
Тьюринга:

1. информационной
   ленты, представляющей собой бесконечную
   (неограниченную) память машины. В
   качестве информационной ленты может
   служить магнитная или бумажная
   бесконечная лента, разделенная на
   отдельные ячейки. В каждой ячейке можно
   поместить лишь один символ, в том числе
   и ноль;

2. “считывающей
   головки” — специального чувствительного

   элемента, способного обозревать
   содержимое ячеек. Вдоль головки

   информационная лента перемещается
   в обе стороны так, что
   бы в каждый
   рассматриваемый момент времени головка
   находилась
   в одной определенной
   ячейке ленты;

3. управляющего
   устройства, которое в каждый рассматриваемый
   момент находится в некотором «состоянии».
   Предполагается, что устройство управления
   машины может находиться в некотором
   конечном числе состояний. Состояние
   устройства управления часто называют
   внутренним состоянием машины. Одно из
   этих
   состояний называется заключительным
   и управляет окончанием
   работы машины.

Рис.
8.1.
Состав машины Тьюринга.

М

Внутренний
алфавит

ашина Тьюринга называется стандартной,
если она при сдвиге ленты может
предварительно изменять состояние
воспринимаемой ячейки.
Пусть алфавит
машины Тьюринга задан в виде множества
А =
{S,
S…,S}
где S
соответствует пустой ячейке, а число
состояний устройства управления задано
в виде множества Q={q,q..,q}
где qо
соответствует заключительному состоянию.

Конечную
совокупность символов алфавита, с
которой работает машина, называют
внешним
алфавитом, конечную
совокупность состояний устройства
управления —внутренним
алфавитом

Совокупность, образованную
последовательностью состояний всех
ячеек ленты и состоянием устройства
управления, называют конфигурацией
машины.
Конфигурация задается в виде слова,
описывающего конкретное состояние
машины.
Пусть в некоторый момент
времени машина Тьюринга находится в
состоянии, представленном на рис. (8.2)

q

Внешний
алфавит

S S S S S S S

Рис.8.2.Создание
машины Тьюринга

Конфигурация
машины для данного случая будет
представлена в виде слова:

…SS…qS…SS…

Где Sо
— символ,
обозначающий
пустую ячейку; r—
число
заполненных ячеек на ленте; S-состояние
первой слева непустой ячейки;
S_jk-состояние
ячейки, просматриваемой в данный момент
времени;
q—
состояние устройства управления.
Каждая
конфигурация содержит лишь одно вхождение
символа q
из внутреннего алфавита. Этот символ
может быть в слове самым левым, но не
может быть самым правым, так как справа
от него должен помещаться символ
состояния обозреваемой ячейки. Если
стандартная машина Тьюринга, находясь
в состоянии q
и воспринимая записанный на ленте символ
S_k
переходит в новое состояние q
осуществляя при этом замену символа в
рассматриваемой ячейке на символ S_m
и сдвиг ленты влево на одну ячейку, то
говорят, что машина выполняет команду
qS_kqS_m

При
манипуляциях с лентами используют
следующие обозначения:
—
движение
ленты влево;
П—
движение
ленты вправо; С—
нет
движения ленты.

Команды
стандартной машины Тьюринга могут
задаваться набором пятерок символов
вида qSkqSmт.е.
стрелка опускается.
Рассмотрим
пример
машины Тьюринга с алфавитами А—
{О,
1}, Q={qq}
и командами q1q1,q0q1C.

Совокупность
всех команд, которые может выполнять
машина, называется ее программой.

Машина
Тьюринга считается заданной, если
заданы:
1)
ее внешний и внутренний алфавиты;
2)
программа;
3) начальная конфигурация;

4) символы обозначающие пустую ячейку
и заключительное
состояние.

При
изучении моделей вычислений обычно
проводят различие между детерминированными
и недетерминированными машинами
Тьюринга. В детерминированной машине
Тьюринга общий ход вычислений полностью
определяется машиной Тьюринга
(программой), начальным символом и
начальными вводами с ленты. В
недетерминированной машине Тьюринга
на каждой стадии вычислений существуют
альтернативы, т. е. она может работать
в одном из нескольких основных режимов.
Современные
электронные вычислительные машины
строятся как универсальные: в запоминающее
устройство наряду с исходными данными
поставленной задачи вводится также и
программа ее решения.
Однако в отличие от машины Тьюринга, в
которой внешняя память (лента) бесконечна,
в любой реальной вычислительной машине
она конечна.

Нормальные
алгоритмы Маркова

Алгоритмическая
система, основанная на соответствии
между словами в абстрактном алфавите,
включает в себя объекты двух типов:
элементарные операторы и элементарные
распознаватели.

Элементарные
операторы
представляют
собой алфавитные операторы, предназначенные
для реализации алгоритмов в рассматриваемой
алгоритмической системе.

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

Граф-схема
алгоритма представляет собой конечное
множество соединенных между собой
вершин (или геометрических фигур),
называемых узлами граф-схемы. Каждому
узлу, кроме особых узлов, называемых
входом и выходом, сопоставляется
какой-либо элементарный оператор (ЭО)
или элементарный распознаватель (ЭР).
При этом из каждого узла, которому
сопоставлен оператор, а также из входного
узла исходит по одной дуге, а из каждого
узла, которому сопоставлен распознаватель,
исходит по две дуги. Из выходного узла
не исходит ни одной дуги. Число дуг,
входящих в узел граф-схемы, может быть
любым.

Общий
вид такой граф-схемы представлен на
рис. 8.4.
Алгоритм,
определенный граф-схемой, работает
следующим образом. Входное
слово поступает на вход и двигается по
направлениям, указанным стрелками. При
попадании слова в распознавательный
узел осуществляется проверка условия,
сопоставленного этому узлу. При выполнении
условия слово направляется в операторный
узел, при невыполнении — к следующему
распознавателю.
Если
входное слово
q,
поданное на вход граф-схемы, проходя
через узлы схемы и преобразуясь, попадает
через конечное число шагов на выход, то
считается, что алгоритм применим к слову
q
(слово
q
входит в область определения этого
алгоритма). Результатом воздействия на
слово q
будет то слово, которое оказывается на
выходе схемы. Если после подачи слова
q
на вход графа его преобразование и
движение по граф-схеме продолжается
бесконечно долго, не приводя на выход,
считается, что алгоритм неприменим к
слову q,
т.е. слово q
не входит в область определения алгоритма.

ЭО

ЭР

ЭО

ЭР

ЭО

ЭР

Рис.8.4.
Общий
вид граф-схемы алгоритма.

В
нормальных алгоритмах в качестве
элементарного оператора используют
оператор подстановки, а в качестве
элементарного распознавателя
распознаватель вхождения.
Распознаватель
вхождения проверяет условие — имеет
ли место вхождение, рассматриваемого
слова Р_i
в качестве подслова некоторого
заданного слова q.

Оператор
подстановки заменяет первое слева
вхождение слова p
в слово q
на некоторое заданное слово р.
Оператор подстановки задается обычно
в виде двух
слов, соединенных стрелкой
р—>p

Например,
для слова 01230123
применение
подстановок 01 —>З2 и 23—>10 через четыре
шага приводит к слову 32103210
(рис.9.5):

0]230123—>32230123—->32233223->321
03223—>321 03210.

Последовательность
слов p,p,….,p
получаемых в процессе реализации
алгоритма, называется дедуктивной
цепочкой, ведущей от слова р
к слову p
Алгоритмы,
которые задаются графами, составленными
только из распознавателей вхождения
слов и операторов подстановки, называют
обобщенными
нормальными алгоритмами.

При
этом предполагается, что к каждому
оператору подстановки ведет только
одна дуга, исходящая из соответствующего
распознавателя.

Рис.8.5.
Граф-схема
алгоритма преобразования входного
слова «01230123» в слово «32103210»

Нормальными
алгоритмами называют обобщенные
нормальные алгоритмы, граф-схемы которых
удовлетворяют следующим условиям:
1.
Все узлы, соответствующие распознавателям,
упорядочиваются путем их нумерации от
1 до n
2.
Дуги,
исходящие из узлов, соответствующих
операторам подстановки, подсоединяются
либо к узлу, соответствующему первому
распознавателю, либо к выходному узлу.
В первом случае подстановка называется
обычной, во втором — заключительной.

З. Входной узел подсоединяется дугой
к первому распознавателю.

ЭР1

ЭO1

ЭО

ЭР2

ЭO2

ЭР3

ЭO3

ЭР4

ЭO4

Выход

Рис.8.6.
Общий вид граф-схемы нормалного алгоритма.

Нормальные
алгоритмы принято задавать упорядоченным
множеством подстановок всех операторов
данного алгоритма, называемым схемой
алгоритма. При этом обычные
подстановки записываются, как и в
обобщенных алгоритмах, в виде двух слов,
соединенных стрелкой (p—>p2),
а
заключительные подстановки обозначаются
стрелкой с точкой (р—>
• р).
Процесс
выполнения подстановок заканчивается
лишь тогда, когда ни одна из подстановок
схемы не применима к полученному слову
или когда выполнена (первый раз) какая-либо
заключительная подстановка. В качестве
примера рассмотрим работу нормального
алгоритма А.А.
Маркова,
алфавит которого представлен алфавитом
русского языка и задано множество
подстановок:

1. БВ
4. ОХ

2. ЛУ
5. ВЯ

3. СМ
6. НА

Тогда,
если на вход подать слово «СЛОН», то оно
переработается алгоритмом в выходное
слово «МУХА» (рис. 9.6):
«СЛОН»

СУОН

МУОН

МУХН«МУХА».

Рис.8.7.
Граф-схема
алгоритма преобразования входного
слова «СЛОН» в слово «МУХА».

Операторные
системы алгоритмизации.

Одной из особенностей
рассмотренных выше алгоритмических
систем является неизменность набора
допустимых средств, используемых для
построения записи алгоритма. Например,
все частично рекурсивные функции
получаются из некоторого фиксированного
набора базисных функций с помощью трех
операторов — подстановки, примитивной
рекурсии, минимизации. Элементарные
акты при вычислениях на машине Тьюринга
ограничиваются фиксированным набором
операций, которые выполняет описываемый
класс машин и т. п.

В то же
время при изучении конкретных алгоритмов
желательно, чтобы каждый алгоритм мог
изучаться в терминах тех элементарных
средств, которые наиболее удобны для
его описания. Например, алгоритмы
линейной алгебры удобнее всего описывать
с помощью четырех арифметических
действий, а алгоритмы вычисления функций
алгебры логики — с помощью тех базисных
логических операций, в терминах которых
функции и

записаны.
Поэтому
одним из требований, которое предъявляется
к определению алгоритма при его
практическом использовании, является
то, чтобы форма
представления перерабатываемой
информации и средства ее переработки
выбирались в зависимости от класса
рассматриваемых алгоритмов. Кроме
того, для классических алгоритмических
систем характерно, что в каждом алгоритме
список предписаний о выполнении
элементарных актов «команд» алгоритма
фиксируется заранее и явно указывается
в записи алгоритма. Например, в нормальных
алгоритмах все применяемые формулы
подстановки заранее указаны в записи
алгоритма. Список допустимых действий
машины Тьюринга при ее работе остается
неизменным. Частично рекурсивная функция
задается фиксированной последовательностью
уравнений. В то же время допущение
формирования команд алгоритма в процессе
его реализации приводит к существенному
сокращению и упрощению записи алгоритма.
В связи с этим следующим требованием,
предъявляемым к понятию алгоритма, при
его практическом использовании является
возможность
формирования команд алгоритма в процессе
его выполнения.
В
общем случае все элементарные операции,
производимые в процессе выполнения
алгоритмов, распадаются на две группы
операций, которые обычно называют
арифметическими и логическими.
Арифметические операции осуществляют
непосредственное преобразование
информации. Логические операции
определяют дальнейшее направление
счета, т. е. последовательность выполнения
арифметических операций. При этом во
многих сложных алгоритмах преобладают
логические операции, в то время как
преобразование информации носит иногда
очень простой характер Элементарные
акты, аналогичные логическим операциям,
в явном или неявном виде вводятся и при
определении понятия выполнения алгоритма
в абстрактной теории алгоритмов.
Например, при выполнении нормального
алгоритма после рассмотрения очередной
формулы подстановки осуществляется
либо переход к следующей формуле
подстановки, либо остановка, либо переход
к первой формуле подстановки схемы
алгоритма. В машине Тьюринга логической
операцией можно считать движение ленты
вправо или влево в зависимости от
состояния машины и прочитанного символа.
Однако, как правило, логические операции
в классических алгоритмических системах
носят тривиальный характер. Во многих
случаях такая тривиальность логических
операций сильно усложняет построение
конкретных алгоритмов.

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

Операторные
алгоритмы Ван Хао

Операторный
алгоритм Ван Хао задается последовательностью
приказов специального вида. Каждый
приказ имеет определенный номер и
содержит указания: какую операцию
следует выполнить над заданным объектом
и, приказ с каким номером следует далее
выполнить над результатом данной
операции. Общий вид такого приказа:

(1)

Где:
i
— номер приказа;
—элементарная
операция над объектом;

—
номера
некоторых приказов.
В терминах машин
Тьюринга номера приказов соответствуют
номерам конфигураций машины, а элементарная
операция над объектом — элементарному
действию над конфигурацией при некотором
состоянии.
Выполнить приказ (1) над
числом х
в операторном алгоритме — значит найти
число

и далее перейти к выполнению над

приказа с номером.
Если же

не определено, то перейти к выполнению
над числом х
приказа
с номером
.

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

который означает,
что вычисления следует остановить.
Число, над которым следует выполнить
этот приказ, есть результат вычислений.

Программой
операторного алгоритма называется
последовательность приказов вида:

где

— заданные функции, определяющие
элементарные операции над объектом x.

-натуральные
числа из последовательности
.

Переработать
х
согласно
данному операторному алгоритму — значит
выполнить над
х
последовательность
следующих действий:

1) i—шаг.
Находим
.
Если

определено, то результатом будет пара
чисел
.
Если

не определено, то результатом i-го
шага будет пара
.

2) i+1-шаг,
если результат предыдущего шага
,
где
.
Находим
.
Если она определена, то результатом
будет пара
,
если не определена, то результатом будет
пара
,
и.т.д.

3)
i+n-1-шаг.
Если в качестве результата на данном
шаге получится пара, указывающая
на
заключительный оператор (z,i+
п),то
процесс завершается и число z
является результатом переработки числа
х
согласно заданному алгоритму

Тип
функции, вычисляемых посредством
операторных алгоритмов Ван Хао, зависит
от того, какие функции входят в записи
приказов.

Операторные
алгоритмы Ляпунова

Алгоритмическая
система отечественного ученого А.А.
Ляпунова, предложенная им в 1953
г.,
является одной из первых, учитывающих
все требования, предъявляемые к конкретным
алгоритмам. Она возникла в связи с
реализацией алгоритмов различных задач
на ЭВМ.

Важнейшим понятием,
введенным А.А. Ляпуновым, было понятие
оператора, являющегося одновременно и
единицей действия, и единицей
конструирования программы. Как единица
действия оператор выполняет некоторое
преобразование над информацией, а как
единица конструирования программы —
имеет некоторое обозначение, показывающее
тип оператора, его место в программе и
конкретное содержание оператора
(спецификацию).

Важным
свойством оператора было то, что трактовка
оператора как единицы действия носит
относительный характер. Два оператора
А
и
В,
выполненные
друг за другом, осуществляют какое-то
совокупное преобразование информации,
т.е. также образуют некоторый оператор
С.
Для
того чтобы операторы А и В выполнялись
подряд, их записывают один за другим:
АВ,
а
связь с оператором С
выглядит
как:
С
—
АВ.
Информация,
например, о том, что А
и В можно
выполнять в любом порядке, получая один
и тот же результат, может быть выражена
равенством А
В =
В
А.

Выражаясь языком
алгебры, можно сказать, что операторы
программ образуют полугруппу, в которой
могут существовать определяющие
отношения. Изучение полугруппы операторов
приобрело фундаментальную роль в
теоретическом программировании.

Аналогия двух
рядом стоящих операторов АВ с произведением
двух чисел делала понятными такие
обозначения, введенные А.А. Ляпуновым,
как:

Эта
запись обозначает кратное повторение
операторов АВС,
причем
символы А(i),и
С(i)
показывают,
что спецификация этих операторов зависит
от значения индекса повторения
Для
записи передач управления зависимости
от условий А.А. Ляпунов ввел
понятие
логических операторов:

Где
P-символ
логического оператора;

передающая
и приемная стрелки соответственно.

Обозначение i
используется, чтобы выделять пары
соответствующих друг другу приемных и
передающих стрелок. При одном значении
Р
управление
передается на оператор, стоящий вслед
за передающей стрелкой i,
а при другом — на оператор, стоящий
вслед за принимающей стрелкой i.

Запись
алгоритма по А.А. Ляпунову состоит из
двух частей. Первая часть — схема алгоритма
— образована символами операторов и
показывает порядок расположения
операторов в программе, а также направления
передач управления. Вторая часть — это
спецификация всех операторов, образующих
программу.

Рассмотрим
пример записи операторного алгоритма
Ляпунова для
решения 10 квадратных
уравнений вида
.
Для каждого уравнения представив общую
формулу решения:

в виде

,

и

в
зависимости от знака дискриминанта
—
4ас
найдем
для действительного случая (призн
=
1). хор
=р +q
и кор2
=р-q,
для комплексного (призн
=
-1), кор1=
и
кор2=

Схема
алгоритма:
СТОП.

Спецификация:

A—
ввод
всех коэффициентов
;

А—
присвоение
переменным

и с
значений коэффициентов
;
А-
вычисление дискриминанта:
;
А-
вычисление вспомогательных значений:

;
А—
проверка
условия: дискр
<
О?;

А-
вычисление модуля и аргумента комплексной
пары корней:
;

A-вычисление
пары действительных корней
;

A-
сохранение знака дискриминанта;

A-
запоминание в массиве решений пары
корней i-ого
уравнения;

А-
печать всех решений.

На основе данного
операторного метода в период 1955- 1960 гг.
были созданы первые алгоритмические
языки и трансляторы, а так же разработаны
первые формализмы теоретического
программирования.

Алгоритмы в математике

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

Исследования психологов и педагогов, опыт коллег показывают: чтобы научить
детей самостоятельно учиться и проявлять творчество необходимо применение
деятельностного подхода в обучении. Для этого учащихся нужно замотивировать и
обучить их приемам и способам учебной деятельности, которые помогут сформировать
необходимые знания, умения и навыки.

Курс школьной математики имеет достаточно широкие возможности для применения
различных приемов, методов и технологий. В последние годы в содержание школьного
курса естественным образом закладывается алгоритмическая линия. Так как
применение алгоритмов является приоритетным в моей работе, то нужно отметить
что, между понятиями “прием” и “алгоритм” существует много общего, ни и есть
принципиальные отличия, а именно:

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

– алгоритм – это общепонятное и однозначное предписание, которое определяет
последовательность действий, позволяющее достичь искомый результат. Алгоритм
предполагает жесткое выполнение шагов, а прием дает общее направление
деятельности по решению учебных задач, не регламентируя каждый шаг. Поэтому я в
своей работе выделяю два подхода: 1) обучение алгоритмам; 2) формирование
приемов решения задач. Школьные задачи делятся на: алгоритмические,
полуалгоритмические, полуэвристические и эвристические. Каждый тип задачи
предполагает свои схемы решения, подходы, применение логики и изобретательности.

На начальном этапе обучения математике применение алгоритмов способствует
формированию и прочному усвоению навыков владения математическими методами.
Также осуществляется подготовка к формированию первоначальных представлений о
математическом моделировании. Уже в начальных классах прослеживается применение
простейших алгоритмов выполнения арифметических операций, дети овладевают
навыками выполнения последовательных действий. Решают задачи с составлением схем
и кратких записей. Это можно рассматривать как пропедевтику операционного стиля
мышления.

Следующий уровень алгоритмической культуры учащихся – введение понятия
алгоритма и формирование его основных свойств. Это происходит в среднем звене
школы. Именно в этот период необходимо сочетания алгоритма и образца ответа, что
дает возможность ученику, верно, ответить на поставленный вопрос, сопроводив его
правильной речью. У учителя появляется возможность предлагать задачи с
элементами творчества. А материал, предлагаемый в наших школьных учебниках,
является хорошей базой для обучения составлению простейших алгоритмов и
дальнейшей их записи в разных формах. Мы применяем табличную, графическую
(блок-схема), словесную и формульную форму записи алгоритмов.

В качестве примера, иллюстрирующего процесс алгоритмизации как средство
обучения, можно указать на решение задач методом уравнений. Примером
графического алгоритма является блок-схема для отыскания количества решений
системы двух линейных уравнений с двумя неизвестными (см. Рисунок 1).

Отыскания числа решений системы двух линейных уравнений (блок-схема)

Рис. 1

Графические алгоритмы

Табличную форму алгоритма можно продемонстрировать на примере таблицы,
составляемой для исследования функций и дальнейшего построения графиков (см.
рис. 2).

Исследование функции и построение графика

Функция задана уравнением у = f(x). Исследовать
функцию и построить ее график.

1. Таблица исследования функции

2. Построение графика

Рис. 2

Табличный алгоритм

Пример формульного способа – последовательность нахождения компонентов при
составлении уравнения касательной к графику той или иной функции (см. рис. 3).

Уравнение касательной к графику функции

Рис. 3

Формульный способ

Словесный алгоритм используется практически во всех правилах выполнения
действий, например, правило сложения чисел с разными знаками (см. рис. 4).

Алгоритм сложения чисел с разными знаками

Рис. 4

Словесный алгоритм

В старших классах работа становится разнообразней и содержательней,
появляется возможность включать упражнения разного типа и уровня сложности,
предполагающее, что приемы деятельности могут быть разной степени сложности и
обобщенности. Они состоят из большого числа действий, выполнение которых
приводит к применению алгоритмов на отдельных этапах работы.

Такой подход к преподаванию математики в основной школе определяет условия
для формирования у учащихся навыков, позволяющих в старших классах успешно
изучать базовый курс “Информатики и ИКТ”. Применение алгоритмов в старших
классах, по мнению некоторых учителей, отбивает творческий подход к решению
задач, но с другой стороны, твердое знание основных задач курса и умение их
решать, является твердым фундаментом для активизации самостоятельной и
творческой работы учащихся.

Список литературы

1. Кухарев Н.В. На пути к профессиональному совершенству. – М.:
   Просвещение, 1990.
2. Епишева О.Б. Крутич В.И. Учить школьников учиться математике. –
   М.: Просвещение, 1990.
3. Сост. Глейзер Г.Д. Повышение эффективности обучения математике в
   школе. – М.: Просвещение, 1991.
4. Груденов Я.И. Совершенствование методики работы учителя
   математики. – М.: Просвещение, 1990.
5. Байдак В.А. и др. Формирование алгоритмической культуры у
   учащихся. – М.: Просвещение, 1989.

Алгоритмическая разрешимость — Карта знаний

• Алгоритмическая разрешимость — свойство формальной теории обладать алгоритмом, определяющим по данной формуле, выводима она из множества аксиом данной теории или нет. Теория называется разрешимой, если такой алгоритм существует, и неразрешимой, в противном случае. Вопрос о выводимости в формальной теории является частным, но вместе с тем важнейшим случаем более общей проблемы разрешимости.

Источник: Википедия

Связанные понятия

Форма́льная систе́ма (форма́льная тео́рия, аксиоматическая теория, аксиоматика, дедуктивная система) — результат строгой формализации теории, предполагающей полную абстракцию от смысла слов используемого языка, причем все условия, регулирующие употребление этих слов в теории, явно высказаны посредством аксиом и правил, позволяющих вывести одну фразу из других.

Те́зис Чёрча — Тью́ринга — это гипотеза, постулирующая эквивалентность между интуитивным понятием алгоритмической вычислимости и строго формализованными понятиями частично рекурсивной функции и функции, вычислимой на машине Тьюринга. В связи с интуитивностью исходного понятия алгоритмической вычислимости, данный тезис носит характер суждения об этом понятии и его невозможно строго доказать или опровергнуть. Перед точным определением вычислимой функции математики часто использовали неофициальный термин…

Аксио́ма (др.-греч. ἀξίωμα «утверждение, положение») или постула́т — исходное положение какой-либо теории, принимаемое в рамках данной теории истинным без требования доказательства и используемое при доказательстве других её положений, которые, в свою очередь, называются теоремами.

Математическое доказательство — рассуждение с целью обоснования истинности какого-либо утверждения (теоремы), цепочка логических умозаключений, показывающая, что при условии истинности некоторого набора аксиом и правил вывода утверждение верно. В зависимости от контекста, может иметься в виду доказательство в рамках некоторой формальной системы (построенная по специальным правилам последовательность утверждений, записанная на формальном языке) или текст на естественном языке, по которому при необходимости…

Теория доказательств — это раздел математической логики, представляющий доказательства в виде формальных математических объектов, осуществляя их анализ с помощью математических методов. Доказательства обычно представляются в виде индуктивно определённых структур данных, таких как списки и деревья, созданных в соответствии с аксиомами и правилами вывода формальных систем. Таким образом, теория доказательств является синтаксической, в отличие от семантической теории моделей. Вместе с теорией моделей…

Аксиома́тика Колмого́рова — общепринятая аксиоматика для математического описания теории вероятностей. Первоначальный вариант предложен Андреем Николаевичем Колмогоровым в 1929 году, окончательная версия — в 1933 году. Аксиоматика Колмогорова позволила придать теории вероятностей стиль, принятый в современной математике.

Логика первого порядка, называемая иногда логикой или исчислением предикатов — формальное исчисление, допускающее высказывания относительно переменных, фиксированных функций и предикатов. Расширяет логику высказываний. В свою очередь является частным случаем логики высших порядков.

Парадокс Скулема — противоречивое рассуждение, описанное впервые норвежским математиком Туральфом Скулемом, связанное с использованием теоремы Лёвенгейма — Скулема для аксиоматической теории множеств.

Аксио́мы Пеа́но — одна из систем аксиом для натуральных чисел, введённая в XIX веке итальянским математиком Джузеппе Пеано.

Тео́рия алгори́тмов — наука, находящаяся на стыке математики и информатики, изучающая общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления. К задачам теории алгоритмов относятся формальное доказательство алгоритмической неразрешимости задач, асимптотический анализ сложности алгоритмов, классификация алгоритмов в соответствии с классами сложности, разработка критериев сравнительной оценки качества алгоритмов и т. п. Вместе с математической логикой теория алгоритмов…

Основания математики — математическая система, разработанная с целью обеспечить вывод математического знания из небольшого числа чётко сформулированных аксиом с помощью логических правил вывода, тем самым гарантируя надёжность математических истин. Основания математики включают в себя три компонента.

Аксиома детерминированности — аксиома теории множеств, обычно обозначаемая AD. Эту аксиому предложили в 1962 году польские математики Ян Мычельский и Гуго Штейнгауз в качестве замены для аксиомы выбора (введённой в 1904 году, обозначается AC). Причиной поиска альтернативы аксиоме выбора стали необычные следствия из этой аксиомы, которые вызывали и продолжают вызывать критику со стороны части математиков. Например, в случае применения аксиомы выбора возникают парадоксальные конструкции вроде «парадокса…

Программа Гильберта в математике была сформулирована немецким математиком Давидом Гильбертом в начале 20-го века. Гильберт предположил, что согласованность более сложных систем, таких как реальный анализ, может быть доказана в терминах более простых систем. В конечном счете, непротиворечивость всей математики может быть сведена к простой арифметике.

Алгоритм Тарского — универсальный алгоритм, позволяющий установить истинность или ложность любой замкнутой арифметической формулы первого порядка с переменными для вещественных чисел.

Теория моделей — раздел математической логики, который занимается изучением связи между формальными языками и их интерпретациями, или моделями. Название теория моделей было впервые предложено Тарским в 1954 году. Основное развитие теория моделей получила в работах Тарского, Мальцева и Робинсона.

Метаматематика — раздел математической логики, изучающий основания математики, структуру математических доказательств и математических теорий с помощью формальных методов. Термин «метаматематика» буквально означает «за пределами математики».

Незави́симость систе́мы аксио́м ― свойство системы аксиом данной аксиоматической теории, состоящее в том, что каждая аксиома является независимой, то есть не является логическим следствием из множества остальных аксиом этой теории. Система аксиом, обладающая этим свойством, называется независимой.

Неконструктивное доказательство (неэффективное доказательство) — класс математических доказательств, доказывающих лишь существование в заданном (как правило, бесконечном) множестве элемента, удовлетворяющего заданным свойствам, но не дающее никакой информации о других свойствах элемента, то есть не позволяющие ни предъявить его, ни приблизительно описать. Доказательства, которые доказывают существование элемента, предъявляя способ получения этого элемента, называются конструктивными.

Оккамово обучение в теории вычислительного обучения является моделью алгоритмического обучения, где целью обучения является получение сжатого представления имеющихся тренировочных данных. Метод тесно связан с почти корректным обучением (ПК обучение, англ. Probably Approximately Correct learning, PAC learning), где учитель оценивает прогнозирующую способность тестового набора.

Теория вычислимости, также известная как теория рекурсивных функций, — это раздел современной математики, лежащий на стыке математической логики, теории алгоритмов и информатики, возникшей в результате изучения понятий вычислимости и невычислимости. Изначально теория была посвящена вычислимым и невычислимым функциям и сравнению различных моделей вычислений. Сейчас поле исследования теории вычислимости расширилось — появляются новые определения понятия вычислимости и идёт слияние с математической…

Задача выполнимости формул в теориях (англ. satisfiability modulo theories, SMT) — это задача разрешимости для логических формул с учётом лежащих в их основе теорий. Примерами таких теорий для SMT-формул являются: теории целых и вещественных чисел, теории списков, массивов, битовых векторов и т. п.

Вероя́тностное простра́нство — понятие, введённое А. Н. Колмогоровым в 30-х годах XX века для формализации понятия вероятности, которое дало начало бурному развитию теории вероятностей как строгой математической дисциплины.

Гипотеза об экспоненциальном времени — это недоказанное допущение о вычислительной сложности, которое сформулировали Импальяццо и Патури. Гипотеза утверждает, что 3-SAT (или любая из связанных NP-полных задач) не может быть решена за субэкспоненциальное время в худшем случае. Из верности гипотезы об экспоненциальном времени, если она верна, следовало бы, что P ≠ NP, но гипотеза является более сильным утверждением. Из утверждения гипотезы можно показать, что многие вычислительные задачи эквиваленты…

Тео́рия мно́жеств — раздел математики, в котором изучаются общие свойства множеств — совокупностей элементов произвольной природы, обладающих каким-либо общим свойством. Создана во второй половине XIX века Георгом Кантором при значительном участии Рихарда Дедекинда, привнесла в математику новое понимание природы бесконечности, была обнаружена глубокая связь теории с формальной логикой, однако уже в конце XIX — начале XX века теория столкнулась со значительными сложностями в виде возникающих парадоксов…

Измери́мые функции представляют естественный класс функций, связывающих пространства с выделенными алгебрами множеств, в частности измеримыми пространствами.

Подробнее: Измеримая функция

Теорема Цермело — теорема теории множеств, утверждающая, что на всяком множестве можно ввести такое отношение порядка, что множество будет вполне упорядоченным.

Интуициони́зм — совокупность философских и математических взглядов, рассматривающих математические суждения с позиций «интуитивной убедительности». Различаются две трактовки интуиционизма: интуитивная убедительность, которая не связана с вопросом существования объектов, и наглядная умственная убедительность.

Индуктивное логическое программирование (Inductive Logic Programming, ILP) — раздел машинного обучения, который использует логическое программирование как форму представления примеров, фоновых знаний и гипотез. Получив описания уже известных фоновых знаний и набор примеров, представленных как логическая база фактов, система ILP может породить логическую программу в форме гипотез, объясняющую все положительные примеры и ни одного отрицательного.

В математической логике, Эрбранова интерпретация — это интерпретация, в которой константам и функциональным символам присвоен очень простой смысл. Конкретнее, каждая константа интерпретируется как она сама, функциональный символ же интерпретируется как функция, которая применяется. Интерпретация также определяет предикатные символы как задающие подмножество соответствующей Эрбрановой базы, фактически задавая, каким образом вычисляется значение замкнутых формул. Это позволяет интерпретировать символы…

Конти́нуум-гипо́теза (проблема континуума, первая проблема Гильберта) — выдвинутое в 1877 году Георгом Кантором предположение о том, что любое бесконечное подмножество континуума является либо счётным, либо континуальным. Другими словами, гипотеза предполагает, что мощность континуума — наименьшая, превосходящая мощность счётного множества, и «промежуточных» мощностей между счетным множеством и континуумом нет, в частности, это предположение означает, что для любого бесконечного множества действительных…

Теоре́ма (др.-греч. θεώρημα «доказательство, вид; взгляд; представление, положение») — утверждение, выводимое в рамках рассматриваемой теории из множества аксиом посредством использования конечного множества правил вывода.

Логика Хоара (англ. Hoare logic, также Floyd—Hoare logic, или Hoare rules) — формальная система с набором логических правил, предназначенных для доказательства корректности компьютерных программ. Была предложена в 1969 году английским учёным в области информатики и математической логики Хоаром, позже развита самим Хоаром и другими исследователями. Первоначальная идея была предложена в работе Флойда, который опубликовал похожую систему в применении к блок-схемам (англ. flowchart).

Гипотеза в математике — утверждение, которое на основе доступной информации представляется с высокой вероятностью верным, но для которого не удаётся получить математическое доказательство. Математическая гипотеза является открытой математической проблемой, и каждую нерешённую математическую проблему, которая является проблемой разрешимости, можно сформулировать в форме гипотезы. Однако в виде гипотезы может быть сформулирована не всякая математическая проблема. Например, конкретное решение некоторой…

Ра́венство (отношение равенства) в математике — бинарное отношение, наиболее логически сильная разновидность отношений эквивалентности.

Теория чисел, или высшая арифметика, — раздел математики, первоначально изучавший свойства целых чисел. В современной теории чисел рассматриваются и другие типы чисел — например, алгебраические и трансцендентные, а также функции различного происхождения, которые связаны с арифметикой целых чисел и их обобщений.

Метод Ньютона, алгоритм Ньютона (также известный как метод касательных) — это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727). Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Модификацией метода является метод хорд и касательных. Также метод Ньютона может быть использован…

Теорема существования — утверждение, которое устанавливает, при каких условиях существует решение математической задачи или математический объект, например производная, неопределенный интеграл, определенный интеграл, решение уравнения и т. д. При доказательстве теорем существования используются сведения из теории множеств. Теоремы существования играют очень важную роль в различных приложениях математики, например при математическом моделировании различных явлений и процессов. Математическая модель…

Комбина́торная ло́гика — направление математической логики, занимающееся фундаментальными (то есть не нуждающимися в объяснении и не анализируемыми) понятиями и методами формальных логических систем или исчислений. В дискретной математике комбинаторная логика тесно связана с лямбда-исчислением, так как описывает вычислительные процессы.

Комбинато́рика (комбинаторный анализ) — раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка). Комбинаторика связана с другими областями математики — алгеброй, геометрией, теорией вероятностей и применяется в различных областях знаний (например, в генетике, информатике, статистической физике).

Четырнадцатая проблема Гильберта — четырнадцатая из проблем, поставленных Давидом Гильбертом в его знаменитом докладе на II Международном Конгрессе математиков в Париже в 1900 году. Она посвящена вопросу конечной порождённости возникающих при определённых конструкциях колец. Исходная постановка Гильберта была мотивирована работой Маурера, в которой утверждалась конечная порождённость алгебры инвариантов линейного действия алгебраической группы на векторном пространстве; собственно же вопрос Гильберта…

Ля́мбда-исчисле́ние (λ-исчисление) — формальная система, разработанная американским математиком Алонзо Чёрчем, для формализации и анализа понятия вычислимости.

Математическая индукция — метод математического доказательства, который используется, чтобы доказать истинность некоторого утверждения для всех натуральных чисел. Для этого сначала проверяется истинность утверждения с номером 1 — база (базис) индукции, а затем доказывается, что если верно утверждение с номером n, то верно и следующее утверждение с номером n + 1 — шаг индукции, или индукционный переход.

Логическая вероятность — логическое отношение между двумя предложениями, степень подтверждения гипотезы H свидетельством E.

Анзац-подход является важным методом при решении дифференциальных уравнений, где мы можем подставить пробные функции в систему уравнений и проверить наше решение.

Задачи тысячелетия — семь открытых математических проблем, определённых Математическим институтом Клэя в 2000 году как «важные классические задачи, решение которых не найдено вот уже в течение многих лет», за решение каждой из которых обещано вознаграждение в 1 млн долларов США. Существует историческая параллель между задачами тысячелетия и списком проблем Гильберта 1900 года, оказавшим существенное влияние на развитие математики в XX веке; из 23 проблем Гильберта большинство уже решены, и только…

Хорновский дизъюнкт — дизъюнктивный одночлен с не более чем одним положительным литералом. Изучены Альфредом Хорном (англ. Alfred Horn) в 1951 году в связи с их важной ролью в теории моделей и универсальной алгебре. Впоследствии стали основой для языка логического программирования Пролог, в котором программа являются непосредственно набором хорновских дизъюнктов, а также нашли важные приложения в конструктивной логике и теории сложности вычислений.

Алгори́тм (лат. al­go­rithmi — от арабского имени математика Аль-Хорезми) — конечная совокупность точно заданных правил решения произвольного класса задач или набор инструкций, описывающих порядок действий исполнителя для решения некоторой задачи. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Независимые инструкции могут выполняться…

Арифметика Пресбургера — это теория первого порядка, описывающая натуральные числа со сложением, но в отличие от арифметики Пеано, исключающая высказывания относительно умножения. Названа в честь польского математика Мойжеша Пресбургера, который в 1929 году предложил соответствующую систему аксиом в логике первого порядка, а также показал её разрешимость.

Алгоритмическая теория информации — Scholarpedia

Эта статья представляет собой краткое руководство в области алгоритмической информации.
теории (AIT), лежащей в ее основе философии и наиболее важных
концепции. AIT возникает путем смешения теории информации и вычислений.
теории для получения объективного и абсолютного представления об информации в
индивидуальный объект, и тем самым порождает цель и
робастное понятие случайности отдельных объектов. Это в отличие от
классическая теория информации, основанная на случайных величинах и
коммуникации, и не имеет отношения к информации и случайности
отдельные объекты.После краткого обзора основные подполя,
представлены приложения, история и карта поля.

Обзор

Алгоритмическая теория информации (AIT) — это
теория информации отдельных объектов, использующая
информатики и занимается
взаимосвязь между вычислением, информацией и случайностью.

Информационное содержание или сложность объекта можно измерить с помощью
длина его кратчайшего описания. Например, строка

 "01010101010101010101010101010101010101010101010101010101010101"
 

имеет краткое описание «32 повторения ’01’», а

 "1100100001100001110111101110110011111010010000100101011110010110"
 

предположительно не имеет простого описания, кроме записи строки
сам.Более формально, алгоритмическая «колмогоровская» сложность
(AC) строки \ (x \) определяется как длина кратчайшего
программа, которая вычисляет или выводит \ (x \, \), где программа выполняется на
какой-то фиксированный эталонный универсальный компьютер.

Близким понятием является вероятность того, что универсальный
компьютер выводит некоторую строку \ (x \) при загрузке с выбранной программой
наугад. Эта алгоритмическая
Вероятность «Соломонова» (AP) является ключом к решению старых
философская проблема индукции формально.

Главный недостаток AC и AP — их несовместимость.
Ограниченная по времени сложность «Левина» наказывает медленную программу, добавляя
логарифм времени его работы до его длины. Это ведет к
вычислимые варианты AC и AP, а также универсальный поиск «Левин»
(США), который решает все задачи инверсии оптимальным образом (за исключением некоторых нереально больших
мультипликативная постоянная) время.

AC и AP также позволяют формальное и строгое определение случайности
отдельных струн, не зависящих от физических или
философские интуиции о недетерминизме или вероятности.Грубо говоря, строка является алгоритмической случайной последовательностью «Мартина-Лёфа» (AR), если она несжимаема в том смысле, что ее алгоритмическая сложность равна ее длине.

AC, AP и AR являются основными дисциплинами AIT, но AIT порождает
во многие другие области. Он служит основой
Минимальная длина описания (MDL)
принцип, может упростить доказательства в теории сложности вычислений,
был использован для определения универсальной метрики сходства между
объекты, решает проблему демона Максвелла и многие другие.

Алгоритмическая «колмогоровская» сложность (АК)

Алгоритмическая сложность формализует понятия простоты и
сложность. Интуитивно строка проста, если ее можно описать в
несколько слов, например «строка из миллиона единиц», и является сложным, если
нет такого короткого описания, как для случайной строки, у которой
кратчайшее описание указывает буквально по частям. Обычно
интересуют только описания или коды , , которые действуют
в том смысле, что декодеры — это алгоритм, на каком-то компьютере.Универсальная машина Тьюринга \ (U \) является стандартной
абстрактная модель универсального компьютера в теоретическом компьютере
наука. Мы говорим, что программа \ (p \) является описанием
строка \ (x \), если \ (p \) запускается на выходах \ (U \)
\ (x \, \) и пишем \ (U (p) = x \. \) Длина
кратчайшее описание обозначается
\ [
K (x): = \ min_p \ {\ ell (p): U (p) = x \}
\]
где \ (\ ell (p) \) — длина \ (p \), измеренная в
биты. Можно показать, что это определение не зависит от выбора
\ (U \) в том смысле, что \ (K (x) \) заменяется на
наиболее аддитивная постоянная, не зависящая от \ (x \.\) Заявление
и доказательство этой теоремы инвариантности (Соломонов, 1964, Колмогоров
1965, Чайтин 1969) часто считают рождением алгоритмических
теория информации.
Это можно назвать тезисом Колмогорова:
интуитивное понятие «кратчайший эффективный код» в самом широком смысле
охвачены формальным понятием колмогоровской сложности, и никаким формальным
механизм может дать существенно более короткий код. Обратите внимание, что
кратчайший код — это тот, для которого есть общий декомпрессор:
Колмогоровская сложность устанавливает предельные пределы того, насколько коротким
файл может быть сжат универсальным компрессором.

Есть много вариантов, в основном по техническим причинам:
исторически первая «простая» сложность, теперь более важная «префикс»
сложность и многие другие. Большинство из них совпадают в пределах добавки
член в длине строки. На этой странице Wiki мы используем \ (K \) для
вариант сложности префикса. Префиксная машина Тьюринга имеет отдельную
входная лента, которую он читает слева направо без резервного копирования,
отдельная рабочая лента, на которой происходит вычисление, и отдельная
выходная лента, на которой записан выход.* \) на так называемом универсальном префиксе Тьюринга
машина \ (U \) с выходом \ (x \) и входом
\ (y \) (Ли, Витаньи, 1997).

Для нестроковых объектов (например, чисел \ (n \, \) пар строк \ ((x, y) \, \)
или вычислимые функции \ (f \)) можно указать некоторую кодировку по умолчанию
\ (\ langle \ cdot \ rangle \) и определите
\ (K (\ mbox {объект}): = K (\ langle \ mbox {объект} \ rangle) \. \)

Рисунок 1: Схематический граф префикса колмогоровской сложности \ (K (x) \) со строкой \ (x \), интерпретируемой как целое число. \ (K (x) \ geq \ log x \) для «большинства» \ (x \) и \ (K (x) \ leq \ log x + 2 \ log \ log x + c \) для всех \ (x \) для подходящей постоянной \ (c \.{-K (x)} \ leq 1 \, \)

, где все (не) равенства выполняются в пределах аддитивной константы.Кроме того, он имеет много общих свойств с энтропией Шеннона.
(информационная мера), но \ (K \) имеет много преимуществ.
Схематический график \ (K \) как целочисленной функции изображен
на рисунке 1.

Алгоритмическая вероятность «Соломонова» (AP)

Соломонов (1964) рассмотрел вероятность того, что универсальный
компьютер выводит некоторую строку \ (x \) при загрузке с выбранной программой
наугад. Эта алгоритмическая «вероятность Соломонова»
(AP) является ключом к формальному решению старой философской проблемы индукции.Он основан на

• Бритва Оккама (выберите самую простую модель, соответствующую данным),
• Принцип множественных объяснений Эпикура (согласовывать все объяснения с данными),
• Правило Байеса (преобразовать априорное распределение в апостериорное согласно свидетельствам, экспериментально полученным данным),
• Универсальные машины Тьюринга (для вычисления, количественной оценки и присвоения кодов всем интересующим величинам) и
• алгоритмическая сложность (чтобы определить, что означает простота / сложность).{-K (x)} \, \), оправданное неравенством Крафт выше.
  Определение
  Алгоритмическая вероятность «Соломонова» (AP), также называемая универсальной
  априорная вероятность уточнена Л.А. Левиным.
  Мы можем выделить априорную вероятность дискретных объектов \ (x \, \)
  как натуральные числа или конечные двоичные строки, обычно обозначаемые как \ (m (x) \, \) и априорная функция плотности вероятности непрерывных
  объекты, как и семейство всех конечных и бесконечных двоичных последовательностей,
  обозначается \ (M \. \) Подробнее см. на странице Алгоритмическая вероятность «Соломонова».Дискретная версия — это вероятность того, что на выходе
  универсальный префикс машины Тьюринга \ (U \) равен \ (x \)
  когда на входной ленте предусмотрены честные подбрасывания монет. Непрерывное понятие подходит для приложений к предсказанию следующего элемента в растущей временной последовательности, и именно это понятие было изобретено Соломоновым. \ (M (x) \) означает меру вероятности, сосредоточенную на множестве всех двоичных последовательностей (конечных или бесконечных), начинающихся с \ (x \. \). Формально \ (M \)
  можно определить как
  \ [
  М (х) \;: = \; \ sum_ {p \;: \; U (p) = x *} 2 ^ {- \ ell (p)}
  \]
  где сумма по всем (так называемая минимальная, не обязательно
  остановка, обозначаемая *) программы \ (p \), для которых \ (U \) выводит строку
  начиная с \ (x \.{-K (x) -O (\ log | x |)} \. \)

  \ (M \) обладает такими же замечательными свойствами, как \ (K \. \). Кроме того,
  прогнозируемое распределение
  \ (M (x_ {n + 1} | x_1 … x_n): = M (x_1 … x_ {n + 1}) / M (x_1 … x_n) \) сходится
  быстро до 1 на (следовательно, предсказывает) любую вычислимую последовательность
  \ (x_1 x_2 x_3 … \. \) Это довольно тривиально. Но, что примечательно, можно также показать, что \ (M \) приводит к отличным
  прогнозы и решения в общих стохастических средах, как описано на странице AP. Алгоритмическая вероятность «Соломонова». Если
  женился на теории последовательных решений, это
  приводит к оптимальному агенту обучения с подкреплением, встроенному в
  произвольная неизвестная среда (Hutter 2005) и формальная
  определение и проверка интеллекта.

  Формально связанная величина — это вероятность того, что \ (U \) остановится, когда
  обеспечен правильным подбрасыванием монеты на входной ленте (т. е. случайный
  компьютерная программа в конечном итоге остановится). Эта вероятность остановки,
  также известная как константа Чайтина \ (\ Omega \, \) или «число мудрости»
  обладает множеством замечательных математических свойств и может использоваться для
  для количественной оценки теоремы Гёделя о неполноте.

  Универсал «Левин» Поиск (США)

  Рассмотрим проблему, для решения которой у нас есть два потенциальных
  алгоритмы \ (A \) и \ (B \, \), например, сначала ширина по сравнению с глубиной
  поиск в конечном (игровом) дереве.Написано много, о чем
  алгоритм лучше при каких обстоятельствах. Рассмотрим
  следующее альтернативное очень простое решение проблемы: A
  мета-алгоритм \ (US \) запускает \ (A \) и \ (B \) параллельно и ожидает
  первый алгоритм остановиться с ответом. Поскольку \ (US \) эмулирует \ (A \) и
  \ (B \) с половинной скоростью, время работы \ (US \) является минимумом
  \ (2 \ times \) время \ ((A) \) и \ (2 \ times \) время \ ((B) \, \)
  то есть \ (US \) так же быстро, как и самый быстрый из двух, за исключением коэффициента 2. Небольшие коэффициенты, такие как 2
  часто незначительны по сравнению с потенциально гораздо большей разницей в
  время работы \ (A \) и \ (B \.{- \ ell (p)} \) каждой (префиксной) программе \ (p \. \) Во-вторых,
  поскольку не все программы решают проблему (некоторые никогда не останавливаются, некоторые просто
  print «Hello World» и т. д.) \ (US \) должен проверить, соответствует ли вывод
  действительно решение, а если не откажитесь от него и продолжайте.

  Как это вписывается в МТА?
  Проблема AC \ (K \) — его невычислимость.
  Ограниченная по времени сложность «Левина» наказывает медленную программу, добавляя
  логарифм его времени на его длину:
  \ [
  Кт (х) \; = \; \ min_p \ {\ ell (p) + \ log (\ mbox {time} (p)): U (p) = x \}
  \]
  Легко видеть, что \ (Kt (x) \) — это просто логарифм бегущей
  время (без проверки) \ (US \, \) и, следовательно, вычислимо.

  Хотя универсальный поиск хорош в теории, он неприменим в
  эта форма из-за огромных скрытых мультипликативных констант в
  время. Еще одно ограничение — проверка должна быть быстрой.
  Хаттер (2005) разработал более общий
  асимптотически самый быстрый алгоритм, удаляющий мультипликативный
  постоянная и необходимость поверки, к сожалению за счет
  еще большей аддитивной постоянной. Шмидхубер (2006) разработал первые практические варианты
  \ (US \), тщательно выбрав язык программирования (\ (U \)),
  адаптивно распределяя время в \ (США \), проектируя обучающие последовательности
  увеличение сложности, повторное использование подпрограмм из более ранних более простых
  проблемы, и разные другие «хитрости».Он также определил скорость
  Prior, который для \ (Kt \) то же, что AP для AC.

  Алгоритмическая случайность «Мартина-Лёфа» (AR)

  Математическая формализация понятия вероятности или
  шанс имеет долгую переплетенную историю. Стандартные (теперь) аксиомы
  Вероятность, изучаемая всеми учениками, принадлежит Колмогорову (1933).

  Хотя математически убедительно, семантика далеко не ясна.
  Фраквенционисты интерпретируют вероятности как пределы наблюдаемого относительного
  частоты, объективисты считают их реальными аспектами мира,
  субъективисты рассматривают их как степень своей веры (часто вызываемой
  от коэффициентов ставок), в то время как Курно придает значение только событиям
  с высокой вероятностью, а именно, что наверняка произойдет в нашем мире.

  Ни один из этих подходов не отвечает на вопрос:
  некоторый конкретный индивидуальный объект или наблюдение, например двоичные строки
  выше, является случайным. Аксиомы Колмогорова не позволяют задавать такие вопросы.
  вопросы.

  Фон Мизес (1919), с уточнениями его подхода Уолдом (1937), и
  Чёрч (1940) с разной степенью успеха попытался формализовать
  интуитивное представление о том, что одна строка выглядит более случайной, чем другая
  (см. пример во введении). Например, если родственник
  частота единиц в бесконечной последовательности не сходится к 1/2, она равна
  явно не случайный, но обратное неверно: например
  «0101010101… «не случайно, так как пара» 01 «встречается слишком часто.
  Псевдослучайные последовательности, такие как цифры \ (\ pi \, \), вызывают
  самые трудности. К сожалению, ни одна последовательность не может удовлетворить все
  тесты на случайность. Подход Мизеса-Вальда-Черча казался удовлетворительным
  пока Вилле (1939) не показал, что некоторые последовательности случайны в соответствии с
  их определение и все же не имеют определенных свойств, которые универсально
  согласились быть удовлетворенными случайными последовательностями. Например, относительный
  частота единиц во все более длинных начальных сегментах должна
  бесконечно часто переключайтесь с более 1/2 на менее 1/2 и наоборот.

  Martin-Loef (1966), вместо того, чтобы дать определение и проверить,
  выполнил все требования, применил подход к формализации понятия
  всех эффективно тестируемых требований в виде тестов на случайность.
  Тесты конструктивные (а именно все и только нижние
  полувычислимые), о которых обычно никто не заботится.
  Поскольку тесты построены на машинах Тьюринга, они могут быть
  эффективно пронумерованы в соответствии с эффективным перечислением
  Они произошли от машин Тьюринга.Поскольку набор последовательностей
  удовлетворяет тесту (имеет свойство случайности, которое проверяет тест), имеет
  измерить один, и есть только счетное множество тестов, набор
  последовательности, удовлетворяющие , все таких тестов также имеют единицу измерения. Эти
  те, которые называются алгоритмически «случайным методом Мартина-Лёфа» (AR).
  Теория разработана как для конечных струн, так и для
  бесконечные последовательности. В последнем случае понятие теста больше
  сложно, и мы говорим о последовательных тестах.

  Для бесконечных последовательностей можно показать, что это в точности
  последовательности, несжимаемые в том смысле, что
  алгоритмическая префиксная сложность каждого начального сегмента не менее
  их длина.Точнее, бесконечная последовательность
  \ [
  x_1 x_2 x_3 … \ mbox {это AR}
  \ quad \ Longleftrightarrow \ quad K (x_1 … x_n) \ geq n
  \ mbox {для всех суф. large} n
  \]
  важный результат Г.Дж. Chaitin и C. Schnorr. Это понятие
  имеет интуитивный смысл: строка может быть сжата , если есть
  некоторые закономерности в строке , если строка не случайна.

  • ML-случайные последовательности не могут быть эффективно построены. Тем не менее, мы можем привести естественный пример: вероятность остановки, \ (\ Omega \) — это действительное число от 0 до 1, а последовательность битов в его двоичном расширении представляет собой бесконечную ML-случайную последовательность.
  • Также можно определить случайность других объектов, кроме строк и последовательностей.
  • Соединяя теорию AR с теорией рекурсии (Дауни и Хиршфельд, 2007), мы обнаруживаем иерархию понятий случайности, по крайней мере, если мы выходим из области вычислимости согласно Тьюрингу. В зависимости от точного определения понятия «конструктивный» можно получить множество вариантов. В частности, «относительная случайность», основанная на (останавливающих) машинах-оракулах, приводит к богатой области, связанной с теорией рекурсии.
  • Наконец, грубое двоичное разделение случайных и неслучайных строк можно уточнить, грубо говоря, рассматривая строки с \ (K (x_1 … x_n) = \ alpha n \) для некоторого \ (0 <\ alpha <1 \. \) Если строки интерпретируются как (разложение) действительных чисел, это приводит к понятию конструктивной или эффективной хаусдорфовой (фрактальной) размерности.

  Приложения AIT

  Несмотря на несоизмеримость основных концепций, AIT имеет много
  часто неожиданные приложения.

  Философия

  AIT помогает решать многие философские проблемы в смысле
  что он позволяет формализовать и количественно оценить многие интуитивно понятные, но расплывчатые
  концепции большого значения, как мы видели выше, и, следовательно,
  позволяет говорить о них содержательно и строго, таким образом
  ведет к более глубокому пониманию, чем без AIT.

  Самое главное, AC формализует и количественно определяет концепции
  простота и сложность уникальным способом. Ядро
  научная парадигма — бритва Оккама, обычно интерпретируемая как «среди
  две модели, которые одинаково хорошо описывают данные, более простая
  следует предпочесть. «Использование AC для количественной оценки» простых «разрешено
  Соломонов и другие, чтобы развить свои универсальные теории
  индукция и действие, в области искусственного интеллекта.

  AIT также полезен в основах термодинамики и ее
  вторая теорема об увеличении энтропии, и в частности для решения
  проблема демона Максвелла.

  Практика

  Приближая (часто грубо) к «идеальным» концепциям, AIT имеет
  был применен к различным проблемам, представляющим практический интерес, например, в
  лингвистика и генетика. Основная идея — заменить
  универсальная машина Тьюринга \ (U \) более ограниченными машинами «Тьюринга»,
  часто адаптируется к решаемой проблеме. Основная проблема в том, что
  точность аппроксимации трудно оценить, и большинство теорем в AIT
  сломать.

  Универсальная метрика подобия, вероятно,
  наибольший практический успех AIT: разумное определение для
  сходство между двумя объектами заключается в том, насколько сложно
  преобразовать их друг в друга.Более формально можно было бы определить
  сходство между строками \ (x \) и \ (y \) как длина самого короткого
  программа, которая вычисляет \ (x \) из \ (y \)
  (что есть \ (K (x | y) \)).
  Симметризация и нормировка приводят к универсальному подобию
  метрической и аппроксимирующей \ (K \) стандартными компрессорами, такими как
  Lempel-Ziv (zip) или bzip2 или PPMZ приводит к нормализованному сжатию
  расстояние, которое использовалось для полностью автоматического восстановления
  языковые и филогенетические деревья и многие другие кластеры
  проблемы.См. Приложения AIT
  для получения подробной информации и ссылок.

  Наука

  В самой науке AIT может конструктивизировать другие области:
  Например, утверждения теории информации Шеннона и классических
  теория вероятности обязательно выполняется только в ожидании или с высокой
  вероятность. Теоремы обычно имеют вид «существует множество
  меры X, для которой выполняется Y «, т. е. они полезны для (больших)
  образцы. AR, с другой стороны, может построить
  устанавливает себя, а результаты сохраняются для отдельных наблюдений / строк.Размерность Хаусдорфа и действительные числа также имеют конструктивную
  аналоги.

  Естественно, концепции AIT также использовались в математике и
  собственно теоретическая информатика: AIT, через несжимаемость
  метод, решил многие открытые проблемы вычислительной сложности
  теории и математики, упростили многие доказательства и
  важен для понимания (бездиссипативных) обратимых вычислений. Это
  нашла применение в статистике, когнитивных науках, биологии,
  Физика и экономика.

  AIT также может служить обобщающей теорией для других, более практичных
  поля, например, в машинном обучении минимальная длина описания
  (MDL) принцип можно рассматривать как уменьшенную практическую версию
  AC.

  История, ссылки, обозначения, номенклатура

  Андрей Колмогоров
  (1965) предложили определять информационное содержание объекта как
  длина самой короткой программы, вычисляющей ее представление.
  Рэй Соломонов (1964) изобрел
  тесно связанное универсальное априорное распределение вероятностей и
  использовал его для прогнозирования временных рядов.Грегори Чайтин опубликовал в (1966) родственное, но не инвариантное понятие,
  а в (1969) в последнем разделе введена также колмогоровская сложность.
  Вместе это положило начало области алгоритмической теории информации в
  1960-е гг. Леонид Левин и
  другие внесли значительный вклад в эту область в 1970-х гг.
  (см., например, Звонкин и Левин 1970). В частности префикс
  сложность и ограниченная по времени сложность (в основном) из-за него.

  Li and Vitanyi (1997) — стандартный учебник по AIT. Книга Калуде
  (2002) сосредотачивается на AC и AR, Hutter (2005) на AP и США, а Downey
  и Hirschfeldt (2007) по AR.Веб-сайт МТА по адресу
  http://www.hutter1.net/ait.htm содержит дополнительные ссылки, список
  активные исследователи, список рассылки, список мероприятий AIT и многое другое.

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

  Даже название всего поля не является общепринятым.
  Алгоритмическая теория информации , изобретенная Грегори Чейтиным,
  кажется наиболее подходящим, поскольку он описательный и безличный, но
  поле также часто называют
  срок Колмогорова сложность .

  Карта поля

  Поле AIT можно разделить примерно на 4 отдельных подполя:
  AC, AP, США и AR.Пятый пункт ниже относится к приложениям.

  Алгоритмическая «колмогоровская» сложность (АК)

  • Философские соображения
  • Свойства переменного тока
  • Простая (Колмогоровская) сложность
  • Сложность префикса
  • Сложность, ограниченная ресурсами
  • Прочие варианты сложности

  Алгоритмическая «вероятность Соломонова» (AP)

  • Бритва Оккама, принцип Эпикура и правило Байеса
  • Дискретная алгоритмическая вероятность
  • Непрерывная алгоритмическая вероятность = априорная полумера
  • Универсальное предсказание последовательности
  • Вероятность остановки = Омега Чейтина = Число Мудрости

  Универсальный «Левин» Поиск (США)

  • Левин поиск
  • Левин сложность и скорость приора
  • Адаптивный поиск Левина
  • Самые быстрые алгоритмы для решения общих задач
  • Оптимально упорядоченный решатель проблем
  • Станки Goedel

  Алгоритмическая случайность «Мартина-Лёфа» (AR)

  • Теория рекурсии
  • Действующие действительные числа
  • Случайность вещественных чисел
  • случайность фон Мизес-Вальда-Черча
  • Случайность Мартина-Лёфа
  • Больше концепций случайности и относительной случайности
  • Эффективное измерение Хаусдорфа

  Приложения AIT

  Список литературы

  С.С. Калуде Информация и случайность: алгоритмическая перспектива .
  Springer, Berlin, 2-е издание, 2002 г. http://www.springer.com/chl/home/generic/search/results?SGWID=2-40109-22-2151448-0

  Г. Дж. Чайтин О длине программ для вычисления конечных двоичных последовательностей:
  Статистические соображения. Журнал ACM , 16 (1): 145-159, 1969. http://www.cs.auckland.ac.nz/CDMTCS/chaitin/acm66.pdf

  Р. Дауни и Д. Р. Хиршфельдт
  Алгоритмическая случайность и сложность .Springer, Berlin, 2007. http://www.springer.com/chl/home/generic/search/results?SGWID=2-40109-22-52080531-0

  М. Хаттер
  Универсальный искусственный интеллект: последовательные решения на основе алгоритмической вероятности .
  Springer, Berlin, 2005. http://www.springer.com/chl/home/generic/search/results?SGWID=2-40109-22-34425910-0

  Колмогоров А.Н.
  Три подхода к количественному определению информации.
  Проблемы информации и передачи , 1 (1): 1-7, 1965.http://commonsenseatheism.com/wp-content/uploads/2013/04/Kolmogorov-Three-Approaches-to-the-Quantiative-Definition-of-Information.pdf

  М. Ли и П. М. Б. Витаньи
  Введение в колмогоровскую сложность и ее приложения.
  Спрингер, Нью-Йорк, 2-е издание, 1997 г., и 3-е издание, 2007 г.
  http://www.springer.com/chl/home/generic/search/results?SGWID=2-40109-22-165245230-0

  Дж. Шмидхубер
  Новый ИИ: общие и звуковые, актуальные для физики.
  В Настоящий ИИ: новые подходы к общему искусственному интеллекту .Springer, 2006. http://www.idsia.ch/~juergen/newai/

  Р. Дж. Соломонов Формальная теория индуктивного вывода:
  Части 1
  и 2.
  Информация и контроль , 7: 1–22 и 224–254, 1964.

  Звонкин А.К., Левин Л.А.
  Сложность конечных объектов и развитие концепций
  информации и случайности с помощью теории алгоритмов.
  Российские математические обзоры , 25 (6): 83—124, 1970.

  Внутренние ссылки

  • Маркус Хаттер, Шейн Легг, Пол М.Б. Витани (2007) Алгоритмическая вероятность. Scholarpedia, 2 (8): 2572.
  • Родни Г. Дауни и Ян Рейманн (2007) Алгоритмическая случайность. Scholarpedia, 2 (10): 2574.
  • Пол М.Б. Витаньи (2007) Андрей Николаевич Колмогоров. Scholarpedia, 2 (2): 2798.
  • Мин Ли и Пол М. Б. Витаньи (2007) Приложения алгоритмической теории информации. Академия наук, 2 (5): 2658.
  • Олаф Спорнс (2007) Сложность. Scholarpedia, 2 (10): 1623.
  • Томаш Даунарович (2007) Энтропия.Академия наук, 2 (11): 3901.
  • Марк Аронофф (2007) Язык. Scholarpedia, 2 (5): 3175.
  • Маттео Гальоло (2007) Универсальный поиск. Scholarpedia, 2 (11): 2575.

  Внешние ссылки

  См. Также

  Алгоритмическая сложность, алгоритмическая вероятность, алгоритмическая случайность, приложения AIT, теория рекурсии, универсальный поиск

  .

  Алгоритмическая случайность — Scholarpedia

  Алгоритмическая случайность — это исследование случайных отдельных элементов в пространствах выборок, в основном набора всех бесконечных двоичных последовательностей. Алгоритмически случайный элемент проходит все эффективно разработанные тесты на случайность.

  ---

  Обзор

  Теория алгоритмической случайности пытается прояснить, что это означает для отдельного элемента пространства выборки, например последовательность подбрасываний монеты, представленная в виде двоичной строки, должна быть случайной.В то время как формализация классической теории вероятностей Колмогоровым присваивает вероятности множествам результатов и определяет, как рассчитывать с такими вероятностями, она не делает различий между отдельными случайными и неслучайными элементами. Например, при равномерном распределении результат «000000000000000 …. 0» (n нулей) имеет ту же вероятность, что и любой другой результат n подбрасываний монеты, а именно 2 ^-n . Однако есть интуитивное ощущение, что последовательность всех нулей не очень случайна.Это тем более верно, если смотреть на бесконечные последовательности. Представляется желательным пояснить, что мы имеем в виду, когда говорим о случайном объекте . Современный взгляд на алгоритмическую случайность предлагает три парадигмы, позволяющие отличать случайные элементы от неслучайных.

  • Непредсказуемость : Должно быть невозможно выиграть против случайной последовательности в честной игре ставок при использовании возможной стратегии ставок .
  • Несжимаемость : Сжать произвольную последовательность должно быть невозможно.
  • Измерьте теоретическую типичность : Случайные последовательности проходят все возможные статистические тесты.

  Характерной чертой алгоритмической случайности является то, что она интерпретирует допустимое как алгоритмически выполнимое .

  Теоретические основы вычислимости

  Теория алгоритмической случайности основывается на понимании эффективности, как это дает теория вычислимости . Основное понятие — это (частичная) вычислимая функция \ (f: \ mathbb {N} \ to \ mathbb {N} \.\) \ (f \) определяется как вычислимое (или рекурсивное ), если оно может быть вычислено машиной Тьюринга . Широко признанный тезис Чёрча-Тьюринга утверждает, что «каждая функция, которую естественно рассматривать как вычислимую, может быть вычислена машиной Тьюринга».

  Вычислимость также может быть определена в областях, отличных от натуральных чисел, с помощью эффективного кодирования. Например, мы можем идентифицировать натуральные числа с их двоичным расширением и определять вычислимые функции на множестве 2 ^<ω = {0,1} ^* всех конечных двоичных последовательностей.Используя функцию спаривания (эффективная инъекция \ (\ mathbb {N} \ times \ mathbb {N} \) в \ (\ mathbb {N} \)), можно определить вычислимость на рациональных числах \ (\ mathbb {Q} \. \) Ниже приведены наиболее общие понятия вычислимости, используемые в алгоритмической случайности.

  • Подмножество \ (X \ substeq \ mathbb {N} \) натуральных чисел вычислимо, если его характеристическая функция \ (\ chi_X: \ mathbb {N} \ to \ {0,1 \} \) равна .
  • Вычислимое действительное число — это действительное число с вычислимым двоичным расширением.{-n}.
    \]
    Следовательно, для реальной функции быть вычислимой означает быть эффективно аппроксимируемой с произвольной степенью точности.
    • Набор \ (X \ substeq \ mathbb {N} \) является вычислимо перечислимым (c.e.), если он является областью определения частично вычислимой функции.
    • Действительное число α равно слева. , если существует равномерно вычислимая возрастающая последовательность \ ((\ gamma) _n \) рациональных чисел такая, что \ (\ lim_n \ gamma_n = \ alpha \. \) Это эквивалентно ее левому сечению \ (\ {\ gamma \ in \ mathbb {Q}: \ gamma <\ alpha \} \) является c.е. набор рациональных.
    • Функция \ (g: \ mathbb {N} \ to \ mathbb {R} \) — это слева-c.e. или перечисляются снизу , если

    \ [
    \ {(\ gamma, k) \ in \ mathbb {Q} \ times \ mathbb {N}: \ gamma

    Развитие алгоритмической случайности в 20 веке

    Систематическое изучение алгоритмической случайности началось в начале 20 века с работы фон Мизеса (1919). Он предложил подход, который позже стал известен как стохастичность .Стремясь к частотной интерпретации вероятности, он определил случайные последовательности как члены так называемого Kollektivs . Идея фон Мизеса заключается в том, что члены Коллектива должны пройти все соответствующие статистические тесты. Двоичная последовательность является элементом коллектива, если

    • имеет предельную частоту, а

    ,

    • , предельная частота сохраняется для любой подпоследовательности, которая выбирается посредством допустимого правила выбора .

    Фон Мизес не пояснил, что следует понимать как допустимое правило.Лишь годы спустя, с развитием теории вычислимости, Черч (1940) и другие утверждали, что «допустимое» следует интерпретировать как «выполнимое с вычислительной точки зрения». Это привело к понятию фон-Мизеса-Вальда-Черча-стохастичности . Фундаментальное возражение против концепции фон Мизеса было высказано Вилле (1939). Он показал, что для любого счетного набора правил выбора существуют элементы результирующего Коллектива, которые не удовлетворяют закону повторного логарифма .

    В конце концов Мартин-Лёф (1966) преодолел эти трудности, отметив, что каждый эффективный статистический тест может быть закодирован как эффективный нулевой набор.

    Случайность Мартина-Лёфа

    Набор всех бесконечных двоичных последовательностей называется канторовским пространством и обозначается 2 ^ω . 2 ^ω можно интерпретировать как полное бесконечное двоичное дерево . Он имеет каноническую топологию, порожденную множествами цилиндров [w], которые состоят из всех бесконечных последовательностей, продолжающих конечную строку w. Отождествляя действительные числа с их бесконечным двоичным расширением, мы можем интерпретировать элементы пространства Кантора как вещественных чисел .{- | w |},
    \]
    где \ (| w | \) обозначает длину \ (w \. \)

    Основная парадигма теории вероятностей состоит в том, что типичный результат случайного эксперимента с распределением λ (например, бесконечные последовательности справедливых подбрасываний монеты) формирует набор меры Лебега один. Однако в классической структуре невозможно определить отдельную случайную последовательность, поскольку каждая отдельная последовательность α, рассматриваемая как одноэлементное подмножество пространства Кантора, является набором нулевой меры. Идея Мартина-Лёфа состоит в том, чтобы выбрать счетное семейство нулевых множеств, эффективных тестов на случайность , и определить последовательность как случайную, если она не содержится ни в одном из этих нулевых множеств.{\ omega} \) проходит тест \ (W \), если
    \ [
    \ alpha \ not \ in \ bigcap_n \ bigcup_ {w \ in W_n} [w].
    \]
    Другими словами, α не содержится в множестве нулей, задаваемом \ (W \. \), Α — случайный Мартина-Лёфа, если он проходит все тесты Мартина-Лёфа.

    Существует только счетное количество тестов Мартина-Лёфа, поэтому объединение всех нулевых множеств, заданных тестами, является набором нулевой меры. Следовательно, множество всех случайных последовательностей Мартина-Лёфа имеет меру Лебега один. В частности, существуют случайные последовательности Мартина-Лёфа.

    Несжимаемость — колмогоровская сложность

    Альтернативный подход к случайности — несжимаемость. Случайная последовательность должна иметь алгоритмически несжимаемые начальные сегменты. К сожалению, в отношении простой колмогоровской сложности C таких последовательностей не существует (Martin-Löf, 1966). Неформально говоря, причина этого в том, что строка \ (w \) дает \ (w + | w | \) много информации. Независимо, Левин и Чайтин предложили вариант простой сложности, без префиксов колмогоровской сложности K, который позволяет обойти эту проблему.

    Последовательность α является алгоритмически случайной , если существует константа c такая, что для всех n,
    \ [
    K (\ alpha \ upharpoonright n) \ geq n — c,
    \]
    где \ (\ alpha \ upharpoonright n \) обозначает первые n битов α.

    Шнорр показал, что последовательность является случайной по Мартину-Лёфу тогда и только тогда, когда она алгоритмически случайна. Он и Левин также охарактеризовали случайность Мартина-Лёфа в терминах связанного понятия сложности, названного монотонной сложностью . Характеристики с точки зрения простой сложности были даны Гачем (1980) и Миллером и Ю (2006).{\ geq 0} \) такая, что для всех строк \ (w \, \)
    \ [
    2 M (w) = M (w0) + M (w1).
    \]
    M можно рассматривать как игру со справедливыми ставками, где M моделирует функцию капитала. \ (M (w) \) представляет собой столицу после того, как были обнаружены биты \ (w (0) \ dots w (| w | -1) \). Справедливость игры отражается в том факте, что ожидаемая стоимость капитала игрока после следующего раунда \ ([M (w0) + M (w1)] / 2 \) равна его текущему капиталу. Мартингал вычислимо перечислим (в. П.), Если он в. П. Слева. как функция.

    Мартингал M следует за в последовательности α, если
    \ [
    \ limsup_n M (\ alpha \ upharpoonright n) = \ infty.\]

    Шнорр (1971) показал, что последовательность α является случайной по Мартину-Лёфу тогда и только тогда, когда не существует в.п. мартингал M, который преуспевает на α.

    Ω и к.э. Чайтина случайные числа

    Внутренняя особенность алгоритмической случайности состоит в том, что трудно показать индивидуальную случайную последовательность. Например, из определения случайности легко следует, что никакая вычислимая последовательность не может быть случайной по Мартину-Лёфу.

    Чайтин (1976) определил действительное число \ (\ Omega \.{- | w |}.
    \]
    Чайтин смог показать, что \ (\ Omega \) случайна по Мартину-Лёфу. (Напомним, что мы отождествляем действительные числа с их бесконечными двоичными расширениями.)

    \ (\ Omega \) — вычислимо перечислимое вещественное число. Это полный по Тьюрингу в том смысле, что он эквивалентен по Тьюрингу проблеме остановки \ (\ emptyset ‘\. \) Следовательно, с вычислительной точки зрения, биты Ω так же трудно решить, как и вопрос, является ли универсальная машина Тьюринга останавливается на заданном входе.

    \ (\ Omega \) не единственное случайное вещественное число с этим свойством, но оно справедливо для любого c.е. случайный реальный. На самом деле между такими реалами существует очень сильная однородность. Для любых в.э. действительный α, следующие эквивалентны (Kucera and Slaman, 2001, и др.).

    • α — случайный результат Мартина-Лёфа.
    • Для всех в.э. reals β существует такое c, что для всех n \ (K (\ beta \ upharpoonright n) \ leq K (\ alpha \ upharpoonright n) + c, \. \)
    • α — вероятность остановки некоторой универсальной машины без префиксов.

    Релятивизация, малость и вычислительная мощность случайности

    Относительная случайность

    Релятивизация — центральное понятие теории вычислимости.Если снабдить машину Тьюринга лентой оракула , которая хранит бесконечную двоичную последовательность, биты которой могут быть прочитаны во время вычисления, можно определить понятие вычислимого относительно последовательности α . Соответственно, можно релятивизировать другие концепции, такие как «вычислимо перечислимый».

    Что касается теории алгоритмической случайности, то это позволяет релятивизировать случайность Мартина-Лёфа путем релятивизации условий эффективности теста. Следовательно, можно говорить о случайности Мартина-Лёфа относительно последовательности β .

    Для двух последовательностей α, β их соединение α ⊕ β обозначает последовательность, полученную вставкой α в каждую четную позицию, β в каждую нечетную позицию.

    • Теорема Ван Ламбальгена : α ⊕ β является случайным по Мартину-Лёфу тогда и только тогда, когда α является случайным по Мартину-Лёфу, а β является случайным по Мартину-Лёфу относительно α.

    Теорема Ван Ламбальгена подразумевает, что если эффективно разделить случайную последовательность на две половины, эти две половины будут алгоритмически независимыми. В частности, ни одно из них не может вычислить другое.

    Низкая

    Хотя по отношению ко многим оракулам (например, к проблеме остановки) набор относительно случайных последовательностей меньше, чем набор (нерелятивизированных) случайных последовательностей Мартина-Лёфа, существуют оракулы, для которых это неверно. Такие оракулы можно рассматривать как реалы с низким содержанием информации — они не помогают при тестировании на случайность. Следовательно, такие последовательности называются low для (Мартина-Лёфа) случайных . Очевидно, что любая вычислимая последовательность не является случайной.п) + с.
    \)
    (Соловей, 1975, Замбелла, 1990, и др.)

    Работа Nies (2005) и др. Показала, что все три понятия совпадают .

    • Последовательность низкая для случайного тогда и только тогда, когда она низкая для K тогда и только тогда, когда она K-тривиальна.

    Вычислительная мощность случайности

    Строительство Кучера-Тервейн одной из самых больших деревень. low для случайной (и, следовательно, K-тривиальной) последовательности дает решение проблемы Поста , предоставляя пример неполного по Тьюрингу c.е. установлен. Дауни, Хиршфельдт, Найс и Стефан (2002) дали простую, безопасную конструкцию (невычислимой) K-тривиальной в.п. установлен.

    Случайные последовательности Мартина-Лёфа, с другой стороны, могут быть очень мощными в вычислительном отношении.
    Не только левые-к.э. случайные последовательности, полные по Тьюрингу, Кучера (1985) и Гакс (1986) независимо показали, что каждая последовательность сводится по Тьюрингу к случайной последовательности Мартина-Лёфа.

    Однако эта ситуация несколько нетипична. Учитывая левый -c.е. случайная последовательность, почти любая другая случайная последовательность Мартина-Лёфа случайна относительно нее. Более того, теорема Кучера-Гакса перестает выполняться, если заменить случайность Мартина-Лёфа на n-случайность (см. Определение ниже) для n ≥ 2. Фактически, работа Миллера и Ниса и др. показал, что n-случайность для n ≥ 2 имеет слабую вычислительную мощность.

    Другие концепции случайности

    Был изучен ряд альтернатив случайности Мартина-Лёфа.

    Арифметическая случайность

    Можно сделать тесты Мартина-Лёфа более мощными, потребовав только, чтобы набор тестов W был равен c.е. относительно какого-то оракула . Последовательность n-случайная , если она проходит все тесты, относящиеся к c.e. в (n-1) -м прыжке, \ (n \ in \ mathbb {N} \, \) проблемы остановки. Следовательно, случайность Мартина-Лёфа совпадает с 1-случайностью. Среди этих понятий случайности существует строгая иерархия в том смысле, что набор (n + 1) -случайных последовательностей строго содержится в наборе n-случайных последовательностей.

    Вычислимость и случайность Шнорра

    Шнорр (1971) критиковал случайность Мартина-Лёфа как алгоритмически слишком свободную.Он предложил две альтернативы, обе основаны на вычислимом , а не на вычислимо перечислимых тестовых понятиях, как в случае случайности Мартина-Лёфа.

    • Последовательность вычислимо случайна , если вычислимый мартингейл не преуспел в ней.
    • Тест Шнорра — это тест Мартина-Лёфа, в котором мерой каждого набора W _n в тесте является единообразно вычислимое действительное число. Последовательность случайная Шнорра, если она проходит каждый тест Шнорра.

    Случайность Курца

    Курц (1981) предложил определять случайность, избегая всех эффективно замкнутых множеств меры 0. Тест Курца — это эффективно замкнутое множество F (представленное бесконечными путями через вычислимое дерево) такое, что μ (F) = 0. Последовательность случайная последовательность Курца , если она не содержится ни в одном тесте Курца.

    Между различными концепциями случайности выполняются следующие строгие выводы:

    • n-случайность (n ≥ 2) \ (\ Rightarrow \) случайность Мартина-Лёфа \ (\ Rightarrow \) вычислимая случайность \ (\ Rightarrow \) случайность Шнорра \ (\ Rightarrow \) случайность Курца.

    Случайность, ограниченная ресурсами

    Помимо вычислимости, к принципу игры с исключенными ставками можно применить множество других оценок эффективности. Таким образом, можно получить такие понятия, как DTIME (n ^c ) — случайность или случайность для экспоненциального времени . Это было введено Лутцем и имеет приложения в теории сложности.

    Случайность Колмогорова-Ловленда

    В качестве попытки преодолеть критику Вилле стохастичности, Колмогоров и Ловленд независимо друг от друга предложили принять правила отбора, которые выбирают позиции в последовательности немонотонно .То же самое можно применить к мартингалам, если интерпретировать их как ставки в бесконечной последовательности. В немонотонной игре со ставками игрок может выбрать следующую позицию для ставки в произвольном порядке.

    • Последовательность , случайная Колмогорова-Ловленда, если никакая вычислимая немонотонная игра со ставками не завершается успешно.

    Случайность Колмогорова-Ловленда сильнее вычислимой случайности и не более чем случайность Мартина-Лёфа.

    Несложно определить критерии Мартина-Лёфа и, следовательно, случайность для вычислимых мер, отличных от меры Лебега.Важным семейством мер являются меры Хаусдорфа H ^s . Грубо говоря, при определении (внешней) величины H ^s набора диаметр каждого набора, используемого в покрытии, взвешивается показателем s. (Следовательно, мера H ¹ соответствует мере Лебега.) Размерность Хаусдорфа набора определяется как нижняя грань по всем неотрицательным s таким, что набор равен H ^s -null. Рассматривая только эффективные нулевые множества H ^s (для рациональных s), можно определить эффективный аналог размерности Хаусдорфа для отдельных последовательностей:
    \ [
    dim_H ^ 1 \ alpha = \ inf \ {s \ in \ mathbb {Q} ^ +: \ alpha \; \; является \;\; не \; \; H ^ s-случайный \}.1 \ alpha = \ limsup_ {n \ to \ infty} \ frac {K (\ alpha \ upharpoonright n)} {n}
    \]
    Следовательно, эффективный Хаусдорф и размер упаковки последовательности соответствуют ее нижней и верхней алгоритмической плотности соответственно.

    Используя модифицированные мартингалы, называемые termgales , Лутц (2003) определил
    понятие размерности для отдельных конечных струн.

    Список литературы

    Р. Дауни и Д. Р. Хиршфельдт. Алгоритмическая случайность и сложность. Спрингер, Берлин, 2010 г.

    М.Ли и П. М. Б. Витани. Введение в сложность Колмогорова и ее приложения. Спрингер, Нью-Йорк, 2-е издание, 1997 г., и 3-е издание, 2008 г.

    П. Мартин-Лёф. Определение случайных последовательностей. Информация и контроль, 9: 602–619, 1966.

    A. Nies. Вычислимость и случайность. Издательство Оксфордского университета, 2009.

    С.-П. Шнорр. Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. Спрингер, Берлин, 1971.

    Внутренние ссылки

    См. Также

    .

    No related posts.