Тьюринг это что такое простыми словами
Значение слова тьюринг
тьюринг в словаре кроссвордиста
тьюринг
Энциклопедический словарь, 1998 г.
ТЬЮРИНГ (Turing) Алан Матисон (1912-1954) английский математик. Основные труды по математической логике, вычислительной математике. В 1936-37 ввел математическое понятие абстрактного эквивалента алгоритма, или вычислимой функции, получившее затем название «машины Тьюринга».
Большая Советская Энциклопедия
Имена, названия, словосочетания и фразы содержащие «тьюринг»:
Примеры употребления слова тьюринг в литературе.
Такое же доказательство лежит в основе современной теории вычисления, разработанной Аланом Тьюрингом и другими в 1930-х годах.
Теперь он знал все о третьей проблеме Гильберта, об уравнении Фредгольма, о машине Тьюринга, о марковских процессах, о постулатах, леммах и теоремах Евклида, Ферма, Коши, Гаусса, Вейерштрасса, Декарта, Абеля, Кантора, Галуа, Римана, Лобачевского и десятков других великих математиков!
Все присутствующие зааплодировали ему и решили: построим Большой Генеральный Автомат Тьюринга, будем всемогущими и никто в мире не сможет противостоять нам.
Тьюринг все равно мог бы его взломать, но Тьюринг в Англии, к тому же он на стороне Уотерхауза и не выдаст.
Нужен был способ дать машине память, чтобы она могла, в терминологии Тьюринга, быстро зарывать данные и так же быстро их выкапывать Это я и сделал.
Таким образом, универсальное вычисление не просто возможно, как этого требовал принцип Тьюринга, оно также является легкообрабатываемым.
Рэнди вспоминает фотографию деда с Тьюрингом и фон Хакльгебером в Принстоне, где, вероятно, все трое возились с дзета функцией.
Объяснение должно включать квантовую физику, принцип Тьюринга и, как отмечал сам Поппер, теорию эволюции.
Если принцип Тьюринга является физическим законом, что я доказал, значит, мы не должны удивляться, обнаружив, что можем создавать точные теории о реальности, потому что это просто виртуальная реальность в действии.
Но вы боитесь, что если мы не сможем доказать принцип Тьюринга, то опять потеряем оправдание того, что полагаемся на научные предсказания?
Жизнь состоит в физической реализации знания, а в главе б мы встречали закон физики, принцип Тьюринга, который также заключается в физической реализации знания.
Источник: библиотека Максима Мошкова
Транслитерация: t’yuring
Задом наперед читается как: гнирюьт
Тьюринг состоит из 7 букв
ТЬЮРИНГ
Полезное
Смотреть что такое «ТЬЮРИНГ» в других словарях:
Тьюринг — Тьюринг, Алан Матисон Алан Тьюринг Alan Mathison Turing Памятник в Сэквиль Парке Дата рождения … Википедия
ТЬЮРИНГ — (Turing) Алан (1912 54), английский математик и логик, который сформулировал теории, ставшие впоследствии основой компьютерной техники. В 1937 г. придумал машину Тьюринга гипотетическую машину, способную преобразовывать набор вводимых команд. Она … Научно-технический энциклопедический словарь
ТЬЮРИНГ — (Turing) Алан Матисон (1912 54), английский математик. В 1936 1937 ввел математическое понятие абстрактного эквивалента алгоритма, или вычислимой функции, получившее затем название машина Тьюринга … Современная энциклопедия
Тьюринг А. — Тьюринг А. Английский математик. [http://www.rfcmd.ru/glossword/1.8/index.php?a=index&d=4889] Тематики защита информации EN Turing … Справочник технического переводчика
Тьюринг А. М. — Алан Тьюринг Alan Turing Памятник в Сэквиль Парке Дата рождения: 23 июня 1912 Место рождения: Лондон, Англия Дата смерти: 7 июня 1954 … Википедия
Тьюринг А. — Алан Тьюринг Alan Turing Памятник в Сэквиль Парке Дата рождения: 23 июня 1912 Место рождения: Лондон, Англия Дата смерти: 7 июня 1954 … Википедия
Тьюринг — (Turing) Алан Матисон (23.6.1912, Лондон, 7.6.1954, Уилмслоу, близ Манчестера), английский математик. Член Королевского общества (1951). По окончании Кембриджского университета (1935) работал над докторской диссертацией в Принстонском… … Большая советская энциклопедия
Тьюринг А. М. — ТЬЮ́РИНГ (Turing) Алан Матисон (191254), англ. математик. Осн. тр. по матем. логике, вычислит. математике. В 193637 ввёл матем. понятие абстрактного эквивалента алгоритма, или вычислимой функции, получившее затем назв. машина Т … Биографический словарь
ТЬЮРИНГ Алан — (полн. Алан Матисон Тьюринг, Alan Mathison Turing) (23 июня 1912, Лондон 7 июня 1954, Уилмслоу, Великобритания), британский математик, автор трудов по математической логике, вычислительной математике. В 1936 1937 годах ввел математическое понятие … Энциклопедический словарь
Тьюринг
Смотреть что такое «Тьюринг» в других словарях:
Тьюринг — Тьюринг, Алан Матисон Алан Тьюринг Alan Mathison Turing Памятник в Сэквиль Парке Дата рождения … Википедия
ТЬЮРИНГ — (Turing) Алан (1912 54), английский математик и логик, который сформулировал теории, ставшие впоследствии основой компьютерной техники. В 1937 г. придумал машину Тьюринга гипотетическую машину, способную преобразовывать набор вводимых команд. Она … Научно-технический энциклопедический словарь
ТЬЮРИНГ — (Turing) Алан Матисон (1912 54), английский математик. В 1936 1937 ввел математическое понятие абстрактного эквивалента алгоритма, или вычислимой функции, получившее затем название машина Тьюринга … Современная энциклопедия
ТЬЮРИНГ — (Turing), Алан Матисон (23 июня 1912 – 7 июня 1954) – англ. логик и математик. В 1936–37 предложил идеализированную машинную модель вычислит. процесса – вычислительную схему, близкую к действиям человека, производящего вычисления, и выдвинул… … Философская энциклопедия
Тьюринг А. — Тьюринг А. Английский математик. [http://www.rfcmd.ru/glossword/1.8/index.php?a=index&d=4889] Тематики защита информации EN Turing … Справочник технического переводчика
Тьюринг А. М. — Алан Тьюринг Alan Turing Памятник в Сэквиль Парке Дата рождения: 23 июня 1912 Место рождения: Лондон, Англия Дата смерти: 7 июня 1954 … Википедия
Тьюринг А. — Алан Тьюринг Alan Turing Памятник в Сэквиль Парке Дата рождения: 23 июня 1912 Место рождения: Лондон, Англия Дата смерти: 7 июня 1954 … Википедия
Тьюринг А. М. — ТЬЮ́РИНГ (Turing) Алан Матисон (191254), англ. математик. Осн. тр. по матем. логике, вычислит. математике. В 193637 ввёл матем. понятие абстрактного эквивалента алгоритма, или вычислимой функции, получившее затем назв. машина Т … Биографический словарь
ТЬЮРИНГ Алан — (полн. Алан Матисон Тьюринг, Alan Mathison Turing) (23 июня 1912, Лондон 7 июня 1954, Уилмслоу, Великобритания), британский математик, автор трудов по математической логике, вычислительной математике. В 1936 1937 годах ввел математическое понятие … Энциклопедический словарь
Идеи и концепции Алана Тьюринга
Странность или гениальность? Зачастую оба утверждения верны, если речь идет о незаурядном человеке. Таковым был Алан Тьюринг, английский математик и взломщик немецких радиограмм во время Второй мировой войны.
Он не любил скучных людей и шутки. Уходя с работы, приковывал цепью свою любимую кружку к батарее, чтоб не украли. Мог одеться, как бродяга, или прийти в гости посреди ночи без предупреждения. Никогда не лебезил перед элитой и был честен до глубины души.
Тьюринга называют отцом информатики, первым хакером и жертвой гомофобии. Статья повествует о гениальном математике и криптографе Алане Тьюринге.
Выдающийся математик родился в 1912 году. Юный Тьюринг был исследователем. Пока сверстники беззаботно играли, Тьюринг наблюдал, как растут цветы во дворе. Его интересовала природа самой жизни. В 10 лет он поставил первый опыт в домашних условиях, пытаясь извлечь йод из водорослей. Родители в воспитании сына не участвовали. Мальчик вырос в интернате.
В 14 лет Тьюринг увлекся точными науками. Его комментарии к теории относительности Эйнштейна поражали зрелостью мысли. Но самой большой страстью стали шахматы. Остальные предметы казались Тьюрингу бесполезными, за что классный руководитель назвал будущего гения «проблемой школы и всего общества».
Чудаком Тьюринга считали и в Кембридже. Он ездил на сломанном велосипеде в противогазе, таким образом спасаясь от аллергии на цветочную пыльцу. Не любил «нудных» разговоров, и мог запросто встать и уйти прямо во время беседы.
Машина Тьюринга
В 24 года Алан Тьюринг создал теорию логических вычисляющих машин, которая вписала его имя в историю. В литературе по математике сокращение ТМ (Turing machine, машина Тьюринга) часто даже не поясняют, настолько оно общепринято.
Идея Тьюринга заключалась в создании программы, хранимой в памяти некой универсальной машины, которая умеет решать любые задачи.
Конечно, машиной как таковой, модель Тьюринга не являлась. Это было условное устройство, по писанию и способу функционирования похожее на вычислительную машину. Его память, а точнее запоминающая лента, была бесконечной, чем не может похвастаться ни один современный компьютер. Можно сказать, что в 30-х годах прошлого века Тьюринг придумал сверхкомпьютер.
Абстрактная машина Тьюринга состояла из трех частей:
По задумке Тьюринга, «головка» должна двигаться вдоль ленты по заданной программе. То есть выполнять команды пользователя. Поочередно считывать либо записывать символы в ячейках до тех пор, пока задание не будет выполнено. Таким образом, Тьюринг хотел показать, что любая задача может быть решена последовательным выполнением операций. То есть шаг за шагом.
Машина Тьюринга демонстрировала главную идею создания компьютерной программы: ее построение должно быть основано на алгоритме – поэтапном исполнении инструкций.
Любое современное устройство, будь то стиральная машина, телевизор или смартфон, работает благодаря концепции, разработанной Тьюрингом.
Расшифровка «загадки» нацистов
В 1938 году Тьюринг блестяще защитил докторскую диссертацию в Принстонском университете – Мекке научного мира. Наконец, его гениальность признали. Там он занимался не только математикой, но и криптографией.
В 1939 году, на третий день после начала Второй мировой войны, военное ведомство Британии поставило перед Тьюрингом задачу: взломать коды «Энигмы» – немецкой машины для шифровки радиограмм. Была создана секретная аналитическая группа под руководством выдающегося математика.
Поставленная задача казалась невыполнимой. «Энигма» (в переводе с немецкого «загадка») преобразовывала предложения в набор букв, лишенный, на первый взгляд, всякого смысла. Однако Тьюринг смог разгадать «загадку». Он переключил машину на обратный режим работы и взломал шифр. Позже на основе этого принципа был создан дешифровочный аппарат под названием «Криптографическая бомба». Такое название он получил из-за характерного звука часового механизма при работе.
Первая оцифровка голоса
Во время войны Тьюринг был направлен военным ведомством в США. Целью поездки было изучение американской системы кодирования голоса SIGSALY, которая использовалась для телефонной связи президентов Уинстона Черчилля и Франклина Рузвельта.
Тьюринг был восхищен работой криптографов США. Однако сложность и чрезмерная монументальность шифровальной системы казалась Тьюрингу неуместной. Вернувшись на родину, математик в очередной раз продемонстрировал прекрасные навыки упрощения. Он создал первый аппарат по оцифровке голоса под названием Delilah.
Уникальность системы была в том, что Тьюринг смог объединить в один блок режимы шифрования и дешифрования, переход между которыми осуществлялся при помощи переключателя. Он стремился использовать только самые необходимые детали для работы устройства. Поэтому Delilah получилась компактной и оригинальной по дизайну.
Для проверки работы Delilah Тьюринг использовал речь Уинстона Черчилля «Наше величайшее усилие грядет», переданную по радио Лондона 26 марта 1944 года.
Помимо кодирования и декодирования голоса Delilah умела шифровать факсимиле.
До конца войны Алан Тьюринг оставался главным консультантом проекта по дешифровке секретных сообщений противника. В 1945 году его наградили орденом кавалера Британской империи.
Пионер электронной музыки
Есть мнение, что первый компьютер, который смог воспроизвести музыку, находится в Австралийском Сиднее. Но это не более чем миф. Первые звуки электронной музыки родились в лаборатории Тьюринга.
Воспроизвести ноты удалось при помощи гигантского компьютера, который занимал целый этаж Лаборатории вычислительных машин. В процессе работы компьютер издавал периодические короткие звуковые импульсы. Тьюринг прислушался и заметил, что если повторять звуковые импульсы по определенной схеме, то человеческое ухо услышит музыкальные ноты.
Каждому процессу в работе компьютера математик присвоил определенную ноту: одну для операции «работа выполнена», другую для команды «переполнение цифр в памяти», третью для сообщения «ошибка». Можно догадаться, что первая «мелодия» была похожа на какофонию. Тьюринг называл этот процесс «слушаньем» компьютера.
Спрограммировать первую музыкальную композицию Тьюринг поручил талантливому пианисту и ученому Кристоферу Стрейчи. Сеанс программирования длился всю ночь. Утром гигантский компьютер хрипло спел Государственной гимн Великобритании. Тьюринг оценил работу Стрейчи фразой «Хорошее шоу».
Тест Тьюринга: беседы с компьютером
Появление в середине XX века первых вычислительных машин породило идею о создании искусственного интеллекта (ИИ). Ученые задались вопросом: каким критериям должен соответствовать ИИ? Алан Тьюринг взялся ответить на этот вопрос.
Он придумал тест. Идея теста проста: человек должен пообщаться с несколькими собеседниками за ширмой, среди которых есть робот. Если человеку не удается понять, что он общается с роботом, то можно утверждать: ИИ создан. Тьюринг предположил, что в начале XXI века машина сможет за 5 минут убедить 30% судей, что те ведут беседу с живым человеком, а не с роботом.
Тест был создан в 1950 году, но активных попыток его пройти не предпринималось.
Лишь в 90-х годах появились желающие пройти тест Тьюринга. Программисты из разных стран пытались создать бота, общение с которым неотличимо от человеческого. В 2014 году это удалось разработчикам из России. Программа «Евгений Густман» была признана первым виртуальным собеседником, прошедшим тест Тьюринга.
На основе теста Тьюринга создана современная CAPTCHA («капча») – программа-тест, цель которой – определить, кто взаимодействует с системой: человек или робот. Каждый пользователь Интернета хоть раз встречал «капчу» на просторах Сети.
Например, вас просили ввести символы с картинки, выполнить сложение простых чисел или из 9 фото выбрать те, где изображен пешеходный переход. Эти шарады и есть «капча». Человек справится с ними без труда, а вот робот «забуксует». Задача «капчи» – не допустить на сайт ботов, созданных для взлома, рассылки спама и прочих вредных действий.
Почему корова пятнистая?
А почему зебра полосатая? Откуда у бабочек узор на крыльях? Удивительно, но ответить на эти вопросы мы можем благодаря взломщику кодов, математику Алану Тьюрингу. В 1952 году при помощи математических формул он смог объяснить характерный окрас животных.
Тьюринг предположил, что в коже присутствуют два химических элемента. Один запускает процесс пигментации, а второй останавливает его. Математик использовал уравнения, чтобы описать различные способы взаимодействия этих химических элементов, приводящие к образованию пятен и полос на коже.
Тьюринг высказал идею о связи живого и неживого через химическую реакцию. Впоследствии эта идея была подтверждена. Спустя полвека ученые опытным путем смогли доказать существование структур Тьюринга и подтвердить предположения математика.
В живой природе структуры Тьюринга проявляются в виде полос на шкуре зебр и тигров, чешуе рыб, в форме пятен на коже коров, гепардов и жирафов. Некоторые ученые считают, что причудливую форму человеческого мозга и позвоночника тоже можно считать структурами Тьюринга.
Запретный плод
В феврале 1952 года квартиру Алана Тьюринга ограбили. Это событие оказалось роковым в биографии великого математика. Грабитель оставил записку, в которой пригрозил Тьюрингу опасными последствиями, если тот обратится в полицию. Так и произошло. Полиция вместо того, чтобы расследовать преступление, обвинила Тьюринга в оскорблении общественной нравственности. Поскольку грабителем оказался его любовник.
Тьюринг не отрицал своей гомосексуальности. Суд предоставил ему нечеловеческий выбор: тюремное заключение либо гормональную терапию эстрогенами. Тьюринг выбрал последнее.
Его отстранили от секретной работы и преподавательской деятельности. Служба безопасности Англии завела на него дело. Подавленный Тьюринг, чье здоровье и карьера были разрушены, бежал в Европу.
«Его убило государство, которое он спас» – так отзывался о смерти Тьюринга его друг.
В 2013 году Алан Тьюринг был посмертно реабилитирован. Его именем назван закон в Великобритании, по которому предоставляется помилование мужчинам, осужденным в период 1885-1967 гг. по обвинению в гомосексуальности.
Алан Тьюринг не боялся давать ход своим идеям. Он задавался вопросом: если предположить, что эксперимент удастся, что я могу сделать уже сегодня для успеха? Друзья, следуйте примеру великого математика. Пусть ваши идеи обретают реальную форму. Не пасуйте перед трудностями и скепсисом окружающих. И будьте терпимы к тем, кто не похож на вас.
Машина Тьюринга — одно из самых важных открытий XX века
Тема: Наука
В 30-е годы XX века английский математик Алан Тьюринг придумал такое странное устройство, которое теперь называют машиной Тьюринга.
Идея его была в том, чтобы придумать устройство, абстрактную машину, которая может делать все, что вообще могут делать машины. Он был не единственным в этот момент, другие люди тоже в других терминах определяли похожие вещи, но в гораздо более абстрактных терминах, по крайней мере, в их работах конкретного механизма работы машины не было.
Факт №1
Оказалось же, что это одно из самых важных открытий XX века. То, что сейчас в разных устройствах — скажем, в телевизоре и в стиральной машине, — может использоваться одна и та же микросхема процессора, — это воплощение одной из идей Тьюринга.
И то, что одна и та же программа может использоваться в самых разных компьютерах, работать с самой разной аппаратурой и выглядеть одинаково, это тоже его идея. Тогда это называлось идеей хранимой программы (программа хранится в памяти и определяет поведение машины), и ещё была идея универсальной машины, — есть машина, которая может делать все, что может делать любая другая машина.
Если бы не Тьюринг, наверно, это придумал бы кто-то другой, он не был единственным, кто над этим работал, но так или иначе такое абстрактное теоретическое устройство оказалось одним из самых важных изобретений в XX веке.
Факт №2
Интересно, что потом Тьюринг, когда настали трудные времена, не только занимался теорией, но и практически участвовал в разных важных проектах.
Он с коллегами расшифровал коды немецкой армии — это известная история. Там использовались шифровальные машины «Энигма», которые пытались расшифровать сначала польские криптографы, а потом английские — при активном участии Тьюринга, и им это удалось.
А после войны Тьюринг уже строил реальную электронную вычислительную машину. Хотя прямой связи с его теоретическими работами не было, но явно это было продолжением той же самой деятельности. Так что хорошая теория — вещь очень практичная, и не надо бояться того, что теоретические работы окажутся бесполезными.
Факт №3
Сейчас это большая наука, которая называется теория сложности вычислений, в ней много всего интересного открыли, но есть самая главная проблема, которая называется проблема перебора, и которая до сих пор не решена.
Ее можно объяснить на таком примере: выпускалась игрушка Eternity — это такая коробочка, в которую уложены плитки, раскрашенные в разные цвета, но они раскрашены так, что видно, какие плитки можно прикладывать друг к другу (там рисунок на краях). Продаются они рассыпанными, и фирма, которая их изготовила, утверждает, что все это можно собрать в одну картинку внутри этой квадратной коробки (там 256 плиток) — то есть что изначально это была одна картинка, разрезанная на плитки.
По современным представлениям, машины такие задачи за обозримое время решать не могут, никакого способа, кроме как перебирать все варианты (а их очень много) сейчас не известно. Но, с другой стороны, никто этого не может и доказать. Это и называется проблемой перебора — доказать, что такой полный перебор каких-то объектов нельзя заменить никаким более коротким вычислением.
Факт №4
В 2000-м году был публично объявлен «список проблем следующего тысячелетия», за которые Институт Клея обещает миллион долларов.
Так вот, первая проблема в этом списке — это проблема перебора, и она там заслуженно. Интересно в теории сложности вычислений то, что не только наличие какого-то алгоритма полезно практически, но, как ни странно, часто бывает полезно отсутствие алгоритма.
Например, есть такой известный вопрос о разложении чисел на множители. Если число небольшое, то легко проверить, что оно простое — можно проверить все меньшие числа, и понять, что там нет делителей. Если число большое, то так просто уже нельзя проверить — но существуют разные алгоритмы, которые позволяют это делать. (Они основаны на малой теореме Ферма и её усовершенствованиях, но это отдельная тема.)
Так или иначе, алгоритмы проверки простоты существуют. А теперь другая задача: возьмём два больших простых числа и их перемножим, сообщим, что у нас получилось, и спросим, какие это были числа. Это задача разложения на множители, и никто не знает, как это быстро сделать. И то, что этого никто не знает, очень хорошо, потому что благодаря этому существует вся вычислительная криптография, это одно из основных её предположений.
Когда кто-нибудь снимает деньги в банке, или в Интернете заходит на сайт с помощью SSL — используются системы криптографии, основанные на том, что быстро разлагать на множители числа нельзя. Если кто-нибудь в какой-то момент обнаружит, что разлагать можно, то, думаю, после этого будет экономический кризис, потому что вся банковская система рухнет, пока люди не заменят это чем-то другим (вообще без использования компьютеров или с какими-то новыми алгоритмами).
Так что отсутствие алгоритма может быть полезнее, чем его наличие. К сожалению, никто не может доказать, что алгоритма нет, хотя все подозревают, что это так — не решена ни общая проблема перебора, ни этот частный ее случай (разложение чисел на множители), особенно важный, и про него тоже все думают, но никто ничего не придумал.
Факт №5
Что такое случайность? Это дело тонкое, вообще, существует ли случайность? Когда в каком-нибудь казино играют в рулетку — может ли наука предсказать, что там выпадет, и как нужно играть, чтобы выиграть, или это в принципе невозможно?
Федор Михайлович Достоевский твердо верил, что если быть хладнокровным и не волноваться во время игры, то можно выиграть, — он говорил, что, к сожалению, ему не удаётся быть хладнокровным, и поэтому он всё время проигрывал.
С другой стороны, теория вероятностей основана на том, что такой системы не существует, что последовательность бросания монеты в какой-нибудь игре, или последовательность выпадения красного и черного в рулетке, случайны и непредсказуемы. Но возникает вопрос, что такое случайность? Как определить, что это значит? Можем ли мы отделить случайное от неслучайного?
Сейчас вы видите две последовательности:
Вам сказано, что одна из них получена бросанием монеты, а другая как-то иначе. Сможете ли вы определить, какая из них получена каким образом?
Я думаю, что сможете, и что более-менее всякий человек, который посмотрит на эту картинку, скажет, что первая последовательность получена не бросанием монеты, а просто чередованием 0 и 1, а вторая вполне может быть получена бросанием монеты.
Но спрашивается, в чём разница? Почему вы смотрите на эту картинку и уверены, что первая последовательность не может быть получена бросанием монеты? Почему монета не может выпасть сначала орлом, потом решкой, потом снова орлом… как это объяснить? Можно сказать так: вероятность того, что это случайно произойдет, очень мала, потому что такая последовательность всего одна, а всего последовательностей очень много. Но ведь то же самое можно сказать и про вторую последовательность, появление конкретно этой последовательности имеет ту же самую малую вероятность, что и для первой. Поэтому вопрос — в чём тут разница, чем первая последовательность «лучше» второй (менее случайна, чем вторая)?
Факт №6
Или другой парадоксальный пример. Представьте себе, как в XIX веке (это написано у Лотмана в его «Беседах о русской культуре») играли в карты. В отличие от нынешней ситуации, когда карты тасуют, тогда карты продавались уже перетасованными заранее.
Поэтому дворяне, которые играли в серьезные игры, каждый раз брали новую колоду и играли с ней. После этого она выбрасывалась и поступала, как пишет Лотман, в распоряжение слуг, которые играли в своего «подкидного дурака».
Так вот, представим себе, что есть фабрика, которая выпускает такие перетасованные колоды и есть машина, которая печатает карты, а есть, которая их тасует — эта машина их как-то внутри себя тасует, потом выкладывает, запаковывает, и они поступают в продажу. Теперь представим себе, что на этой фабрике есть, как говорили в советское время, «отдел технического контроля», который должен проверять, хорошо ли они перетасованы.
Время от времени он из пачки сделанных колод достаёт одну колоду, распаковывает и смотрит, хорошо ли она перетасована. С одной стороны, он должен что-то контролировать, то есть если он никогда никакие колоды не будет браковать как негодные, то зачем он вообще нужен? А с другой стороны, непонятно, что он может контролировать, потому что вся идея того, что карты хорошо перетасованы, состоит в том, что все варианты, все возможные последовательности карт в колоде, имеют совершенно одинаковую вероятность.
Соответственно, ни одна из них, с точки зрения тасовальной машины, не лучше другой. Почему же мы некоторые колоды (некоторые последовательности карт) бракуем, а некоторые оставляем? Это как-то загадочно.
Если, скажем, все карты идут в порядке возрастания их значения, или сначала идут все красные карты, а потом черные — такие комбинации, вроде бы, надо браковать. Но, с другой стороны, непонятно, чем они хуже других. Одной из попыток ответить на этот вопрос (60-е годы XX века) было понятие сложности, то, что сейчас называется колмогоровская сложность или алгоритмическая сложность.
Факт №7
Идея эта совсем простая — что первая из последовательностей
потому выглядит неслучайной, что она проста. «Проста» значит, что существует очень короткий способ объяснить, как она устроена — сказать, что там нули и единицы чередуются. В нашем примере такая разница, может, не сильно заметна — но если там будет тысяча чередующихся нулей и единиц, то ясно, что короче это объяснить словами, чем выписывать всю последовательность.
А для настоящей случайной монеты (как считается в рамках этого объяснения случайности) — никакого способа описать последовательность более коротким способом, чем показав просто все нули и единицы, как они есть, не существует.
Можно сказать, что, если мы начнем «сжимать» последовательности каким-то архиватором, то вторая последовательность не сожмётся, а первая сожмется.
В этом и состоит основная идея Колмогорова и его коллег, которые придумали, что сложность последовательности — это длина кратчайшей программы, которая такую последовательность может напечатать, а случайные последовательности отличаются от неслучайных тем, что нельзя их напечатать никакой программой, которая короче, чем сама последовательность.
Теперь целая наука на эту тему возникла, она называется алгоритмическая теория информации, алгоритмическая случайность, но, конечно, многие вопросы там еще не ясны. Не ясен вопрос о том, что можно сделать с ограничением на сложность вычислений.
Возможно, что последовательность на самом деле неслучайна и имеет какое-то короткое описание, но мы его просто не знаем и не можем найти — или проблема может быть не в том, что мы его не можем найти, а в том, что для того, чтобы восстановить последовательность по этому описанию, нужно очень много времени.
Вот это такая активно развивающаяся и, к сожалению, ещё не очень развитая область, и там, может быть, что-нибудь интересное в ближайшее время (или не в ближайшее время) откроют.
Если вы хотите получать больше статей, подобно этой, то кликните Recommend ниже.