Сообщение Re[8]: Проблема остановки и память от 09.10.2015 19:50
Изменено 10.10.2015 2:17 Evgeny.Panasyuk
Здравствуйте, Кодт, Вы писали:
KV>>Если для вычисления CounterExample требовалась бы МТ, то классического способа доказать выделенное просто не существовало бы. Однако, для вычисления x ^ n + y ^ n == z ^ n вероятно достаточно и стекового автомата, поэтому мы и имеем 130 страниц, доказывающих по сути, что на любых наборах входных данных этот автомат не достигнет допускающего состояния.
К>Какая-то хитрость в этих рассуждениях.
Хитрость на поверхности:
Из неразрешимости проблемы останова следуют то, что мы не можем иметь общий/единый алгоритм на МТ который доказывает не останов произвольного алгоритма на МТ.
Но из этого отнюдь не следует того, что для какого-то конкретного алгоритма МТ у нас не может быть алгоритма МТ доказательства его не останова.
KV>>Если для вычисления CounterExample требовалась бы МТ, то классического способа доказать выделенное просто не существовало бы. Однако, для вычисления x ^ n + y ^ n == z ^ n вероятно достаточно и стекового автомата, поэтому мы и имеем 130 страниц, доказывающих по сути, что на любых наборах входных данных этот автомат не достигнет допускающего состояния.
К>Какая-то хитрость в этих рассуждениях.
Хитрость на поверхности:
Из неразрешимости проблемы останова следуют то, что мы не можем иметь общий/единый алгоритм на МТ который доказывает не останов произвольного алгоритма на МТ.
Но из этого отнюдь не следует того, что для какого-то конкретного алгоритма МТ у нас не может быть алгоритма МТ доказательства его не останова.
Re[8]: Проблема остановки и память
Здравствуйте, Кодт, Вы писали:
KV>>Если для вычисления CounterExample требовалась бы МТ, то классического способа доказать выделенное просто не существовало бы. Однако, для вычисления x ^ n + y ^ n == z ^ n вероятно достаточно и стекового автомата, поэтому мы и имеем 130 страниц, доказывающих по сути, что на любых наборах входных данных этот автомат не достигнет допускающего состояния.
К>Какая-то хитрость в этих рассуждениях.
Хитрость на поверхности:
Из неразрешимости проблемы останова следует то, что мы не можем иметь общий/единый алгоритм на МТ который доказывает не останов произвольного алгоритма на МТ.
Но из этого отнюдь не следует того, что для какого-то конкретного алгоритма МТ у нас не может быть алгоритма МТ доказательства его не останова.
KV>>Если для вычисления CounterExample требовалась бы МТ, то классического способа доказать выделенное просто не существовало бы. Однако, для вычисления x ^ n + y ^ n == z ^ n вероятно достаточно и стекового автомата, поэтому мы и имеем 130 страниц, доказывающих по сути, что на любых наборах входных данных этот автомат не достигнет допускающего состояния.
К>Какая-то хитрость в этих рассуждениях.
Хитрость на поверхности:
Из неразрешимости проблемы останова следует то, что мы не можем иметь общий/единый алгоритм на МТ который доказывает не останов произвольного алгоритма на МТ.
Но из этого отнюдь не следует того, что для какого-то конкретного алгоритма МТ у нас не может быть алгоритма МТ доказательства его не останова.