Задача обучения вычислимости

22

Мне трудно преподавать понятие вычислимых функций. Я попытался развить идею, почему такие исследователи, как Гильберт / Аккерманн / Годель / Тьюринг / Черч / ... изобрели понятие «вычислимости». Студенты сразу спросили: «что означает вычислимость?» и я не могу ответить, пока не научу их машинам Тьюринга, а затем отвечу: «Функция вычислима, если машина Тьюринга вычисляет ее».

Так,

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

mcKlane
источник
10
«Каждая функция, которую может вычислить компьютер»? Обычно я прибегаю к языкам программирования, так как студенты, вероятно, знают один. Я также пытался использовать «любой рецепт для вычисления функции» как интуитивное определение алгоритма.
Михаэль Кадилхак
5
Задача вычислима, если ее можно решить с помощью конечного набора правил, управляющих эволюцией дискретной динамической системы за конечное число шагов.
Мохаммед Аль-Туркистани
1
Кроме того, вы можете использовать десятую проблему Гильберта, чтобы объяснить студентам, почему она неразрешима и что доказательство неразрешимости требовало, помимо прочего, формализации понятия вычислимости в математике.
Мохаммед Аль-Туркистани
Другой вопрос: тезис Черча-Тьюринга утверждает, что функция может быть вычислена некоторой машиной Тьюринга тогда и только тогда, когда она может быть вычислена некоторой машиной любой другой «разумной и общей» модели вычисления [Goldreich, 2008]. Итак, возможно ли модельно-независимое понятие вычислимости?
MS Dousti

Ответы:

37

75 лет назад вокруг не было компьютеров. Поэтому нужно было очень тщательно объяснить математическую идею компьютера.

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

Вы просто идете в класс и спрашиваете: что там, что ваши айфоны не могут вычислить? Это сразу же приводит вас к вопросам о ограниченных ресурсах. Затем вы говорите: хорошо, предположим, что у вашей машины действительно было неограниченное количество памяти, есть что-то, что она не могла вычислить? И вы идеализируете немного больше и ограничите внимание теоретико-числовыми функциями (потому что вы не интересуетесь Facebook в данный момент). Вам придется немного объяснить, как работают компьютеры (как уже упоминалось в комментариях, хорошо, если студенты знают язык программирования, потому что вы можете использовать его вместо описания аппаратного обеспечения), но после этого вы можете использовать все классические аргументы вычислимости теория для получения результатов. Неважно, что ментальная картина ваших учеников - это iPhone. На самом деле это имеет значение:для них более важно знать, что их iPhone не может делать определенные вещи.

Андрей Бауэр
источник
2
Мне очень нравится этот аргумент, потому что он идет от конкретного (iPhone) к абстрактному.
Суреш Венкат
2
Вот интересная загадка: каковы теоремы smn и utm в Haskell?
Андрей Бауэр
18
«75 лет назад вокруг не было компьютеров». Это просто ложь. 75 лет назад вокруг было много компьютеров. Это были люди, в основном женщины; у них были ученые степени по математике, несколько элементарных инструментов для механических вычислений (например, добавление машин и правила слайдов) и много-много бумаги. Эти компьютеры были основой как Манхэттенского проекта, так и парка Блетчли во время Второй мировой войны (несмотря на бомбу и бомбу). Это компьютерная среда, которую моделировал Тьюринг: люди с карандашом и бумагой.
Джефф
10
@Jeffe: давай, вы знаете, что я имел в виду.
Андрей Бауэр
8
@JeffE: мы можем проверить твою гипотезу. Подойдите к своим коллегам и попросите их нарисовать «компьютер в короткой юбке». Пожалуйста, сообщите, сколько человек нарисовал.
Андрей Бауэр
12

«Функция вычислима, если существует« эффективная процедура »для перехода от ввода к выводу». Представляя эту тему, я в прошлом указывал, как они (студенты) имеют эффективную процедуру для решения квадратных уравнений, но не имеют одну для решения уравнений степени 5 или более. Это может привести к обсуждению того, как можно формализовать «эффективную процедуру», но это обсуждение - то, чего вы хотите добиться, поэтому я думаю, что это особенность, а не ошибка.

Питер Бут
источник
3
Примечательно: теорема Абеля – Руффини утверждает, что не существует общего алгебраического решения, т. Е. Решения в радикалах, для полиномиальных уравнений степени пять или выше. Однако существуют методы, такие как радикал Бринга , для получения замкнутых решений уравнений в квинтах.
MS Dousti
Ваш придирки на самом деле отлично. Обсуждая вычислимость, вы хотите поговорить о таких вещах, как «разрешенные операции», а решения для полиномов - это одна из тех вещей, которые становятся более сложными по мере того, как вы на них смотрите. Но для введения я думаю, что слова «эффективная процедура» и упоминание о квадратичной формуле являются отличной отправной точкой. Они не совсем верны, но интуиция довольно хороша, ИМО.
Питер Бут
8

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

Дэйв Кларк
источник
6

Я начинаю с вопроса: «Есть ли вопрос, на который ни один компьютер не смог бы ответить убедительно?» и вести дискуссию к философским вопросам, таким как «если дерево падает в лесу, оно издает звук?» или "есть ли загробная жизнь?" Мы быстро получаем согласие с тем, что человеческий язык может выражать вопросы «да / нет», связанные с парадоксами или концепциями, которые не могут быть выражены математически, и, таким образом, да, есть невычислимые вопросы.

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

Затем я возвращаюсь к доказательствам на машинах Тьюринга.

Кевин Вортман
источник
0

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

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