Является ли C на самом деле полным по Тьюрингу?

40

Я пытался объяснить кому-то, что C завершена по Тьюрингу, и понял, что на самом деле не знаю, действительно ли он технически завершен по Тьюрингу. (C как в абстрактной семантике, а не как в реальной реализации.)

«Очевидный» ответ (грубо говоря: он может адресовать произвольный объем памяти, поэтому он может эмулировать машину с ОЗУ, поэтому он завершается по Тьюрингу), на самом деле, насколько я могу судить, не совсем корректен, хотя стандарт C позволяет для того, чтобы size_t был сколь угодно большим, он должен быть фиксирован на некоторой длине, и независимо от того, на какой длине он фиксирован, он по-прежнему конечен. (Другими словами, хотя вы могли бы при произвольной остановке машины Тьюринга выбрать длину size_t так, чтобы она работала «правильно», нет способа выбрать длину size_t так, чтобы все останавливающие машины Тьюринга работали правильно).

Итак: завершен ли C99 по Тьюрингу?

TLW
источник
3
Какова "абстрактная семантика" C? Они определены где-нибудь?
Юваль Фильмус
4
@YuvalFilmus - см., Например, здесь , т.е. C, как определено в стандарте, а не, например, «это то, как это делает gcc».
TLW
1
Существует «техническая составляющая», заключающаяся в том, что современные компьютеры не имеют бесконечной памяти, как ТМ, но все еще считаются «универсальными компьютерами». и обратите внимание, что языки программирования в их «семантике» на самом деле не предполагают ограниченную память, за исключением того, что все их реализации , конечно, ограничены в памяти. Посмотрите, например, работает ли наш компьютер как машина Тьюринга . во всяком случае, по существу, все "основные" языки программирования являются законченными по Тьюрингу
vzn
2
C (как и машины Тьюринга) не ограничивается использованием внутренней компьютерной памяти для своих вычислений, так что это действительно недопустимый аргумент против полноты Тьюринга C.
reinierpost
@reinierpost - это все равно что сказать, что телетайп разумен. Это говорит о том, что «C + внешний TM-эквивалент» полон по Тьюрингу, а не что C полон по Тьюрингу.
TLW

Ответы:

34

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

В большинстве языков программирования вы можете моделировать машину Тьюринга:

  • моделирование конечного автомата с помощью программы, использующей конечный объем памяти;
  • моделирование ленты с помощью пары связанных списков целых чисел, представляющих содержимое ленты до и после текущей позиции. Перемещение указателя означает перенос заголовка одного из списков на другой список.

Конкретная реализация, работающая на компьютере, могла бы исчерпать память, если бы лента стала слишком длинной, но идеальная реализация могла бы точно выполнять машинную программу Тьюринга. Это можно сделать ручкой и бумагой или покупкой компьютера с большим объемом памяти и компилятором, ориентированным на архитектуру с большим количеством битов на слово и т. Д., Если программе когда-либо не хватает памяти.

Это не работает в C, потому что невозможно иметь связанный список, который может расти вечно: всегда есть какое-то ограничение на количество узлов.

Чтобы объяснить почему, мне сначала нужно объяснить, что такое реализация на Си. C на самом деле семейство языков программирования. Стандарт ISO C (точнее, конкретная версия этого стандарта) определяет (с уровнем формальности, который допускает английский язык) синтаксис и семантику семейства языков программирования. C имеет много неопределенного поведения и поведения, определенного для реализации, «Реализация» C кодифицирует все поведение, определяемое реализацией (список вещей для кодификации приведен в приложении J для C99). Каждая реализация C - это отдельный язык программирования. Обратите внимание, что значение слова «реализация» немного своеобразно: оно действительно означает языковой вариант, может быть несколько разных программ компилятора, которые реализуют один и тот же языковой вариант.

В данной реализации C байт имеет возможных значения CHAR_BIT . Все данные могут быть представлены в виде массива байтов: тип имеет максимум 2 CHAR_BIT × sizeof (t) возможных значений. Это число варьируется в разных реализациях C, но для данной реализации C оно является константой.2CHAR_BITt2CHAR_BIT×SizeOf (т)

В частности, указатели могут принимать только . Это означает, что существует конечное максимальное количество адресуемых объектов.2CHAR_BIT×SizeOf (недействительными *)

Значения CHAR_BITи sizeof(void*)являются наблюдаемыми, поэтому, если у вас не хватает памяти, вы не можете просто возобновить работу своей программы с большими значениями для этих параметров. Вы будете запускать программу под другим языком программирования - другой реализацией Си.

Если программы на языке могут иметь только ограниченное число состояний, то язык программирования не более выразителен, чем конечные автоматы. Фрагмент C, который ограничен адресным хранилищем, допускает самое большее состояний программы, где n - размер абстрактного синтаксического дерева программы (представляющего состояние потока управления), поэтому это Программа может быть смоделирована конечным автоматом с таким количеством состояний. Если C более выразителен, это должно быть сделано с помощью других функций.N×2CHAR_BIT×SizeOf (недействительными *)N

C напрямую не навязывает максимальную глубину рекурсии. Реализация может иметь максимум, но также может не иметь. Но как мы общаемся между вызовом функции и ее родителем? Аргументы бесполезны, если они адресуемы, потому что это косвенно ограничило бы глубину рекурсии: если у вас есть функция, int f(int x) { … f(…) …}то все вхождения в xактивных кадрах fимеют свой собственный адрес, и поэтому число вложенных вызовов ограничено числом возможных адресов для x.

Программа AC может использовать неадресуемые хранилища в виде registerпеременных. «Нормальные» реализации могут иметь только небольшое конечное количество переменных, которые не имеют адреса, но теоретически реализация может позволить неограниченный объем registerпамяти. В такой реализации вы можете делать неограниченное количество рекурсивных вызовов функции, пока ее аргумент есть register. Но поскольку аргументы таковы register, вы не можете сделать на них указатель, и поэтому вам необходимо явно копировать их данные: вы можете передавать только конечный объем данных, а не структуру данных произвольного размера, состоящую из указателей.

С неограниченной глубиной рекурсии и ограничением, что функция может получать данные только от своего прямого вызывающего ( registerаргументы) и возвращать данные своему прямому вызывающему (возвращаемое значение функции), вы получаете мощность детерминированных автоматов выталкивания .

Я не могу найти способ пойти дальше.

(Конечно, вы можете заставить программу хранить содержимое ленты внешне, через функции ввода / вывода файла. Но тогда вы не будете спрашивать, является ли C завершенным по Тьюрингу, но является ли C плюс бесконечная система хранения полным по Тьюрингу, чтобы ответ - скучное «да». Вы также можете определить хранилище как вызов оракула Тьюринга  fopen("oracle", "r+"), fwriteначальное содержимое ленты и freadобратно конечное содержимое ленты.)

Жиль "ТАК - перестань быть злым"
источник
Не сразу понятно, почему набор адресов должен быть конечным. Я написал несколько мыслей в ответ на вопрос, на который вы ссылаетесь
Алексей Б.
4
Извините, но по той же логике, нет никаких языков программирования, полных по Тьюрингу. Каждый язык имеет явное или неявное ограничение на адресное пространство. Если вы создадите машину с бесконечной памятью, то указатели произвольного доступа, очевидно, также будут иметь бесконечную длину. Поэтому, если такая машина появляется, она должна предложить набор инструкций для последовательного доступа к памяти, а также API для языков высокого уровня.
IMil
14
@IMil Это не правда. Некоторые языки программирования не имеют ограничений на адресное пространство, даже неявно. Возьмем очевидный пример: универсальная машина Тьюринга, в которой начальное состояние ленты формирует программу, является языком программирования, полным по Тьюрингу. Многие языки программирования, которые фактически используются на практике, имеют одно и то же свойство, например Lisp и SML. Язык не должен иметь понятие «указатель произвольного доступа». (продолжение)
Жиль "ТАК - перестань быть злым"
11
@IMil (продолжение) Реализации обычно влияют на производительность, но мы знаем, что реализация, выполняемая на конкретном компьютере, не является полной по Тьюрингу, так как она ограничена размером памяти компьютера. Но это означает, что реализация не реализует весь язык, только подмножество (программ, работающих в N байтах памяти). Вы можете запустить программу на компьютере, и если ей не хватит памяти, перенести ее на больший компьютер и так далее до бесконечности или до тех пор, пока она не остановится. Это был бы правильный способ реализовать весь язык.
Жиль "ТАК - перестань быть злым"
6

Добавление C99 va_copyк API с переменным аргументом может дать нам задний ход к полноте по Тьюрингу. Поскольку становится возможным повторять список переменных аргументов более одного раза в функции, отличной от той, которая первоначально получила аргументы, va_argsможно использовать для реализации указатель без указателя.

Конечно, реальная реализация API аргументов с переменным аргументом, вероятно, где-то будет иметь указатель, но в нашей абстрактной машине он может быть реализован с использованием магии.

Вот демонстрационная версия, реализующая 2-стопочный автомат с произвольными правилами перехода:

#include <stdarg.h>
typedef struct { va_list va; } wrapped_stack; // Struct wrapper needed if va_list is an array type.
#define NUM_SYMBOLS /* ... */
#define NUM_STATES /* ... */
typedef enum { NOP, POP1, POP2, PUSH1, PUSH2 } operation_type;
typedef struct { int next_state; operation_type optype; int opsymbol; } transition;
transition transition_table[NUM_STATES][NUM_SYMBOLS][NUM_SYMBOLS] = { /* ... */ };

void step(int state, va_list stack1, va_list stack2);
void push1(va_list stack2, int next_state, ...) {
    va_list stack1;
    va_start(stack1, next_state);
    step(next_state, stack1, stack2);
}
void push2(va_list stack1, int next_state, ...) {
    va_list stack2;
    va_start(stack2, next_state);
    step(next_state, stack1, stack2);
}
void step(int state, va_list stack1, va_list stack2) {
    va_list stack1_copy, stack2_copy;
    va_copy(stack1_copy, stack1); va_copy(stack2_copy, stack2);
    int symbol1 = va_arg(stack1_copy, int), symbol2 = va_arg(stack2_copy, int);
    transition tr = transition_table[state][symbol1][symbol2];
    wrapped_stack ws;
    switch(tr.optype) {
        case NOP: step(tr.next_state, stack1, stack2);
        // Note: attempting to pop the stack's bottom value results in undefined behavior.
        case POP1: ws = va_arg(stack1_copy, wrapped_stack); step(tr.next_state, ws.va, stack2);
        case POP2: ws = va_arg(stack2_copy, wrapped_stack); step(tr.next_state, stack1, ws.va);
        case PUSH1: va_copy(ws.va, stack1); push1(stack2, tr.next_state, tr.opsymbol, ws);
        case PUSH2: va_copy(ws.va, stack2); push2(stack1, tr.next_state, tr.opsymbol, ws);
    }
}
void start_helper1(va_list stack1, int dummy, ...) {
    va_list stack2;
    va_start(stack2, dummy);
    step(0, stack1, stack2);
}
void start_helper0(int dummy, ...) {
    va_list stack1;
    va_start(stack1, dummy);
    start_helper1(stack1, 0, 0);
}
// Begin execution in state 0 with each stack initialized to {0}
void start() {
    start_helper0(0, 0);
}

Примечание. Если va_listтип массива, то на самом деле существуют скрытые параметры указателя на функции. Так что, вероятно, было бы лучше изменить типы всех va_listаргументов на wrapped_stack.

feersum
источник
Это может сработать. Возможная проблема заключается в том, что он опирается на неограниченное количество автоматических va_listпеременных stack. Эти переменные должны иметь адрес &stack, и мы можем иметь только ограниченное число из них. registerМожет быть, это требование можно обойти, объявив каждую локальную переменную ?
Чи
@chi AIUI переменная не обязана иметь адрес, если кто-то не пытается взять адрес. Кроме того, незаконно объявлять аргумент, непосредственно предшествующий многоточию register.
feersum
По той же логике, не должно ли intбыть обязательным иметь ограничение, если кто-то не использует ограничение или sizeof(int)?
Чи
@chi Совсем нет. Стандарт определяет как часть абстрактной семантики, что значение intимеет значение между некоторыми конечными границами INT_MINи INT_MAX. И если значение intпереполняет эти границы, происходит неопределенное поведение. С другой стороны, стандарт намеренно не требует, чтобы все объекты физически присутствовали в памяти по определенному адресу, поскольку это позволяет оптимизировать, например, сохранять объект в регистре, сохранять только часть объекта, представляя его иначе, чем стандарт макет или вообще его опуская, если он не нужен.
feersum
4

Возможно, нестандартная арифметика?

Итак, похоже, что проблема заключается в конечном размере sizeof(t). Тем не менее, я думаю, что знаю обходной путь.

Насколько я знаю, C не требует реализации, чтобы использовать стандартные целые числа для своего целочисленного типа. Поэтому мы могли бы использовать нестандартную модель арифметики . Тогда мы установили sizeof(t)бы нестандартное число, и теперь мы никогда не достигнем его за конечное число шагов. Поэтому длина ленты машин Тьюринга всегда будет меньше «максимальной», так как максимум буквально невозможно достичь. sizeof(t)просто не число в обычном смысле этого слова.

Это одна из техничностей, конечно: теорема Тенненбаума . В нем говорится, что единственная модель арифметики Пеано является стандартной, что, очевидно, не подходит. Однако, насколько мне известно, C не требует реализаций для использования типов данных, которые удовлетворяют аксиомам Пеано, и не требует, чтобы реализация была вычислимой, так что это не должно быть проблемой.

Что должно произойти, если вы попытаетесь вывести нестандартное целое число? Ну, вы можете представить любое нестандартное целое число, используя нестандартную строку, поэтому просто передавайте цифры из передней части этой строки.

PyRulez
источник
Как будет выглядеть реализация?
Reinierpost
@reinierpost Я предполагаю, что это будет представлять данные с использованием некоторой исчисляемой нестандартной модели PA. Он будет вычислять арифметические операции с использованием степени PA . Я думаю, что любая такая модель должна обеспечивать правильную реализацию языка Си.
PyRulez
Извините, это не работает. sizeof(t)само по себе является значением типа size_t, поэтому оно является натуральным целым числом от 0 до SIZE_MAX.
Жиль "ТАК - перестань быть злым"
@Gilles SIZE_MAX тоже будет нестандартным.
PyRulez
Это интересный подход. Обратите внимание, что вам также понадобится, например, intptr_t / uintptr_t / ptrdiff_t / intmax_t / uintmax_t, чтобы быть нестандартным. В C ++ это противоречит гарантиям продвижения вперед ... не уверен насчет C.
TLW
0

ИМО, сильным ограничением является то, что адресуемое пространство (через размер указателя) конечно, и это невозможно восстановить.

Можно утверждать, что память может быть «перенесена на диск», но в какой-то момент адресная информация сама превысит адресуемый размер.

Ив Дауст
источник
Разве это не главное в принятом ответе? Я не думаю, что это добавляет что-то новое к ответам на этот вопрос 2016 года.
Чи
@chi: нет, в принятом ответе не упоминается обмен на внешнюю память, что можно считать обходным решением.
Ив Дауст
-1

На практике эти ограничения не имеют отношения к полноте по Тьюрингу. Реальное требование - позволить ленте быть произвольной длины, а не бесконечной. Это создало бы проблему остановки другого типа (как вселенная "вычисляет" ленту?)

Это так же фальшиво, как сказать: «Python не завершен по Тьюрингу, потому что вы не можете сделать список бесконечно большим».

[Редактировать: спасибо мистеру Уитледжу за разъяснение, как редактировать.]

доктор
источник
7
Я не думаю, что это отвечает на вопрос. Вопрос уже предвосхитил этот ответ и объяснил, почему он не действителен: «хотя стандарт C допускает, чтобы size_t был произвольно большим, он должен быть фиксированным на некоторой длине, и независимо от того, на какой длине он зафиксирован, он по-прежнему конечен ». Есть ли у вас ответ на этот аргумент? Я не думаю, что мы можем считать вопрос ответом, если ответ не объясняет, почему этот аргумент неправильный (или правильный).
DW
5
В любой момент времени значение типа size_tконечно. Проблема в том, что вы не можете установить границу, size_tкоторая действительна на протяжении всего вычисления: для любой грани программа может ее переполнить. Но язык C утверждает, что существует предел для size_t: в данной реализации он может расти только до sizeof(size_t)байтов. Также будь милым . Сказать, что люди, которые критикуют вас, «не могут думать самостоятельно» - это грубо.
Жиль "ТАК ... перестать быть злым"
1
Это правильный ответ. Токарный станок не требует бесконечной ленты, он требует «произвольно длинной» ленты. То есть, вы можете предположить, что лента настолько длинна, насколько это необходимо для завершения вычисления. Вы также можете предположить, что ваш компьютер имеет столько памяти, сколько ему нужно. Бесконечная лента абсолютно не требуется, потому что любое вычисление, которое останавливается за конечное время, не может использовать бесконечное количество ленты.
Джеффри Л Уитледж
Этот ответ показывает, что для каждой TM вы можете написать реализацию C с достаточной длиной указателя, чтобы смоделировать ее. Однако невозможно написать одну реализацию C, которая может имитировать любую TM. Таким образом, спецификация запрещает, чтобы любая конкретная реализация была T-полной. Само по себе это не T-complete, потому что длина указателя фиксирована.
1
Это еще один правильный ответ, который едва заметен из-за неспособности большинства людей в этом сообществе. Между тем, принятый ответ является ложным, и его секция комментариев защищена модераторами, удаляющими критические комментарии. Пока, cs.stackexchange.
xamid
-1

Съемные носители позволяют нам обойти проблему неограниченной памяти. Возможно, люди подумают, что это злоупотребление, но я думаю, что все в порядке и, по сути, неизбежно в любом случае.

Исправить любую реализацию универсальной машины Тьюринга. Для ленты мы используем съемные носители. Когда головка стекает с конца или начала текущего диска, аппарат предлагает пользователю вставить следующий или предыдущий. Мы можем использовать специальный маркер для обозначения левого конца моделируемой ленты или иметь ленту, которая не ограничена в обоих направлениях.

Ключевым моментом здесь является то, что все, что должна делать программа на C, конечно. Компьютеру требуется только достаточно памяти для симуляции автомата, и он size_tдолжен быть достаточно большим, чтобы можно было адресовать тот (на самом деле, довольно маленький) объем памяти и дисков, которые могут иметь любой фиксированный конечный размер. Поскольку пользователю предлагается только вставить следующий или предыдущий диск, нам не нужно неограниченно большие целые числа, чтобы сказать: «Пожалуйста, вставьте диск с номером 123456 ...»

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

Дэвид Ричерби
источник
3
Я бы сказал, что если определение C не требует такого неограниченного внешнего хранилища, то это не может быть принято как доказательство полноты по Тьюрингу. (ISO 9899, ​​конечно, не требует, чтобы он был написан для разработки в реальном мире.) Меня беспокоит то, что, если мы примем это, по аналогичным соображениям мы можем утверждать, что DFA завершены по Тьюрингу, поскольку их можно использовать водить голову над лентой (внешний накопитель).
Чи
@ Чи, я не понимаю, как следует аргумент DFA. Весь смысл DFA в том, что он имеет доступ только для чтения к хранилищу. Если вы позволите ему «загнать голову через ленту», разве это не машина Тьюринга?
Дэвид Ричерби
2
Действительно, я немного придираюсь к этому. Суть в том, почему можно добавить «ленту» в C, позволить C моделировать DFA и использовать этот факт, чтобы утверждать, что C завершен по Тьюрингу, когда мы не можем сделать то же самое с DFA? Если C не может самостоятельно реализовать неограниченную память, его не следует считать завершенным по Тьюрингу. (Я бы по-прежнему назвал это «морально» завершением по Тьюрингу, по крайней мере, поскольку границы настолько велики, что на практике они не имеют значения в большинстве случаев). Я думаю, что для окончательного решения вопроса потребуется строгая формальная спецификация C (стандарт ISO не достаточен)
Чи
1
@chi Это нормально, потому что C включает в себя процедуры ввода-вывода файлов. DFA нет.
Дэвид Ричерби
1
C не полностью определяет, что делают эти подпрограммы - большая часть их семантики определяется реализацией. Реализация AC не требуется для хранения содержимого файла, например, я думаю, что он может вести себя так, как если бы каждый файл был, так сказать, «/ dev / null». Также не требуется хранить неограниченное количество данных. Я бы сказал, что ваш аргумент верен, если учесть, что делает подавляющее большинство реализаций C, и обобщить это поведение на идеальную машину. Если мы строго полагаемся только на определение C, забыв о практике, я не думаю, что оно справедливо.
Чи
-2

Выберите size_tбыть бесконечно большим

Вы можете выбрать size_tбыть бесконечно большим. Естественно, невозможно реализовать такую ​​реализацию. Но это не удивительно, учитывая конечную природу мира, в котором мы живем.

Практические последствия

Но даже если бы можно было реализовать такую ​​реализацию, возникли бы практические проблемы. Рассмотрим следующее утверждение C:

printf("%zu\n",SIZE_MAX);

SIZE_MAXSIZE_MAXО(2sяZе_T)size_tSIZE_MAXprintf

К счастью, для наших теоретических целей я не смог найти в спецификации никаких требований, которые гарантировали бы printfпрекращение для всех входных данных. Итак, насколько мне известно, мы не нарушаем здесь спецификацию C.

О вычислительной полноте

Осталось доказать, что наша теоретическая реализация является Тьюринг-Полной . Мы можем показать это, внедрив «любую машину Тьюринга с одной лентой».

Большинство из нас, вероятно, внедрили Машину Тьюринга как школьный проект. Я не буду вдаваться в подробности конкретной реализации, но вот часто используемая стратегия:

  • Количество состояний, количество символов и таблица переходов состояний фиксированы для любой машины. Таким образом, мы можем представлять состояния и символы в виде чисел, а таблицу переходов состояний - в виде двумерного массива.
  • Лента может быть представлена ​​в виде связанного списка. Мы можем использовать либо один двойной связанный список, либо два одинарных связанных списка (по одному для каждого направления от текущей позиции).

Теперь посмотрим, что требуется для реализации такой реализации:

  • Способность представлять некоторый фиксированный, но произвольно большой набор чисел. Чтобы представить любое произвольное число, мы также выбираем MAX_INTбыть бесконечным. (В качестве альтернативы мы могли бы использовать другие объекты для представления состояний и символов.)
  • Возможность создания сколь угодно большого связного списка для нашей ленты. Еще раз, нет никаких ограничений на размер. Это означает, что мы не можем создать этот список заранее, так как мы бы потратили навсегда только на создание нашей ленты. Но мы можем построить этот список постепенно, если мы используем динамическое выделение памяти. Мы можем использовать malloc, но есть еще кое-что, что мы должны рассмотреть:
    • Спецификация C позволяет mallocпотерпеть неудачу, если, например, доступная память была исчерпана. Таким образом, наша реализация по-настоящему универсальна только в том случае, если mallocникогда не потерпит неудачу
    • Однако, если наша реализация запускается на машине с бесконечной памятью, то нет необходимости mallocв сбое. Без нарушения стандарта C наша реализация гарантирует, что mallocникогда не подведет.
  • Возможность разыменования указателей, элементов массива поиска и доступа к членам узла связанного списка.

Таким образом, приведенный выше список - это то, что необходимо для реализации машины Тьюринга в нашей гипотетической реализации на Си. Эти функции должны быть прекращены. Однако все остальное может быть прекращено (если это не требуется стандартом). Это включает в себя арифметику, IO и т. Д.

Натан Дэвис
источник
6
Что бы printf("%zu\n",SIZE_MAX);напечатать на такой реализации?
Руслан
1
@ Руслан, такая реализация невозможна, как невозможно реализовать машину Тьюринга. Но если бы такая реализация была возможной, я представляю, что она напечатала бы некоторое десятичное представление бесконечно большого числа - предположительно, бесконечный поток десятичных цифр.
Натан Дэвис
2
@NathanDavis Возможно реализовать машину Тьюринга. Хитрость в том, что вам не нужно создавать бесконечную ленту - вы просто строите использованную часть ленты постепенно, по мере необходимости.
Жиль "ТАК ... перестать быть злым"
2
@ Жиль: В этой конечной вселенной, в которой мы живем, невозможно реализовать машину Тьюринга.
gnasher729
1
@NathanDavis Но если вы это сделаете, то вы изменились sizeof(size_t)(или CHAR_BITS). Вы не можете выйти из нового состояния, вам нужно начать заново, но выполнение программы может быть другим, теперь, когда эти константы разные
Жиль "ТАК - перестань быть злым"
-2

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

Для этого есть обходной путь, хотя я не уверен, совпадает ли это с ISO C.

Предположим, у вас есть машина с бесконечной памятью. Таким образом, вы не ограничены размером указателя. У вас все еще есть ваш тип size_t. Если вы спросите меня, что такое sizeof (size_t), ответ будет просто sizeof (size_t). Если вы спросите, например, больше ли это 100, ответ будет положительным. Если вы спросите, что такое sizeof (size_t) / 2, как вы могли догадаться, ответ по-прежнему sizeof (size_t). Если вы хотите распечатать его, мы можем договориться о выводе. Разница между этими двумя может быть NaN и так далее.

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

PS Распределение памяти sizeof (size_t) все еще возможно, вам нужен только исчисляемый размер, поэтому допустим, что вы берете все четы (или похожий трюк).

Евгений
источник
1
«Разница этих двух может быть NaN». Нет, этого не может быть. В C. не существует такого понятия, как NaN целочисленного типа
TLW
Согласно стандарту, sizeofдолжен вернуть size_t. Таким образом, вы должны выбрать определенное значение.
Драконис
-4

Да, это.

1. Цитируемый ответ

В качестве реакции на большое количество отрицательных ответов на мои (и другие) правильные ответы - по сравнению с пугающе высоким подтверждением ложных ответов - я искал менее теоретически глубокое альтернативное объяснение. Я нашел это . Я надеюсь, что это покрывает некоторые из здесь распространенных ошибок, так что немного больше понимания. Существенная часть аргумента:

[...] Его аргумент таков: предположим, кто-то написал определенную завершающую программу, которой может потребоваться при ее выполнении до некоторого произвольного объема памяти. Не изменяя эту программу, можно апостериорно реализовать часть компьютерного оборудования и его компилятор C, который обеспечивает достаточно памяти для размещения этого вычисления. Это может потребовать расширения ширины char (через CHAR_BITS) и / или указателей (через size_t), но программу не нужно будет модифицировать. Поскольку это возможно, C действительно является Turing-Complete для завершения программ.

Сложность этого аргумента в том, что он работает только при рассмотрении завершающих программ. У завершающих программ есть это замечательное свойство, заключающееся в том, что они имеют статическую верхнюю границу для своего требования к хранилищу, которую можно определить экспериментальным путем, запустив программу над желаемым вводом с увеличивающимися размерами хранилища, пока она не «подойдет».

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

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

2. Мой оригинальный ответ

Существуют широко распространенные противоречия между математическими понятиями в теоретической информатике (такими как полнота по Тьюрингу) и их практическим применением, то есть методами в практической информатике. Полнота по Тьюрингу не является свойством физически существующих машин или моделей, ограниченных в пространстве и времени. Это просто абстрактный объект, описывающий свойства математических теорий.

C99 полон по Тьюрингу независимо от ограничений на основе реализации, как и практически любой другой распространенный язык программирования, поскольку он способен выражать функционально полный набор логических связок и в принципе имеет доступ к неограниченному объему памяти. Люди указали, что C явно ограничивает доступ к произвольной памяти, но это ничто, что никто не мог бы обойти, так как это дополнительно заявленные ограничения в стандарте C, в то время как полнота по Тьюрингу уже подразумевается без них :

Вот очень простая вещь о логических системах, которой должно хватить для неконструктивного доказательства. Рассмотрим исчисление с некоторыми аксиомными схемами и правилами, такими, что набор логических следствий равен X. Теперь, если вы добавите некоторые правила или аксиомы, набор логических последствий возрастает, то есть должен быть надмножеством X. Вот почему, например, например, , модальная логика S4 правильно содержится в S5, Точно так же, когда у вас есть под спецификация, полная по Тьюрингу, но вы добавляете некоторые ограничения сверху, они не предотвращают каких-либо последствий в X, т. Е. Должен быть способ обойти все ограничения. Если вы хотите не полный по Тьюрингу язык, исчисление должно быть сокращено, а не расширено. Расширения, которые утверждают, что что-то было бы невозможно, но на самом деле, только добавляют несогласованность. Эти несоответствия в стандарте C могут не иметь практических последствий, так же как полнота по Тьюрингу не связана с практическим применением.

Моделирование произвольных чисел на основе глубины рекурсии (т. Е. Это ; с возможностью поддержки нескольких чисел через планирование / псевдопотоки; теоретического ограничения глубины рекурсии в C не существует ) или использование файлового хранилища для имитации неограниченной памяти программы ( идея ) вероятно, только две из бесконечных возможностей конструктивно доказать полноту по Тьюрингу C99. Следует помнить, что для вычислимости сложность времени и пространства не имеет значения. В частности, допущение ограниченной среды для фальсификации полноты по Тьюрингу является просто циклическим рассуждением, поскольку это ограничение исключает все проблемы, которые превышают предполагаемую границу сложности.

( ПРИМЕЧАНИЕ . Я написал этот ответ только для того, чтобы не дать людям получить математическую интуицию из-за ограниченного мышления, ориентированного на приложения. Очень жаль, что большинство учеников прочтут ложный принятый ответ из-за того, что за него проголосовали фундаментальные недостатки рассуждения, так что больше людей распространят такие ложные убеждения. Если вы отрицаете этот ответ, вы просто являетесь частью проблемы.)

Xamid
источник
4
Я не следую вашему последнему абзацу. Вы утверждаете, что добавление ограничений увеличивает выразительную силу, но это явно не так. Ограничения могут только уменьшить выразительную силу. Например, если вы берете C и добавляете ограничение, согласно которому ни одна программа не может получить доступ к хранилищу объемом более 640 КБ (любого типа), то вы превратили его в причудливый конечный автомат, который явно не является полным по Тьюрингу.
Дэвид Ричерби
3
Если у вас есть фиксированный объем памяти, вы не можете имитировать ничего, что требует больше ресурсов, чем у вас есть. Существует только конечное число конфигураций, в которых может находиться ваша память, а это означает, что есть только конечное число вещей, которые вы можете сделать.
Дэвид Ричерби
2
Я не понимаю, почему вы ссылаетесь на «физически существующие машины». Обратите внимание, что полнота по Тьюрингу является свойством математической вычислительной модели, а не физических систем. Я согласен, что никакая физическая система, будучи конечным объектом, не может приблизиться к мощности машин Тьюринга, но это не имеет значения. Мы все еще можем взять любой язык программирования, рассмотреть математическое определение его семантики и проверить, завершен ли этот математический объект по Тьюрингу. Игра жизни Конвея является мощной по Тьюрингу, даже если нет никакой физической реализации.
Чи
2
@xamid Если у вас есть сомнения по поводу политики модерации на этом сайте, отправьте ее в Computer Science Meta . До тех пор, пожалуйста, будьте милы . Вербальные оскорбления других не допустимы. (Я удалил все комментарии, которые не имеют отношения к предмету под рукой.)
Рафаэль
2
Вы говорите, что изменение ширины указателя не изменит программу, но программы могут считывать ширину указателя и делать с этим значением все, что захотят. То же самое для CHAR_BITS.
Драконис