Полный словарь
Под "словарем" я подразумеваю массив пар ключ / значение с уникальными ключами. Если нет, то почему? Если достаточно долго, вы можете использовать ключ в качестве входных данных и значение в качестве выходных данных, и это может решить столько проблем, сколько вы пожелаете. Он может "вычислять" что угодно, пока он достаточно длинный, чтобы вместить все возможные входные данные. Который не должен был бы быть бесконечным, пока установлено, что вход будет иметь определенное количество битов. Так что, если мы согласны с тем, что входные данные будут состоять из X битов, то вам понадобится только словарь с 2^X элементами, и у вас есть все возможные машины Тьюринга, которые будут принимать X битов в качестве входных данных.
Правильно? Ну, я думаю, что нет, но почему?
3 ответа
Простая машина Тьюринга может добавить два целых числа - любые два целых числа. Конечный словарь не может.
РЕДАКТИРОВАТЬ:
(Я редактирую свой ответ, потому что soandos высказал мнение слишком хорошо, чтобы отвечать в тесном поле для комментариев.)
Хороший вопрос! Предположим, у нас есть бесконечный словарь, в котором перечислены пары {ключ, значение}, в которых ключами являются все возможные комбинации машин Тьюринга и их конечных входов (или, что то же самое, все возможные конечные последовательности ввода для универсальной машины Тьюринга) в порядке увеличения размера. Значения представляют собой соответствующие конечные состояния с начальным битом, указывающим [HALTS, НЕ HALT]. Я утверждаю, что это полный по Тьюрингу. (Поиск записи очень прост, и я не думаю, что мы должны спорить об этом).
Неразрешимость проблемы остановки имеет эквивалент в словаре Дж. Сольди: если мы хотим иметь возможность искать бит [HALT, НЕ HALT] любой записи ниже определенного размера, нам нужна только конечная часть словаря. Но чтобы реализовать большую часть словаря в качестве машины Тьюринга, нам понадобится машина, размер которой больше этого предельного размера - его запись не будет в этой части словаря. Для машин любого размера есть машина, которая может ответить на вопрос остановки для всех машин такого размера, но эта машина больше, поэтому она не может ответить на вопрос о себе. Точно так же любой конечный том словаря полностью повторяется в какой-либо записи (на самом деле, бесконечное количество записей), но эта запись не в этом объеме.
Машина Тьюринга будет способна вычислять любой тип ввода с помощью любой программы, и это не обязательно будет ввод фиксированной длины. Кроме того, в словаре не будет возможности выбрать, какая пара ключ / значение соответствует вводу для выбранной программы.
Кроме того, если вы введете X бит, ваше пространство клавиш не будет X^2, оно будет 2^X. И это будет для одной программы.
На самом деле, даже если бы у вас был словарь с бесконечным количеством пар ключ / значение, держу пари, что логика, необходимая для определения того, какой ключ вы должны выбрать, вероятно, потребовала бы машину Тьюринга или что-то более сложное для выбора ключа.
Полнота Тьюринга связана с набором правил, чтобы что-то делать, а не с тем, как хранятся данные. Смотрите здесь.