Машина тьюринга что это

Машина Тьюринга

В 1936 г. Аланом Тьюрингом для уточнения понятия алгоритма был предложен абстрактный универсальный исполнитель. Его абстрактность заключается в том, что он представляет собой логическую вычислительную конструкцию, а не реальную вычислительную машину. Термин «универсальный исполнитель» говорит о том, что данный исполнитель может имитировать любой другой исполнитель. Например, операции, которые выполняют реальные вычислительные машины можно имитировать на универсальном исполнителе. В последствие, придуманная Тьюрингом вычислительная конструкция была названа машиной Тьюринга.
Кроме того, предполагается, что универсальный исполнитель должен уметь доказывать существование или отсутствие алгоритма для той или иной задачи.

Что собой представляет машина Тьюринга?

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

Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие:

Автомат машины Тьюринга в процессе своей работы может выполнять следующие действия:

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

Пример работы машины Тьюринга

Можно усложнить программу. Допустим, головка располагается не обязательно над первым, а над любым символом слова. Тогда программа для данной машины Тьюринга может быть такой (а могла бы быть и другой):

Здесь происходит сдвиг головки влево до тех пор, пока она не окажется над пустым символом. После этого машина переходит в состояние q₂ (команды которого совпадают с командами q₁ предыдущей программы).

Источник

Машина Тьюринга

Маши́на Тью́ринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.

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

Содержание

Устройство машины Тьюринга

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

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

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

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

Описание машины Тьюринга

Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: q_ia_j→q_i1a_j1d_k (если головка находится в состоянии q_i, а в обозреваемой ячейке записана буква a_j, то головка переходит в состояние q_i1, в ячейку вместо a_j записывается a_j1, головка делает движение d_k, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (N)). Для каждой возможной конфигурации имеется ровно одно правило (для недетерминированной машины Тьюринга может быть большее количество правил). Правил нет только для заключительного состояния, попав в которое машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.

Пример машины Тьюринга

Приведём пример МТ для умножения чисел в унарной системе счисления. Машина работает по следующему набору правил:

Умножим с помощью МТ 3 на 2 в единичной системе:

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

Полнота по Тьюрингу

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

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

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

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

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

На машине Тьюринга можно имитировать машину Поста, нормальные алгоритмы Маркова и любую программу для обычных компьютеров, преобразующую входные данные в выходные по какому-либо алгоритму. В свою очередь, на различных абстрактных исполнителях можно имитировать Машину Тьюринга. Исполнители, для которых это возможно, называются полными по Тьюрингу (Turing complete).

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

Варианты машины Тьюринга

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

Машина Тьюринга, работающая на полубесконечной ленте

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

Рассмотрим доказательство, приведённое Ю. Г. Карповым в книге «Теория автоматов». Доказательство этой теоремы конструктивное, то есть мы дадим алгоритм, по которому для любой машины Тьюринга может быть построена эквивалентная машина Тьюринга с объявленным свойством. Во-первых произвольно занумеруем ячейки рабочей ленты МТ, то есть определим новое расположение информации на ленте:

Затем перенумеруем ячейки, причём будем считать, что символ «*» не содержится в словаре МТ:

Наконец, изменим машину Тьюринга, удвоив число её состояний, и изменим сдвиг головки считывания-записи так, чтобы в одной группе состояний работа машины была бы эквивалентна её работе в заштрихованной зоне, а в другой группе состояний машина работала бы так, как исходная машина работает в незаштрихованной зоне. Если при работе МТ встретится символ ‘*’, значит головка считывания-записи достигла границы зоны:

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

Двумерные машины Тьюринга

См. также

Другие абстрактные исполнители и формальные системы вычислений

Ссылки

Литература

Полезное

Смотреть что такое «Машина Тьюринга» в других словарях:

Машина тьюринга — (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча Тьюринга, способна … Википедия

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

машина Тьюринга — Теоретическая модель вычислительного устройства; предложена Аланом Тьюрингом. [http://www.rfcmd.ru/glossword/1.8/index.php?a=index&d=4890] Тематики защита информации EN Turing machine … Справочник технического переводчика

машина Тьюринга — Turing o mašina statusas T sritis automatika atitikmenys: angl. Turing machine vok. Turing Maschine, f rus. машина Тьюринга, f pranc. machine de Turing, f ryšiai: sinonimas – Tiuringo mašina … Automatikos terminų žodynas

«МАШИНА ТЬЮРИНГА» — абстрактная вычислит. машина, предполагающая максимально простую логич. структуру и наличие бесконечной внеш. памяти, напр., в виде неогранич. с обеих сторон ленты, раздел. на ячейки. Идея М. Т. была предложена англ. математиком А. М. Тьюрингом… … Большой энциклопедический политехнический словарь

Машина Тьюринга для умножения чисел — Машина Тьюринга (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча… … Википедия

машина Тьюринга с несколькими магнитными лентами — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN multitape Turing machine … Справочник технического переводчика

Детерминированная машина Тьюринга — Машина Тьюринга (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча… … Википедия

Недетерминированная машина Тьюринга — Машина Тьюринга Варианты машин Универсальная машина Тьюринга Квантовая машина Тьюринга en:Read only Turing machine en:Read only right moving Turing Machines Вероятностная машина Тьюринга Недетер … Википедия

Вероятностная машина Тьюринга — Машина Тьюринга Варианты машин Универсальная машина Тьюринга Квантовая машина Тьюринга en:Read only Turing machine en:Read only right moving Turing Machines Вероятностная машина Тьюринга Не … Википедия

Источник

Машина Тьюринга

Содержание

Машина Тьюринга (англ. Turing machine) — модель абстрактного вычислителя, предложенная британским математиком Аланом Тьюрингом в 1936 году. Эта модель позволила Тьюрингу доказать два утверждения. Первое — проблема останова неразрешима, т.е. не существует такой машины Тьюринга, которая способна определить, что другая произвольная машина Тьюринга на её ленте зациклится или прекратит работу. Второе — не существует такой машины Тьюринга, которая способна определить, что другая произвольная машина Тьюринга на её ленте когда-нибудь напечатает заданный символ. В этом же году был высказан тезис Чёрча-Тьюринга, который терминах теории рекурсии формулируется как точное описание интуитивного понятия вычислимости классом общерекурсивных функций. В этой формулировке часто упоминается как просто тезис Чёрча. В терминах вычислимости по Тьюрингу тезис гласит, что для любой алгоритмически вычислимой функции существует вычисляющая её значения машина Тьюринга. В виду того, что классы частично вычислимых по Тьюрингу и частично рекурсивных функций совпадают, утверждение объединяют в единый тезис Чёрча — Тьюринга.

Неформально машина Тьюринга определяется как устройство, состоящее из двух частей:

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

Определение [ править ]

Определение машины [ править ]

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

Определение процесса работы [ править ]

Особо следует рассмотреть случай переходов по пробельному символу:

Для машины Тьюринга, которая пишет символ [math]B[/math] на ленту также можно дать аналогичное формальное определение. Оно будет отличаться тем, что символы в строчках конфигурации могут содержать пробелы, и для того, чтобы эти строчки имекли конечную длину, нужно аккуратно учесть наличие пробелов при записи правил перехода.

Результат работы [ править ]

Примеры машин-распознавателей и машин-преобразователей будут даны ниже.

Примеры машин Тьюринга [ править ]

Прибавление единицы [ править ]

Для начала приведём пример машины-преобразователя, которая прибавляет единицу к числу, записанному на ленте в двоичной записи от младшего бита к старшему. Алгоритм следующий:

Проверка того, является ли слово палиндромом [ править ]

Варианты машины Тьюринга [ править ]

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

Многодорожечная машина Тьюринга [ править ]

Машина Тьюринга с полубесконечной лентой [ править ]

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

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

Затем перенумеруем ячейки, и запишем символ [math]c \in \Pi \setminus \Sigma, B[/math] в начало ленты, который будет означать границу рабочей зоны:

Начальное состояние новой машины Тьюринга устанавливается в одной или другой зоне в зависимости от того, в какой части исходной ленты располагалась головка считывания-записи в исходной конфигурации.[math]\triangleleft[/math]

Многоленточная машина Тьюринга [ править ]

Многоленточная машина с [math]n[/math] дорожками эмулируется многодорожечной машиной с [math]2n[/math] дорожками следующим образом: каждая нечётная дорожка соответствует ленте исходной машины, а на каждой чётной дорожке отмечены специальным символом [math]*[/math] позиция головки на ленте выше (считаем, что ленты нумеруются сверху вниз).

Каждый шаг исходной машины эмулируется конечной последовательностью шагов построенной машины следующим образом: исходно головка находится в позиции самой левой отметки и идёт вправо до самой правой отметки, запоминая прочитанные около символов [math]*[/math] символы в состоянии. Пройдя до самой правой отметки, головка возвращается влево, совершая необходимые действия (переписывая символы около отметок и передвигая сами отметки). После такого прохода головка переходит в следующее состояние, завершая эмуляцию шага.

Аланом Тьюрингом было сформулировано следующее утверждение:

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

Универсальная машина Тьюринга [ править ]

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

Источник

Машина Тьюринга — одно из самых важных открытий XX века

Тема: Наука

В 30-е годы XX века английский математик Алан Тьюринг придумал такое странное устройство, которое теперь называют машиной Тьюринга.

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

Факт №1

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

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

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

Факт №2

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

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

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

Факт №3

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

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

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

Факт №4

В 2000-м году был публично объявлен «список проблем следующего тысячелетия», за которые Институт Клея обещает миллион долларов.

Так вот, первая проблема в этом списке — это проблема перебора, и она там заслуженно. Интересно в теории сложности вычислений то, что не только наличие какого-то алгоритма полезно практически, но, как ни странно, часто бывает полезно отсутствие алгоритма.

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

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

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

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

Факт №5

Что такое случайность? Это дело тонкое, вообще, существует ли случайность? Когда в каком-нибудь казино играют в рулетку — может ли наука предсказать, что там выпадет, и как нужно играть, чтобы выиграть, или это в принципе невозможно?

Федор Михайлович Достоевский твердо верил, что если быть хладнокровным и не волноваться во время игры, то можно выиграть, — он говорил, что, к сожалению, ему не удаётся быть хладнокровным, и поэтому он всё время проигрывал.

С другой стороны, теория вероятностей основана на том, что такой системы не существует, что последовательность бросания монеты в какой-нибудь игре, или последовательность выпадения красного и черного в рулетке, случайны и непредсказуемы. Но возникает вопрос, что такое случайность? Как определить, что это значит? Можем ли мы отделить случайное от неслучайного?

Сейчас вы видите две последовательности:

Вам сказано, что одна из них получена бросанием монеты, а другая как-то иначе. Сможете ли вы определить, какая из них получена каким образом?

Я думаю, что сможете, и что более-менее всякий человек, который посмотрит на эту картинку, скажет, что первая последовательность получена не бросанием монеты, а просто чередованием 0 и 1, а вторая вполне может быть получена бросанием монеты.

Но спрашивается, в чём разница? Почему вы смотрите на эту картинку и уверены, что первая последовательность не может быть получена бросанием монеты? Почему монета не может выпасть сначала орлом, потом решкой, потом снова орлом… как это объяснить? Можно сказать так: вероятность того, что это случайно произойдет, очень мала, потому что такая последовательность всего одна, а всего последовательностей очень много. Но ведь то же самое можно сказать и про вторую последовательность, появление конкретно этой последовательности имеет ту же самую малую вероятность, что и для первой. Поэтому вопрос — в чём тут разница, чем первая последовательность «лучше» второй (менее случайна, чем вторая)?

Факт №6

Или другой парадоксальный пример. Представьте себе, как в XIX веке (это написано у Лотмана в его «Беседах о русской культуре») играли в карты. В отличие от нынешней ситуации, когда карты тасуют, тогда карты продавались уже перетасованными заранее.

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

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

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

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

Если, скажем, все карты идут в порядке возрастания их значения, или сначала идут все красные карты, а потом черные — такие комбинации, вроде бы, надо браковать. Но, с другой стороны, непонятно, чем они хуже других. Одной из попыток ответить на этот вопрос (60-е годы XX века) было понятие сложности, то, что сейчас называется колмогоровская сложность или алгоритмическая сложность.

Факт №7

Идея эта совсем простая — что первая из последовательностей

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

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

Можно сказать, что, если мы начнем «сжимать» последовательности каким-то архиватором, то вторая последовательность не сожмётся, а первая сожмется.

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

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

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

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

Если вы хотите получать больше статей, подобно этой, то кликните Recommend ниже.

Источник

• ← Нднд для лодки пвх что это
• К чему снятся насекомые во сне в большом количестве →