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