связь между счетностью и остановкой машины Тьюринга

Question

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

Answer 1

Я надеюсь, что не помогу вам ответить на вопрос экзамена, ответив на ваш вопрос.

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

Кстати, счетно бесконечное множество - это «маленькое» бесконечное множество или множество ℵ₀. (С точки зрения непрофессионала, малое бесконечное или счетно бесконечное множество - это множество целых чисел. Целые числа, нечетные числа или четные числа имеют одинаковую мощность - малое бесконечное множество. Существует бесконечная иерархия бесконечных множеств, начинающаяся с ℵ₀ и идущая вверх в ℵ_∞. ℵ₀, набор целых чисел, является наименьшим бесконечным набором. ℵ₁ является надмножеством ℵ₀. R , набор действительных чисел, имеет ту же мощность, что и ℵ₁, и т. д.) Понимание того, что существует бесконечная иерархия, поможет вам понять, что вам нужно доказать, чтобы продемонстрировать вычислимость.

Простейшая машина Тьюринга имеет небольшую бесконечную ленту. Показ того, что задача может быть вычислена с помощью машины Тьюринга, означает, что задача имеет решение, ограниченное малым бесконечным временем и пространством. У машины Тьюринга есть лента с бесконечными ячейками, которые могут содержать символы. Есть бесконечные ячейки в обоих направлениях (маленькие бесконечные), так же как множество целых чисел бесконечно в обоих направлениях. С лентой связана головка для чтения и записи, которая может перемещаться влево или вправо на ленте и может читать или записывать один символ при каждом перемещении. Показать последовательность инструкций, которая перемещает головку на ленте из исходного состояния в конечное состояние остановки или завершения, чтобы показать, что проблема является «вычислимой». Доказательство того, что машина Тьюринга не может решить проблему, значит доказать, что проблема не вычислима, независимо от того, даем ли мы бесконечно много времени или ресурсов. Кстати, время и пространство дополняют друг друга. Если вы можете решить задачу за конечное время, используя счетное бесконечное пространство, или решить ее, потребляя конечное пространство со счетным (то есть небольшим) бесконечным временем, вы покажете, что задача вычислима.

Answer 2

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

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

Так, например, если ваш набор проблем

Для некоторой функции f: N -> N напишите программу, которая при заданном n вычисляет f (n)

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

неисчислимо много.

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

Конечно, важность исчисляемости и несчетности гораздо более разнообразна, чем этот пример. Я надеюсь, что другие люди могут предоставить еще немного.

Answer 3

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

Примером операции, для которой машина Тьюринга была бы неадекватной, было бы суммирование квадратов всех чисел от 1 до 2. Довольно легко можно показать, что весь список рациональных чисел в этом интервале можно перечислить в счетный список, в котором каждое число может быть отображено 1-к-1 с помощью счетного числа. Таким образом, выполнение шагов по одному в этом списке чисел может выполняться машиной Тьюринга. Однако этого нельзя сделать с помощью иррациональных чисел на этом интервале, потому что их слишком много. Можно показать (не так просто), что список иррациональных чисел нельзя поместить в упорядоченный (счетный) список. Таким образом, нет порядка, в котором можно перечислить каждое число на интервале, что означает, что машина Тьюринга не может выполнить задачу, даже если ей предоставляется бесконечное количество времени.

Счётность рациональных чисел

Неисчислимость, если иррациональные числа - набор Кантора