Почему полнота по Тьюрингу верна?

15

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

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

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

У меня есть два актуальных вопроса :

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

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

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

MathematicalOrchid
источник
7
Компьютеры (и их теоретические модели, такие как машины Тьюринга) НЕ МОГУТ вычислить все. Посмотрите, например, проблему остановки .
2
Ответ на второй вопрос: мы не докажем это; это вопрос определения; оказывается, что то, что мы интуитивно думаем о «вычислимом», вычислимо на машинах Тьюринга (или что-нибудь эквивалентное). Это утверждение известно как тезис Черча-Тьюринга .
sdcvvc
2
Такие машины, как ваш компьютер, имеющие ограниченную память, не являются эквивалентными по Тьюрингу. Машины Тьюринга имеют неограниченную ленту, что означает, что чем дольше продолжается вычисление, тем больше памяти они могут использовать. ПК не могут выполнять вычисления, которые занимают ограниченное время, но требуют больше памяти, чем они имеют в наличии.
Майк Самуэль
3
@MikeSamuel - это педантичное различие, похожее на то, что «во вселенной есть конечное число частиц, поэтому все в конечном состоянии». Это верное утверждение, но не полезное. Редко полезно моделировать реальный компьютер как конечный автомат.
Артем Казнатчеев

Ответы:

17

Человечество формализовало вычисления и разработало две системы для них в 1936 году с оригинальными документами Алонзо Черча о -calculus и Алане Тьюринге (которому сегодня, 23 июня 2012 года, исполнилось бы 100 лет, если бы не презрительные обстоятельства, приведшие к его раннему уходу) на то, что стало известно как машины Тьюринга. Оба математика решали проблему Entscheidungs .λ

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

Как вы заметили, вычислимый определяется как «вычислимый на машине Тьюринга», и все другие разумные модели вычислений оказались эквивалентными по своей мощности. Вера в то, что все разумные модели вычислений эквивалентны в решении проблем, которые они могут решить, известна как тезис Черча-Тьюринга . В своем первоначальном виде оно почти полностью верилось ученому сообществу. На самом деле не совсем ясно, что это значит для доказательства / опровержения тезиса Черча-Тьюринга ; во многих отношениях это становится эмпирическим вопросом.

λ вычислимо) квантовые вычисления все еще эквивалентны модели Тьюринга.

Артем Казнатчеев
источник
1
Работа Тьюринга 1936 года, по сравнению с работой Черча в то время, была гораздо более убедительной в своем аргументе, что любая числовая функция, которая может быть вычислена алгоритмически человеком, может быть вычислена машиной Тьюринга. Формализм Черча, очевидно, не обладал этим свойством, и по сей день приведение других вычислительных систем к машинам Тьюринга жизненно важно из-за первоначального анализа Тьюринга того, что машины Тьюринга могут вычислить.
Карл Маммерт
1
@CarlMummert Я определенно согласен, но работа Черча должна быть упомянута для полноты. Кроме того, это не так уж и незначительно, хотя большая часть Теории А построена вокруг ТМ, Теория Б гораздо более дружественна к лямбда-кальку. Так что это также частично разница культур.
Артем Казнатчеев
Подождите - значит, вы говорите, что не было доказано, что более мощной вычислительной системы не существует? Это просто предположение ?
Математическая
@MateticOrchid все разумные модели вычислений (разумные примерно означают: когда-то работающие только с конечными сечениями объектов и только с одним из конечного числа опций), с которыми я знаком, были показаны эквивалентными машинам Тьюринга.
Артем Казнатчеев
2
@MateticOrchid Чтобы дать потенциально более простой ответ на ваш дополнительный вопрос: правильно, никто не доказал, что не существует разумной модели вычислений, более мощной, чем TM. «Предположение» - одно слово для этого; «гипотеза» это другое. Мы могли бы проснуться завтра и увидеть новую, лучшую модель вычислений на CNN. Это маловероятно, но возможно.
Patrick87
-2

Есть причина, по которой она называется машиной Тьюринга, и это потому, что она была изобретена Аланом Тьюрингом. Он сделал статью 1936 года, обосновав эти концепции. Если вы хотите узнать больше о машинах Тьюринга, проверьте бумагу. До того, как он спроектировал и построил тот, который взломал Enigma, он серьезно сомневался, что эта концепция действительно может работать. Однако англичане были в отчаянии, и он был гением, поэтому они доверяли ему, и это окупилось.

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

щенок
источник
Тьюринг не проектировал и не создавал загадки (хотя он проектировал другой компьютер, который никогда не был построен). Ваш второй абзац хорошо сделан: много волнений во времена Тьюринга (и это действительно был смысл его собственной статьи) связано с пределами вычислений.
Марчин
Мы доверяли ему? Только до тех пор, пока он публично не доказал, что он гомосексуалист, мы его за это убили. Также было доказано, что существует ряд проблем, которые могут быть установлены в рамках любой аксиоматической структуры, которые никогда не могут быть доказаны с помощью этих аксиом.
@TonyHopkinson: я знаю. Однако работа ТМ состоит не в том, чтобы вычислять все , а только в том, что можно вычислить. Ваше утверждение только говорит о том, что есть некоторые вычисления, которые не могут быть подтверждены. Это не значит, что они не могут быть сделаны.
@ Марчин: Я никогда не подразумевал, что Тьюринг спроектировал или построил Энигму. Я сказал, что он сыграл решающую роль в машине, которая взломала Enigma.
7
Этот ответ неверен . Тьюринг не разработал ТМ для взлома загадки, он помог разработать Bombe, которая была специализированной машиной для атаки на шифр Enigma, а не универсальной. Кроме того, не было известно, что математика может быть сведена к некоторому набору аксиом. Фактически в 1931 году Годель доказал обратное, и именно на идеях этого доказательства была основана работа Тьюринга. Даже вступительный комментарий о чтении оригинальной статьи Тьюринга вводит в заблуждение. Хотя статья великолепна, если вы просто хотите изучить основы, современные учебники, такие как Sipser, лучше.
Артем Казнатчеев