Здравствуйте, kov_serg, Вы писали:
G>>Ну то есть, вот допустим я написал такую программу-анализатор, которая принимает на вход начальное состояние виртуальной машины и выдает ответ, остановится она или нет.
_>Берём, например, теорему Ферма и ищем решения x^n+y^n=z^n перебором
_>если решение есть выходим иначе ищем до посинения. Как анализатор может понять есть там хоть одно решение или нет?
Для начала невредно вспомнить, что Ферма имел в виду целые числа.
А в компьютере никаких "целых чисел" нет.
Обычная арифметика работает не с Z, а кольцом вычетов по модулю 2^N.
Арифметика с "бесконечными целыми" всё ещё работает с целыми вполне себе ограниченного размера.
Поэтому никакая реальная программа не сможет перебрать "все целые числа".
Построение анализатора, который бы проверял воображаемую программу для воображаемой машины, невозможно.
А вот построение анализатора, который бы проверял реальную программу на реальной машине — теоретически возможно.
И если мы реализовали перебор корректно, то программа успешно переберёт все доступные ей целые числа и остановится.
А если мы допустили в программе косяк, то она впадёт в цикл и её поймает детектор циклов.

Ни в одном из этих случаев мы так и не получим доказательства теоремы Ферма.
Единственная надежда — на то, что мы вдруг получим опровержение теорем, найдя контрпример, влезающий в ограничения реальной машины.

Здравствуйте, kov_serg, Вы писали:
G>>Ну то есть, вот допустим я написал такую программу-анализатор, которая принимает на вход начальное состояние виртуальной машины и выдает ответ, остановится она или нет.
_>Берём, например, теорему Ферма и ищем решения x^n+y^n=z^n перебором
_>если решение есть выходим иначе ищем до посинения. Как анализатор может понять есть там хоть одно решение или нет?
Для начала невредно вспомнить, что Ферма имел в виду целые числа.
А в компьютере никаких "целых чисел" нет.
Обычная арифметика работает не с Z, а кольцом вычетов по модулю 2^N.
Арифметика с "бесконечными целыми" всё ещё работает с целыми вполне себе ограниченного размера.
Поэтому никакая реальная программа не сможет перебрать "все целые числа".
Построение анализатора, который бы проверял воображаемую программу для воображаемой машины, невозможно.
А вот построение анализатора, который бы проверял реальную программу на реальной машине — теоретически возможно.
И если мы реализовали перебор корректно, то программа успешно переберёт все доступные ей целые числа и остановится.
А если мы допустили в программе косяк, то она впадёт в цикл и её поймает детектор циклов.

Ни в одном из этих случаев мы так и не получим доказательства теоремы Ферма.
Единственная надежда — на то, что мы вдруг получим опровержение теоремы, найдя контрпример, влезающий в ограничения реальной машины.