Я начинаю читать книгу о вычислительной сложности и машинах Тьюринга. Вот цитата:
Алгоритм (т. Е. Машина) может быть представлен в виде битовой строки, как только мы определимся с каноническим кодированием.
Это утверждение представлено как простой факт, но я не могу его понять.
Например, если у меня есть алгоритм, который принимает качестве входных данных и вычисляет или:( х + 1 ) 2
int function (int x){
x = x + 1;
return x**2;
}
Как это можно представить в виде строки, используя алфавит ?
algorithms
turing-machines
computability
computation-models
Кененбек Арзиматов
источник
источник
Ответы:
Самый наивный и простой ответ на ваш вопрос заключается в том, что предоставленный код (и скомпилированный машинный код) фактически представлены в виде синтаксических строк {0,1} *. Кроме того, поскольку вы говорите о машинах Тьюринга, программы, которые они запускают, представляют собой линейный список операций / инструкций, нет никаких причин, по которым они не могут быть представлены в битах / байтах.
источник
У вас уже есть представление этой функции в виде текста. Преобразуйте каждый символ в однобайтовое значение, используя кодировку ASCII. Тогда результатом является последовательность байтов, т. Е. Последовательность битов, т. Е. Строка над алфавитом . Это один из примеров кодирования.{ 0 , 1 }*
источник
Я не могу устоять ...
(Точки выше представляют собой единицы, пробелы нули).
источник
Ваш компьютер хранит все как последовательности
0и1, включая вопрос, который вы ввели, чтобы спросить, как он это делает. Например, каждая буква и символ представлены 8-разрядными (я говорю о том, как все было раньше, сейчас это 16-разрядные и более сложные). Вы можете увидеть их здесь . Ну, они показывают не биты, а шестнадцатеричные и восьмеричные коды. Знаете ли вы, как преобразовать число в цифровое представление?источник
Основополагающей гипотезой этой концепции является тезис Черча-Тьюринга . Может быть трудно понять, что любой алгоритм может быть представлен в виде цепочки битов, потому что термин «алгоритм» можно рассматривать в очень неформальных терминах. В тезисе Черча-Тьюринга они используют очень строго определенную концепцию того, что такое алгоритм (и даже тогда было несколько вопросов о словах). Однако их терминология стала настолько влиятельной, что иногда утверждают, что эти определения для слов типа «алгоритм» настолько эффективны, что мы просто принимаем их в качестве определения.
Черч-Тьюринг утверждает, что каждый алгоритм может быть реализован в виде вычисления на машине Тьюринга. Учитывая, что описание машины Тьюринга представляет собой конечный набор значений, тривиально увидеть, как отобразить это описание в последовательность чисел, а затем в последовательность из 0 и 1.
Как уже упоминалось в других ответах, представить свой пример алгоритма тривиально, используя кодировку ASCII или другие кодировки.
Я думаю, что причина, по которой ваша книга приводит это утверждение как факт, связана с тем фактом, что многие просто используют тезис Черча-Тьюринга в качестве основы для определения алгоритма. Если вы используете такое определение, оно так же очевидно из факта, как «5 - это число», потому что вы в основном определили его как таковое.
источник
Это утверждение основано на существовании универсальных ТМ . Это в основном программируемые ТМ, которые могут имитировать любую другую ТМ с максимальными накладными расходами. Следовательно, ваша программа является просто частью ввода, закодированной как нули и единицы.
источник
Что ж, давайте поговорим об алгоритмах, которые нельзя представить в виде конечной битовой строки для любого вида кодирования.
Позвольте мне напечатать такой алгоритм для вас ... Ах, но если я сделаю это, я смогу представить этот алгоритм с кодировкой моего напечатанного текста.
Как насчет представления моего алгоритма, используя некоторые «аналоговые средства», скажем, положением нескольких монет на моем столе. Хотя положение этих монет можно смоделировать с помощью некоторых действительных чисел (которые в некоторых кодировках невозможно представить окончательно), все это описание снова можно считать представлением моего алгоритма и снова можно закодировать в битовую строку!
Я надеюсь, что эти примеры проясняют, что если какой-либо алгоритм не может быть представлен конечной цепочкой битов, у нас нет средств для описания этого алгоритма вообще!
Итак, почему мы должны рассматривать существование чего-то, о чем мы не можем говорить? Возможно, интересно для философии, но не для науки. Следовательно, мы определяем понятие алгоритма так , чтобы оно могло быть представлено битовой строкой, поскольку тогда мы, по крайней мере, знаем, что мы можем говорить обо всех алгоритмах.
Хотя приведенный выше ответ на заданный вопрос, я думаю, что путаница в приведенном примере в основном связана с тем фактом, что представление должно только однозначно представлять некоторый алгоритм. Способ представления не должен включать фактические вычисления, вызываемые алгоритмом! Это очень полезно, так как это означает, что мы также можем представлять неисчислимые алгоритмы!
источник
Еще один способ увидеть это через теорию информации. Все кодировки значимой / полезной информации / вопросов могут быть преобразованы в двоичные «последовательности».
Большая часть поля посвящена вопросу: «Как задать наименьшее среднее количество вопросов для передачи значимой части информации?» На практике это то же самое, что «каков оптимальный подход к наименьшему количеству вопросов« да / нет », чтобы понять, что было сообщено или сказано?»
источник