Математик Теренс Тао обогнал компьютер в решении проблемы несоответствия Эрдеша

Математик Теренс Тао обогнал компьютер в решении проблемы несоответствия Эрдеша

Математик Теренс Тао решил так называемую проблему несоответствия Пала Эрдеша. Предыдущее ее решение, полученное в течение шести часов компьютером, представляет собой файл объемом 13 гигабайт, что на три гигабайта больше, чем весь текстовый архив Wikipedia. Свои результаты исследований Тао опубликовал на сайте arXiv.org, а кратко с ними знакомит издание New Scientist.

Проблема несоответствия Эрдеша формулируется следующим образом. Пусть дана бесконечная последовательность, элементами которой выступают только числа -1 и +1. Из нее можно выделить подпоследовательность, содержащую конечное число таких элементов. Их сумма будет давать число, называемое несоответствием. Несоответствие определяет внутренние свойства подпоследовательности и исходной последовательности.

Эрдеш полагал, что у любой бесконечной последовательности, состоящей из -1 и +1, всегда найдется конечная подпоследовательность, несоответствие которой будет больше, чем любое выбранное число. Ученый не доказал свое утверждение, однако (как часто делал) в 1930 году предложил за него премию в 500 долларов.

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

Доказательство Тао из Калифорнийского университета в Лос-Анджелесе заняло 20 страниц текста (вместе с титульным листом и списком литературы). Аргументы математика использовали специального вида гипотезу Эллиота-Халберстама (о распределении простых чисел в арифметической прогрессии), а также данные, полученные в проекте Polymath5 — добровольного объединения ученых, которые с помощью технологий типа Wikipedia и блогов совместно работали над доказательством проблемы несоответствия.

Австралийский и американский математик Теренс Тао родился в 1975 году в городе Аделаида. В 24 года он стал самым молодым профессором Калифорнийского университета в Лос-Анджелесе. В 2006 году на 25-м Международном конгрессе математиков в Мадриде Тао стал лауреатом Филдсовской премии, а в 2014 году — «Премии за прорыв в математике» Юрия Мильнера, Марка Цукерберга и Сергея Брина.

Lenta.ru

Похожие новости:
Математик вычислил "траекторию жизни" при помощи Facebook
Facebook  может быть прекрасным источником для получения самых разнообразных статистических данных. Новое исследование известного математика показало, что при помощи соцсети можно вычислить, каким образом у людей со временем меняются интересы, предпочтения в общении и многое другое.  Известный математик ..
2013-04-27 1164 0 Разное, интересное
0
Великобритания разрешила редактировать геном человеческих эмбрионов
Министерство здравоохранения Великобритании выдало первое разрешение на редактирование генома эмбрионов человека в исследовательских целях. Его получит исследовательская группа из Института Френсиса Крика под руководством биолога Кети Никен (Kathy Niakan). Великобритания, таким образом, станет второй страной в мире, где разрешены подобные процедуры — в апреле прошлого года стало ..
2016-02-02 1097 0 Разное, интересное
0
Насколько умён искусственный интеллект?
...Как выясняется, пока не слишком: экспериментальная компьютерная система ConceptNet 4 по «умственным» способностям может сравниться разве что с четырёхлетним ребёнком. Как далеко зашли технологии развития искусственного интеллекта (ИИ)? Задавшись этим вопросом, специалисты из Иллинойсского университета в Чикаго (США), ..
2013-07-17 1302 0 Разное, интересное
0
В Стэнфордском университете создают живой компьютер
Американцы решили совместить технологии и медицину в одном компьютере. Они работают над электронным устройством на основе ДНК живых организмов. Первая деталь уже готова - биологический транзистор. По словам ученых, он работает гораздо лучше, чем электронные аналоги. Созданный элемент являет собой воплощение нано-технологического ..
2013-03-30 1283 0 Разное, интересное
0
Для колонизаторов Марса уже разработано iOS-приложение
Студенты Томского госуниверситета разработали приложение для будущих колонизаторов Марса. «В приложении в популярной и местами веселой форме поданы основные аспекты проблемы этого мероприятия», — рассказал технический руководитель группы студентов Василий Вершинин. По его словам, кроме ..
2013-12-5 1064 0 Разное, интересное
0
Существование того света с позиций квантовой механики
Так, может быть, и в самом деле, помимо видимого всем нам мира, существует какой-то иной- Тот, в котором обитают души, покинувшие тела- Ученные сделали открытие о физических процессах, связанных с перемещениями душ. Не счесть свидетельств людей, переживших ..
2015-07-16 7782 0 Разное, интересное
0
Ученые: воспоминания могут изменить судьбу
Воспоминания отражают прошлое, помогают предвидеть будущее. Ученые выяснили, что человеческие мозг, чтобы получить новые знания, соотносит полученную информацию с жизненным опытом. Исследования, результаты которых опубликованы в журнале Neuron, показали, что процесс осмысления информации помогает людям ..
2012-07-23 2381 0 Разное, интересное
0
Искусственный интеллект ещё не изобретён, но им уже пугают
Как говорил один мудрец, трудно искать чёрную кошку в тёмной комнате, особенно если её там нет. То же с искусственным интеллектом — сложно составить представление о том, чего ещё не существует. Кинематограф и литература успешно справляются со своими задачами по формированию у зрителей и читателей ..
2015-07-05 4307 0 Разное, интересное
1
Будущее глазами футуролога из Google. Бессмертие – только начало
Американский футуролог и технический директор Google Рэй Курцвейл знаменит во всем мире. Популярность ему принесли книги, посвященные будущему технологий и человечества. Он доказал, что человеческий прогресс стремительно пошел вверх с появлением технологий распознавания речи.И вот новое сенсационное заявление Рэймонда Курцвейля ..
2016-04-11 1907 0 Разное, интересное
0
Энергия силы духа
Сам того не желая, я стал участником интереснейшего исследования. Энергетическая компания Repsol пригласила меня принять участие в цикле лекций по теме энергии. Эксперты в области физики и химии утверждают, что энергия – это способность осуществлять работу, а работа – это сила, ..
2013-05-29 1568 0 Разное, интересное
0
Стивен Хокинг перечислил источники вдохновения
Британский физик-теоретик Стивен Хокинг, отвечая на вопросы поклонников, рассказал о вдохновении, благодаря которому он сумел прожить интересную жизнь. Об этом ученый сообщил в первой части радиопередачи на BBC Radio 4, посвященной исследованиям черных дыр.Один из слушателей радиопередачи, 17-летний Дункан ..
2016-01-27 1251 0 Разное, интересное
-1
Объяснено отсутствие во Вселенной самовоспроизводящихся машин
Биофизик Алекс Коувалд из Ньюкаслского университета (Великобритания) объяснил причину, по которой Вселенная не может быть заполнена зондами фон Неймана — самовоспроизводящимися машинами, которые самостоятельно распространяются, размножаются и эволюционируют по мере освоения ими окружающего пространства. Посвященный этому исследованию препринт ..
2016-05-16 1371 0 Разное, интересное
0
Фотографу пересадили вместо глаза камеру
Таня Влач, фотограф из Сан-Франциско. Она лишилась левого глаза в автокатастрофе. И теперь решилась на уникальную операцию, когда вместо потерянного глаза ей будет встроена мини-кинокамера... Операция стоит 15000 долларов. Новое устройство позволит Тане записывать самые интересные ..
2012-06-26 1567 0 Разное, интересное
0
Компьютерный сбой помог Deep Blue победить Каспарова
В 1997 году Гарри Каспаров проиграл шахматный матч компьютеру Deep Blue. В первой партии матча компьютер сделал ход, который вывел Каспарова из равновесия и заставил экспертов говорить о скрытой силе искусственного интеллекта. Поражение Каспарова навсегда ..
2012-10-5 1219 0 Разное, интересное
0
Искусственный интеллект: реальность или будущее?
На протяжении многих тысячелетий человек пытался определить, как он думает, какие процесс происходят у него в голове. Так и в сфере искусственного интеллекта (ИИ) ученым предстоит решить еще более сложную задачу. Ведь в данной области специалистам предстоит не только понять сущность ..
2012-10-16 3073 0 Разное, интересное
0