Двадцатилетний студент решил задачу о машине Тьюринга
25 октября 2007 года, 14:53
Текст: Владимир Парамонов
Двадцатилетний британский студент Алекс Смит из Бирмингемского университета решил сложную математическую задачу, доказав, что машина Тьюринга с двумя состояниями каретки и алфавитом из трех символов является универсальной.
Машина Тьюринга, представляющая собой абстрактный исполнитель, была предложена британским математиком Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. В состав машины Тьюринга входит бесконечная в обе стороны лента, разделенная на ячейки, и управляющее устройство (каретка), способное находиться в одном из состояний, число которых точно определено. Каретка может перемещаться влево и вправо по ленте, читать и записывать в ячейки символы некоторого конечного алфавита. При этом управляющее устройство работает в соответствии с набором правил, которые предписывают каретке переместиться на одну клетку, записать символ и т.д. Универсальной называют такую машину Тьюринга, которая может заменить собой любую другую машину Тьюринга.
Весной нынешнего года известный американский математик Стивен Вольфрам предложил желающим доказать или опровергнуть предположение о том, что машина Тьюринга с двумя состояниями каретки, набором правил и алфавитом из трех символов является универсальной. В качестве приза за решение задачи Вольфрам учредил денежное вознаграждение в размере 25 тысяч долларов США.
Как теперь сообщает ArsTechnica, первым с поставленной задачей справился Алекс Смит, которому удалось доказать, что предложенная Вольфрамом машина Тьюринга действительно является универсальной. С изысканиями Смита можно ознакомиться здесь (файл в формате PDF).
http://science.compulenta.ru/337135/
Последние аномальные новости

Жители острова Пасхи посещали Южную Америку

Загадка образования первых галактик

Загадочный проект 'Синий луч' в действии

Замаскированный НЛО замечен над Португалией

Изучение экзотических звездных явлений

Космический телескоп распутал историю нашей галактики

Марсианский вертолет мог бы стать бортовым геологом

НЛО замечен над Южной Африкой

НЛО летают над атомными электростанциями Индии

Новый троянский астероид нашли на орбите Марса

Обнаружены четыре новых экзотических белых карлика

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

Сверхмассивная черная дыра не оправдывает ожиданий

Секреты пояса Ван Аллена раскрыты

Стареющие коричневые карлики становятся одинокими

Таинственный свет в небе над Сан-Антонио

Темная материи поможет понять эволюцию галактик

Уфологи могут научить нас политической паранойе

Элитные коммандос захватили НЛО

Японский летчик-истребитель рассказал о НЛО

Бигфут и сасквоч - инопланетные гибриды

Выявили лучшие места в США для обнаружения НЛО

Инопланетяне дали нам план Стоунхенджа

Инопланетяне используют невероятные технологии

Культурная площадь в Розуэлле примет уфо-фестиваль

НЛО вблизи ядерных установок ставят экспертов в тупик

НЛО замечен над поверхностью Луны

Оборона землян будет быстро подавлена инопланетянами

Общественный колледж Портленда предлагает курс по НЛО

Одна из дюжины звезд поедает свои планеты

Официальные лица США ничего не знают о НЛО

Планетологи пытаются оценить толщину льда на Европе

Поиски обломков рейса MH370 дали новую надежду

Пришло время изучить лунные лавовые трубки

Самые паранормальные места в Нью–Йорке

Строительные блоки жизни стабильны в условиях Венеры

Уинстон Черчилль скрывал информацию об НЛО

Уфологи устремились на юг Франции

Фестиваль НЛО пройдет в апреле в Эдинбурге

Шведский архив регистрирует паранормальные явления

Автокресло

Влияние накрутки реакций в Telegram на контентную стратегию. Анализ и рекомендации

Астрофизики дадут подсказку в поисках темной материи

Более 1500 наблюдений НЛО над Великобританией за 4 года

Британский взгляд на внешность инопланетян

В Великобритании замечено почти 2000 наблюдений НЛО

ИИ ChatGPT является очень эффективным инструментом

Как были сделаны татуировки ледяного человека Эци

Как, по мнению британцев, выглядят инопланетяне

Китай может начать атаку на США с Луны

Китай строит ядерный космический двигатель

Люди изменили свои суждения под воздействием ИИ

Наблюдения НЛО в районе Тиссайда

Наблюдения НЛО над Ноттингемширом за последние три года

Намеки на третью планету системе PDS 70

Начались продажи электрических летающих такси

Нашли одну из древнейших звезд

Один астероид создал более 2 млрд вторичных кратеров

Пентагон усердно скрывает информацию об НЛО

Плавающие кристаллы замедляют старение звезд

Планетарная геофизика поможет в поиске инопланетян

Последние наблюдения НЛО в Лестершире

Почему миллиардеры по всему миру строят бункеры

Рентген показал каменного младенца внутри женщины

Робот, который выполнил сальто назад без гидравлики

Сбитый с толку астроном заметил НЛО над Луной

Следующий имплант Neuralink подарит зрение слепым

Собираются создать лунную железную дорогу

Создали импульсный двигатель на водяном топливе

У людей с гаванским синдромом не выявили повреждений мозга

Флотилия НЛО замечена над горой Шаста

Эра ИИ наступит быстрее, чем мы думали

Анализ может привести к изменению парадигмы о НЛО

Более 1500 наблюдений НЛО над Англией за 4 года

В Башкирии заметили падение с неба светящегося шара

Вампиршу XVI века похоронили с кирпичом в зубах

Детей из Зимбабве мучает полтергейст

Екатеринбуржцы увидели НЛО в облаках над городом

Жительница Эдинбурга заметила дискообразный НЛО

Загадка Безумного камня

Йог 22 года медитирует на жутком холоде

Как мы будем с ними разговаривать с инопланетянами

Легендарная подземная школа чернокнижников

Мы увидим полностью созданные ИИ игры через 5-10 лет

Наблюдения НЛО в Англии с 2020 года

Наблюдения НЛО над Мерсисайдом

Наркомана убила статуя Будды

НАСА обнаружит жизнь на Европе к 2030 году

Нечто с длинной шеей попал на камеру наблюдения

НЛО пролетает над поверхностью Луны

НЛО сбили в бразильском городе Пау Гранде

Новые изображения дьявольской кометы

Новые необычные наблюдения НЛО в районе Ковентри

ООН приняла эпохальную резолюцию по ИИ

Полемика вокруг загадочных сферул не утихает

Процедуры отчетности о НЛО и утилизации материалов

Рост числа государственных служащих-роботов

Самые реалистичные сценарии Апокалипсиса

Ужасающее заболевание - синдром лица демона

Что предсказал Нострадамус России

Штаты США, где вы будете похищены инопланетянами

Эволюция мозговых чипов

Бетти Андреассон провела у пришельцев несколько часов

Где в США лучшее место, чтобы увидеть НЛО

Загадочный космонавт Солуэй Ферт

Интерактивная карта НЛО в Великобритании

Истинно верующие атаковали бывшего главу AARO

Историческая уфологическая хроника

Лучшее место для встречи с инопланетянами

Не ждите правды от правительства США о НЛО

Несколько НЛО были замечены над Орегоном

Нефтянник заметил НЛО в форме тарелки

НЛО заметили в штате Миннесота

НЛО над фермой в Орегоне

НЛО украл шесть дней из жизни Трэвиса Уолтона

Офицер полиции Лонни Замора заметил НЛО

Парень заметиил НЛО прежде чем они растворились

Первая трансплантация ГМ-почки свиньи пациенту

Похищение Бетти и Барни Хилл одно из самых странных

Сексуальные эксперименты инопланетян над землянами

Тайна наблюдений НЛО вблизи ядерных объектов

Уфологи терроризируют бывшего директора AARO

Азиатская Зона 51 проводит фестиваль

Астероид изменил форму после удара зонда землян

Вы когда-нибудь сталкивались с инопланетянами в Айдахо

Изменяющий форму НЛО замечен над Бирмингемом

ИИ комментирует теории заговора о Кеннеди

ИИ может заменить умерших близких людей

ИИ становится волком с Уолл-стрит

Масштабная уфо-конференция все ближе

Модель Эбби Клэнси боится инопланетян

Нашли лучшее место для наблюдений НЛО в США

НЛО в форме тарелки парил над нефтяной вышкой

Одержимая женщина помочилась черным

Пациент Neuralink с параличом конечностей играет в шахматы

Похищение в Паскагуле покажут на Netflix

Почему так много людей все еще верят в НЛО

Сверхпроводимости при комнатной температуре не существует

Уфологи собрались у офиса Чака Шумера в Нью-Йорке

Уфологи устремились в тихий город Лимож

Уфологическая неделя на британском ТВ

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

Быстрые займы онлайн

Аватар никогда не будет лгать или будет

Адмирал ВМС видел секретные файлы об НЛО

Водород обеспечивал энергию при зарождении жизни

Высокоскоростная камера зафиксировала полет НЛО

Добровольцы обнаружили 15 редких активных астероидов

Инопланетяне более чем реальны

Как Земля остается пригодной для жизни

Может ли земная жизнь выжить у красного карлика

Наблюдения НЛО в Арканзасе

Нам следует изучать на неопознанные подводные объекты

Нейтринный фон мог бы многое рассказать нам о Вселенной

Нехватка воды приводит к образованию кругов фей

НЛО замечен над Лас-Вегасом и горой Спирит

Оператор нефтяной вышки заметил НЛО

Опубликована карта активных черных дыр

Песчаные дюны Титана состоят из разбитых маленьких лун

Сколько времени потребуется, чтобы обойти Марс

Таинственные звери Японии. Жуткие ползающие твари

Тайна сознания. Чего может достичь наука

Уфо-конференция стоимостью 160 фунтов за билет

Британский спецназ обнаружил сбитый НЛО

Воспроизвели самую раннюю форму жизни в лаборатории

Где замечали рейс MH370 на картах Google

ИИ представляет угрозу для человечества

Кукла на ветрине пугает покупателей

НЛО - это одно, но НПО представляют реальную угрозу

НЛО представляют явную и настоящую опасность

Новые кадры НЛО являются ключом к разгадке тайны

НПО представляют угрозу

Пентагон продолжает поиски внеземной жизни

Пилоты путают НЛО со спутниками Starlink

Портативные наборы для обнаружения НЛО

Робот пародирует Илона Маска и Дональда Трампа

Секретные материалы газеты Гримсби Телеграф

Сколько НЛО было замечено в Мичигане

Тайна, стоящая за взрывом наблюдений НЛО

Тайны легендарного наблюдения 'Огни Феникса'

Уфологи вызовут НЛО для документального фильма

Что случилось с рейсом MH370

Я скептически отношусь к инопланетным НЛО

Натуральная продукция по уходу за лицом и телом. Основные плюсы

Военный ИИ Пентагон улучшал с помощью StarCraft II

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

Подписка на новости
Наверх
Яндекс.Метрика