CD
не думаю, что трансляцию из LLVM в команды CPU можно верифицировать, это решение эквивалентности программ
Size: a a a
2020 August 24
EG
Начнём с того, что не любую программу можно верифицировать, казалось бы.
EG
Казалось бы, это решало бы проблему останова.
CD
Начнём с того, что не любую программу можно верифицировать, казалось бы.
Любую, конечно, теоретически - память ограничена
EG
Любую, конечно, теоретически - память ограничена
Ты не можешь по произвольной функции проверить, не зависает ли она случайно на каком-то инпуте.
EG
Это теоретически невозможно.
CD
Это теоретически невозможно.
Невозможно для МТ, но твой комп в x64 это конечный автомат, а не МТ
CD
У тебя предел адресов, лента конечная
CD
всего лишь какие-нибудь 2^(2^64) памяти решают эту задачу
EG
У тебя предел адресов, лента конечная
Интуитивно кажется, что у тебя заведомо не хватит памяти, чтобы решить проблему останова для МТ с таким же количеством памяти
EG
Доказать не могу. Интересный вопрос.
CD
Интуитивно кажется, что у тебя заведомо не хватит памяти, чтобы решить проблему останова для МТ с таким же количеством памяти
Ну я умею решать проблему останова для IP = 18 бит, AL = 8 бит, других регистров и памяти нет)
CD
Доказать не могу. Интересный вопрос.
Да бобра пихай
CD
Всегда срабатывает)
CD
Доказать не могу. Интересный вопрос.
https://en.wikipedia.org/wiki/Busy_beaver
вот это офигенная моделька происходящего
вот это офигенная моделька происходящего
CD
Если не помогает - решаем универсальное диофантово уравнение)
CD
Интуитивно кажется, что у тебя заведомо не хватит памяти, чтобы решить проблему останова для МТ с таким же количеством памяти
Правда, МТ с конечной памятью это конечный автомат, так что скорее всего надо в сторону P == NP копать
S
А почему ты не учитываешь вероятность, что ты тупо допустишь ту же самую ошибку в доказательстве?
А почему ты не учитываешь вероятность, что ты тупо допустишь ту же самую ошибку в тесте?
CD
А почему ты не учитываешь вероятность, что ты тупо допустишь ту же самую ошибку в тесте?
Качество тестов проще всего контролировать именно на детектировании глупых ошибок
CD
Убрать определенное множество ошибок - уже хрюшка для тестов