Как доказать, что простой бессмысленный код вычислим или нет?

Характеристики вычислимой задачи:

  • Полный означает, что он охватывает все случаи;
  • Механистический означает, что он точен;
  • Детерминированный означает, что при вводе одних и тех же входных данных будут предоставлены одни и те же выходные данные.

Поправьте меня, если я ошибаюсь, я обнаружил это в ходе исследований и не совсем понял, что это на самом деле означает, за исключением детерминированного.

Итак, я пытаюсь доказать простой код, например:

int i = 0;
do{
    int j = 0;
    do{
        printf("Hello\n");
        j++;
    }while (j < n);
    printf("Hello\n");
    i++;
}while (i < n);

является вычислимым.

Я знаю, как показать, что это детерминировано, так как это довольно очевидно, но я не знаю, как показать, что это механистично или завершено.

Характеристика Complete, насколько я понимаю, больше похожа на "Есть ли какой-нибудь способ, чтобы код не выполнялся или возвращался как ошибка?" например, при открытии текстового файла есть вероятность, что файл не существует, потому что введено неправильное имя файла или указано неправильное местоположение и т. д.

Но в случае кода фрагмента выше, как я должен доказать, что он завершен?

Что касается Механизма, будет ли 1 + 1 = 2 вместо 3?

То же самое, в случае фрагмента кода выше, как я могу доказать, что он точен, поскольку сам код не решает никаких проблем, он просто печатает привет в соответствии с n значениями? Что в данном случае n ^ 2 + n число привет.


c computation-theory formal-verification formal-methods computability
person Lorale    schedule 13.11.2020    source источник
comment
Это кажется довольно бессмысленной практикой вне формальных методов, которые могут быть тем, что вы на самом деле ищете.   -  person Lundin    schedule 13.11.2020
comment
Вы выполняете около n^2 вызовов printf. Это вполне может вызвать проблемы, если n велико.   -  person gnasher729    schedule 13.11.2020
comment
Если n — это картофелина, код не скомпилируется, если n — с плавающей запятой, иногда будет трудно заранее сказать, сколько итераций на самом деле произойдет. Если n беззнаковое или длинное (длинное), код может бесконечно зацикливаться. Так действительно ли это правильно? Также довольно очевидно, что это не общепринятый формат доказательства.   -  person dratenik    schedule 13.11.2020
comment
Поиск терминов, которые вы использовали, не дает ничего особенно полезного, вам, возможно, придется обратиться к определениям (и/или объяснениям), которые вы предоставили, и проверить, удовлетворяются ли они.   -  person dratenik    schedule 13.11.2020
comment
Я не понимаю вопроса в заголовке: как какой-то код может быть бессмысленным и в то же время вычислимым. Вы понимаете, что значит вычисляемый?   -  person Luis Colorado    schedule 20.11.2020
comment
Код печатает n*(n+1) раз строку "Hello\n" (если n >= 1, если n == 0, он печатает "Hello\n" дважды). Что для вас бессмысленно?   -  person Luis Colorado    schedule 20.11.2020

Ответы (1)


arrow_upward
2
arrow_downward

Вы смешиваете несколько вещей.

Во-первых, вы предоставили кусок кода и спросили, как доказать его вычислимость. Но это не имеет никакого смысла — кусок кода не может быть вычислимым или невычислимым.

(Математическое) множество может быть вычислимым или невычислимым. И исходя из этого, все остальное, что также является набором: например, язык (который представляет собой набор строк), задача принятия решения (который представляет собой набор принятых inputs) или функцию (которая представляет собой набор пар ключ-значение).

Во-вторых, упомянутые вами характеристики не определяют вычислимых задач. Я не знаю, откуда вы их взяли, но в лучшем случае они представляют собой очень неформальное описание некоторых аспектов алгоритма решения вычислимой задачи. Так что я думаю, что вы говорите не о вычислимых задачах, а об алгоритмах. Но, учитывая, что ваши характеристики неформальны, вы не можете их доказать.

Итак, вот несколько более точных (но все же не формальных) утверждений, которые могут оказаться полезными:

  • Задача вычислима тогда и только тогда, когда существует алгоритм, решающий ее.
  • An algorithm solves a problem iff
    • it can be expressed within a standard model of computation (e.g. a Turing Machine or a standard programming language);
    • он верный по отношению к задаче: любой ответ, выдаваемый алгоритмом, принадлежит набору ответов задачи;
    • он полный по отношению к задаче: любой элемент набора ответов задачи создается алгоритмом;
    • алгоритм останавливается на всех входах.

Это характеристики, которые достаточно точны, чтобы вы могли использовать их для доказательства того, что проблема вычислима или что алгоритм решает конкретную проблему.

person Mo B.    schedule 18.11.2020