Связь между счетностью и остановкой машины Тьюринга
Привет, у меня есть сомнения в счетности. Почему необходимо выяснить, исчисляются ли определенные вещи. Есть ли польза от его поиска? А также, если какая-то вещь неисчислима, означает ли это, что не существует машины Тьюринга, которая могла бы ее решить?
3 ответа
Я надеюсь, что я не помогу вам ответить на вопрос экзамена, отвечая на ваш вопрос.
Счетные машины и машины Тьюринга - это две стороны одной медали. Это дополнительные способы определения, является ли проблема "вычислимой". Существуют и другие эквивалентные способы отображения вычислимости (поиск счетных машин, счетных функций, вычислимых функций и т. Д.). По определению, вы показываете, что задача вычислима, если вы можете продемонстрировать, что она может быть решена машиной Тьюринга. В качестве альтернативы вы можете показать задачу вычислимой, если вы можете показать, что она имеет биекцию решения из счетно бесконечного множества.
Кстати, счетно бесконечное множество - это "малое" бесконечное множество или множество ℵ₀. (С точки зрения непрофессионала, малое бесконечное или счетно бесконечное множество - это множество целых чисел. Целые числа, нечетные числа или четные числа имеют одинаковую мощность - малое бесконечное множество. Существует бесконечная иерархия бесконечных множеств, начинающаяся с ℵ₀ и идущая вверх в ℵ_∞. ℵ₀, множество целых чисел, является наименьшим бесконечным множеством. ℵ₁ является надмножеством ℵ₀. R, множество действительных чисел, имеет ту же мощность, что и ℵ₁, и т. д.) Понимание того, что существует иерархия из бесконечности поможет вам понять, что вам нужно доказать, чтобы показать вычислимость.
Простейшая машина Тьюринга имеет небольшую бесконечную ленту. Показ того, что задача может быть вычислена с помощью машины Тьюринга, означает, что задача имеет решение, ограниченное малым бесконечным временем и пространством. У машины Тьюринга есть лента с бесконечными ячейками, которые могут содержать символы. Есть бесконечные ячейки в обоих направлениях (маленькие бесконечные), так же как множество целых чисел бесконечно в обоих направлениях. С лентой связана головка для чтения и записи, которая может перемещаться влево или вправо на ленте и может читать или записывать один символ при каждом движении. Показать последовательность инструкций, которая перемещает головку на ленте из исходного состояния в конечное состояние остановки или завершения, чтобы показать, что проблема является "вычислимой". Доказательство того, что машина Тьюринга не может решить проблему, значит доказать, что проблема не вычислима, независимо от того, даем ли мы бесконечно много времени или ресурсов. Кстати, время и пространство дополняют друг друга. Если вы можете решить задачу за конечное время, используя исчисляемое бесконечное пространство, или решить ее, используя конечное пространство со счетно (т.е. малым) бесконечным временем, вы покажете, что задача вычислима.
Я могу дать вам небольшой ответ (извините, я знаю только немного теории вычислений).
Существует только много машин Тьюринга. Таким образом, если у вас есть множество проблем, которые неисчислимы, вы знаете, что в этом наборе есть по крайней мере одна проблема, для которой нет машины Тьюринга, которая ее решит.
Так, например, если ваш набор проблем
Для некоторой функции f:N -> N напишите программу, которая, учитывая n, вычисляет f(n)
Вы знаете, что есть хотя бы один f для которых такая программа не может быть дана, потому что существует бесчисленное множество таких f,
Я не верю, что этот анализ может быть применен к проблеме остановки, потому что проблема остановки состоит из ровно одной проблемы: "учитывая код для машины Тьюринга, решите, будет ли она, в случае пустой ленты, в конечном итоге останавливаться". Это всего лишь одна проблема со счетным количеством возможных входных данных, поэтому, если подсчитать, это выглядит потенциально разрешимым. Вы должны были бы поспорить другим способом, что это не разрешимо.
Конечно, важность исчисляемости и несчетности гораздо более разнообразна, чем этот пример. Я надеюсь, что другие люди могут предоставить еще немного.
Счетность на самом деле очень важна, когда дело доходит до машины Тьюринга и во многих других областях математики и естественных наук. Поскольку машина Тьюринга должна выполнять операции последовательно, каждому шагу может быть присвоен счетный номер. Если процесс продолжается вечно, то процесс бесконечно бесконечен.
Примером операции, для которой машина Тьюринга была бы неадекватной, было бы суммирование квадратов всех чисел от 1 до 2. Можно легко показать, что весь список рациональных чисел в этом интервале может быть перечислен в счетном списке в который каждое число может быть сопоставлено 1 к 1 с подсчетом числа. Таким образом, выполнение шагов по одному в этом списке чисел может выполняться машиной Тьюринга. Однако этого нельзя сделать с помощью иррациональных чисел на этом интервале, потому что их слишком много. Можно показать (не так просто), что список иррациональных чисел нельзя поместить в упорядоченный (счетный) список. Таким образом, нет порядка, в котором можно перечислить каждое число на интервале, что означает, что машина Тьюринга не может выполнить задачу, даже если ей предоставляется бесконечное количество времени.