История изменений
Исправление ilammy, (текущая версия) :
Анон, хватит уже путать. Абстрактный вычислитель с конечной памятью — это не машина Тьюринга. У него конечное число состояний (собственные состояние машины, помноженные на все состояния памяти). Полноценная машина Тьюринга может за некоторое конечное время выписать у себя в памяти вообще все состояния вычислителя с конечной лентой — вершины графа. Затем для каждой вершины она может определить следующую, пользуясь конечным списком правил конечного вычислителя — это будут дуги. Каждая вершина имеет не более одной исходящей дуги, так как конечный вычислитель детерминирован. Все циклы на конечном графе можно найти за конечное время. Для решения проблемы останова для конечного вычислителя достаточно проверить, достижим ли какой-то цикл из вершины, представляющей начальную конфигурацию конечного вычислителя.
Естественно, сам конечный вычислитель не сможет решить проблему останова для самого себя, потому что у него памяти не хватит, чтобы вместить все эти графы. Машина Тьюринга не может этого сделать по той же причине: нет перечислимых множеств, которые были бы более бесконечны, чем множество натуральных чисел.
Исправление ilammy, :
Анон, хватит уже путать. Абстрактный вычислитель с конечной памятью — это не машина Тьюринга. У него конечное число состояний (собственные состояние машины, помноженные на все состояния памяти). Полноценная машина Тьюринга может за некоторое конечное время выписать у себя в памяти вообще все состояния вычислителя с конечной лентой — вершины графа. Затем для каждой вершины она может определить следующую, пользуясь конечным списком правил конечного вычислителя — это будут дуги. Каждая вершина имеет не более одной исходящей дуги, так как конечный вычислитель детерминирован. Все циклы на конечном графе можно найти за конечное время. Для решения проблемы останова для конечного вычислителя достаточно проверить, достижим ли какой-то цикл из вершины, представляющей начальную конфигурацию конечного вычислителя.
Исправление ilammy, :
Анон, хватит уже путать. Абстрактный вычислитель с конечной памятью — это не машина Тьюринга. У него конечное число состояний (собственные состояние машины, помноженные на все состояния памяти). Полноценная машина Тьюринга может за некоторое конечное время выписать у себя в памяти вообще все состояния вычислителя с конечной лентой — вершины графа. Затем для каждой вершины она может определить следующую, пользуясь конечным списком правил конечного вычислителя — это будут дуги. Каждая вершина имеет не более одной исходящей дуги, так как конечный вычислитель детерминирован. Все циклы на конечном можно найти за конечное время. Для решения проблемы останова для конечного вычислителя достаточно проверить, достижим ли какой-то цикл из вершины, представляющей начальную конфигурацию конечного вычислителя.
Исходная версия ilammy, :
Анон, хватит уже путать. Абстрактный вычислитель с конечной памятью — это не машина Тьюринга. У него конечное число состояний (собственные состояние машины, помноженные на все состояния памяти). Полноценная машина Тьюринга может за некоторое конечное время выписать у себя в памяти вообще все состояния вычислителя с конечной лентой — вершины графа. Затем для каждой вершины она может определить следующую, пользуясь конечным списком правил конечного вычислителя — это будут дуги. Каждая вершина имеет не более одной исходящей дуги, так как конечный вычислитель детерминирован. Для решения проблемы останова для конечного вычислителя достаточно проверить, входит ли в какой-то цикл вершина, представляющая начальную конфигурацию конечного вычислителя.