Максимальная вычислительная мощность реализации C

28

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

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

Для целей этого вопроса нет внешнего хранилища. Единственный ввод / вывод, который вы можете выполнить, - getchar(для чтения ввода программы) и putchar(для записи вывода программы). Также любая программа, которая вызывает неопределенное поведение, является недопустимой: допустимая программа должна иметь свое поведение, определенное спецификацией C, плюс описание реализации определенных поведением реализаций, приведенное в приложении J (для C99). Обратите внимание, что вызов библиотечных функций, которые не упомянуты в стандарте, является неопределенным поведением.

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

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

Это верно? Можете ли вы найти более мощную реализацию C? Существует ли полная реализация Тьюринга C?

Жиль "ТАК - перестань быть злым"
источник
4
@ Дэйв: Как объяснил Жиль, кажется, что у вас может быть неограниченная память, но нет способа напрямую с ней справиться.
Юкка Суомела
2
Из вашего объяснения кажется, что любая реализация на C может быть запрограммирована только на прием языков, принимаемых детерминированными автоматами, которые слабее, чем даже языки без контекста. Однако, на мой взгляд, это наблюдение малоинтересно, поскольку речь идет о неправильном применении асимптотики.
Уоррен Шуди
3
Следует помнить, что существует множество способов вызвать «поведение, определяемое реализацией» (или «поведение, не определенное»). И вообще, реализация может предоставлять, например, библиотечные функции, которые предоставляют функциональность, которая не определена в стандарте C. Все они предоставляют «лазейки», через которые вы можете получить доступ, скажем, к машине Тьюринга. Или даже что-то намного более сильное, как оракул, который решает проблему остановки. Глупый пример: определяемое реализацией поведение целочисленных переполнений со знаком или преобразований целочисленных указателей может позволить вам получить доступ к такому оракулу.
Юкка Суомела
7
Кстати, было бы неплохо добавить тег «развлекательный» (или что-то, что мы используем для смешных головоломок), чтобы люди не воспринимали это слишком серьезно. Это, очевидно, «неправильный вопрос», но тем не менее я нашел его забавным и интригующим. :)
Юкка Суомела
2
@Jukka: Хорошая идея. Например, переполнение с помощью X = запись X / 3 на ленту и перемещение в направлении X% 3, underflow = запуск сигнала, соответствующего символу на ленте. Это похоже на оскорбление, но это определенно в духе моего вопроса. Не могли бы вы написать это как ответ? (@others: Не то, чтобы я хотел отговорить других таких умных предложений!)
Жиль, ТАК - перестань быть злым "

Ответы:

8

Как отмечено в вопросе, стандарт C требует, чтобы существовало значение UCHAR_MAX, чтобы каждая переменная типа unsigned charвсегда содержала значение от 0 до UCHAR_MAX включительно. Кроме того, требуется, чтобы каждый динамически размещенный объект был представлен последовательностью байтов, которая может быть идентифицирована с помощью указателя типа unsigned char*, и чтобы существовала константа sizeof(unsigned char*), так чтобы каждый указатель этого типа был идентифицируем с помощью последовательности sizeof(unsigned char *)значений типа unsigned char. Таким образом, число объектов, которые могут быть динамически распределены одновременно, жестко ограничено . Ничто не помешает теоретическому компилятору присваивать значения этих констант для поддержки более 10 10 10 объектов, но с теоретической точки зрения наличие любой границы, независимо от ее размера, означает, что что-то не бесконечно.UCHAR_MAXsizeof(unsigned char)101010

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

Однако существует еще одна потенциальная проблема: требуется, чтобы, если программа проверяла базовые последовательности значений символов фиксированной длины, связанные с двумя указателями на разные объекты, эти последовательности должны быть уникальными. Потому что есть только UCHAR_MAXsizeof(unsigned char)возможные последовательности символьных значений, любая программа, которая создала количество указателей на отдельные объекты, превышающие его, не могла бы соответствовать стандарту C, если код когда-либо проверял последовательность символов, связанных с этими указателями . Однако в некоторых случаях для компилятора будет возможно определить, что ни один код не собирался проверять последовательность символов, связанных с указателем. Если бы каждый символ «char» был способен удерживать любое конечное целое число, а память машины представляла собой счетно-бесконечную последовательность целых чисел [с помощью машины Тьюринга с неограниченной лентой, можно было бы эмулировать такую ​​машину, хотя она была бы очень медленной], тогда было бы действительно возможно сделать C тьюрингово-полным языком.

Supercat
источник
С такой машиной, что бы вернуть sizeof (char)?
TLW
1
@TLW: То же, что и на любой другой машине: 1. Макросы CHAR_BITS и CHAR_MAX были бы немного более проблематичными; Стандарт не допускает концепцию типов, которые не имеют границ.
суперкат
Ой, я имел в виду CHAR_BITS, как вы сказали, извините.
TLW
7

С (дополнительной) библиотекой потоков C11 можно сделать полную реализацию Turing при неограниченной глубине рекурсии.

Создание нового потока дает второй стек; Для полноты по Тьюрингу достаточно двух стеков. Один стек представляет то, что слева от головы, другой стек, что справа.

Джаред
источник
Но машины Тьюринга с лентой, бесконечно движущимися только в одном направлении, так же мощны, как машины Тьюринга с лентой, бесконечно движущимися в двух направлениях. Кроме того, планировщик может смоделировать несколько потоков. В любом случае, нам даже не нужна библиотека потоков.
Xamid
3

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

  • определить структуру, которая может использоваться как двойной связанный список для представления ленты
    typdef struct {
      cell_t * pred; // ячейка слева
      cell_t * succ; // ячейка справа
      int val; // значение ячейки
    } cell_t 

headБудет указатель на cell_tструктуру

  • определить структуру, которая может быть использована для хранения текущего состояния и флага
    typedef struct {
      Int State;
      int flag;
    } info_t 
  • затем определите функцию одного цикла, которая имитирует Universal TM, когда заголовок находится между границами двойного связанного списка; когда голова достигнет границы, установите флаг структуры info_t (HIT_LEFT, HIT_RIGHT) и вернитесь:
void simulate_UTM (cell_t * head, info_t * info) {
  while (true) {
    head-> val = UTM_nextsymbol [info-> state, head-> val]; // написать символ
    info-> state = UTM_nextstate [info-> state, head-> val]; // следующее состояние
    if (info-> state == HALT_STATE) {// напечатать, если принимает и выходит из программы
       putchar ((info-> state == ACCEPT_STATE)? '1': '0');
       Выход (0);
    }
    int move = UTM_nextmove [info-> state, head-> val];
    if (move == MOVE_LEFT) {
      голова = голова-> пред; // движение влево
      if (head == NULL) {info-> flag = HIT_LEFT; возвращение; }
    } еще {
      голова = голова-> сукц; // переместить вправо
      if (head == NULL) {info-> flag = HIT_RIGHT; возвращение; }
    }
  } // все еще на границе ... продолжаем
}
  • затем определите рекурсивную функцию, которая сначала вызывает процедуру моделирования UTM, а затем рекурсивно вызывает себя, когда лента должна быть расширена; когда лента должна быть расширена сверху (HIT_RIGHT), нет проблем, когда она должна быть смещена снизу (HIT_LEFT), просто сдвиньте значения ячеек вверх, используя двойной связанный список:
накопитель пустот (cell_t * top, cell_t * bottom, cell_t * head, info_t * info) {
  simulate_UTM (голова, информация);
  cell_t newcell; // новая ячейка
  newcell.pred = top; // обновляем двойной связанный список новой ячейкой
  newcell.succ = NULL;
  top-> succ = & newcell;
  newcell.val = EMPTY_SYMBOL;

  переключатель (info-> hit) {
    case HIT_RIGHT:
      накопитель (& newcell, нижний, newcell, информация);
      перемена;
    case HIT_BOTTOM:
      cell_t * tmp = newcell;
      while (tmp-> pred! = NULL) {// сдвинуть вверх значения
        tmp-> val = tmp-> pred-> val;
        tmp = tmp-> pred;
      }
      tmp-> val = EMPTY_SYMBOL;
      накопитель (& newcell, снизу, снизу, информация);
      перемена;
  }
}
  • исходная лента может быть заполнена простой рекурсивной функцией, которая создает двойной связанный список и затем вызывает stackerфункцию, когда она читает последний символ входной ленты (используя readchar)
void init_tape (cell_t * top, cell_t * bottom, info_t * info) {
  cell_t newcell;
  int c = readchar ();
  накопитель if (c == END_OF_INPUT) (& top, bottom, bottom, info); // больше нет символов, начало
  newcell.pred = top;
  if (top! = NULL) top.succ = & newcell; иначе bottom = & newcell;
  init_tape (& newcell, bottom, info);
}

РЕДАКТИРОВАТЬ: подумав немного, есть проблема с указателями ...

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

Марцио де Биаси
источник
3
stackernewcellstacker2n/sns=sizeof(cell_t)
@ Жиль: ты прав (см. Мои правки); если вы ограничите глубину рекурсии, вы получите конечный автомат
Марцио Де Биаси
@MarzioDeBiasi Нет, он не прав, поскольку ссылается на конкретную реализацию, которую стандарт не предполагает. На самом деле, не существует теоретический предел глубины рекурсии в C . Выбор использования реализации на основе ограниченного стека ничего не говорит о теоретических ограничениях языка. Но полнота по Тьюрингу является теоретическим пределом.
xamid
0

Пока у вас есть неограниченный размер стека вызовов, вы можете кодировать вашу ленту в стеке вызовов и осуществлять произвольный доступ к ней, перематывая указатель стека, не возвращаясь из вызовов функций.

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

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

Я бы даже предположил, что число языков, которые вы можете распознать, конечно (даже если сами языки могут быть бесконечными, например, a*это нормально, но b^kработает только для конечного числа ks).

РЕДАКТИРОВАТЬ : Это не так, поскольку вы можете закодировать текущее состояние в дополнительных функциях, чтобы вы могли по-настоящему распознать ВСЕ обычные языки.

Скорее всего, вы можете получить все языки типа 2 по той же причине, но я не уверен, что удастся ли вам поместить и состояние, и стековое согласие в стек вызовов. Но, в общем, вы можете эффективно забыть об оперативной памяти, поскольку вы всегда можете масштабировать размер автомата, чтобы ваш алфавит превышал пропускную способность оперативной памяти. Так что, если бы вы могли смоделировать TM только со стеком, Type-2 был бы равен Type-0, не так ли?

битовая
источник
5
Что такое «указатель стека»? (Обратите внимание, что слово «стек» не встречается в стандарте C.) Мой вопрос касается C как класса формальных языков, а не реализации C на компьютере (которые, очевидно, являются конечными автоматами). Если вы хотите получить доступ к стеку вызовов, вы должны сделать это так, как это предусмотрено языком. Например, принимая адрес аргументов функции - но любая данная реализация имеет только конечное число адресов, что затем ограничивает глубину рекурсии.
Жиль "ТАК - перестать быть злым"
Я изменил свой ответ, чтобы исключить использование указателя стека.
битовая
1
Я не понимаю, куда вы идете с вашим пересмотренным ответом (кроме изменения формулировки с вычислимых функций на признанные языки). Поскольку у функций тоже есть адрес, вам нужна достаточно большая реализация для реализации любого данного конечного автомата. Вопрос заключается в том, можно ли и как реализацию C сделать больше (скажем, реализовать универсальную машину Тьюринга) , не опираясь на ООН определенного поведения.
Жиль "ТАК - перестань быть злым"
0

Я однажды подумал об этом и решил попробовать реализовать неконтекстно-свободный язык, используя ожидаемую семантику; Ключевой частью реализации является следующая функция:

void *it;

void read_triple(void *back)
{
  if(read_a()) read_triple(&back);
  else reject();
  for(it = back; it != NULL; it = *it)
     if(!read_b()) reject();
  if(read_c()) return;
  else reject();
}

{anbncn}

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

Фиксированная версия:

void *it;

void read_triple(void *back)
{
  if(read_a()) read_triple(&back);
  else for(it = back; it != NULL; it = * (void **) it)
     if(!read_b()) reject();
  if(read_c()) return;
  else reject();
}
Бен Стандевен
источник
Ну, не принципиальная ошибка, но it = *itдолжна быть заменена it = * (void **) it, так как в противном случае *itимеет тип void.
Бен Стандевен
Я был бы очень удивлен, если бы такое перемещение стека вызовов было бы определенным поведением в C.
Раду ГРИГОР
О, это не сработает, потому что первый 'b' вызывает сбой read_a () и, следовательно, вызывает отклонение.
Бен Стандевен
Но вполне допустимо перемещать стек вызовов таким способом, поскольку стандарт C говорит: «Для такого объекта [то есть объекта с автоматическим хранением], который не имеет тип массива переменной длины, его время жизни простирается от входа в блок с который ассоциируется до тех пор, пока выполнение этого блока не завершится каким-либо образом. (Ввод закрытого блока или вызов функции приостанавливает, но не прекращает выполнение текущего блока.) Если блок вводится рекурсивно, то новый экземпляр объекта создается каждый раз. " Таким образом, каждый вызов read_triple создаст новый указатель, который можно использовать в рекурсии.
Бен Стандевен
2
2CHAR_BITsizeof(char*)
0

В соответствии с ответом @ supercat:

Утверждения о неполноте C, кажется, сосредоточены вокруг того, что разные объекты должны иметь разные адреса, а набор адресов предполагается конечным. Как пишет @supercat

Как отмечено в вопросе, стандарт C требует, чтобы существовало такое значение UCHAR_MAX, чтобы каждая переменная типа unsigned char всегда содержала значение от 0 до UCHAR_MAXвключительно. Кроме того, требуется, чтобы каждый динамически размещенный объект был представлен последовательностью байтов, которая может быть идентифицирована с помощью указателя типа unsigned char *, и чтобы существовала константа sizeof(unsigned char*), так чтобы каждый указатель этого типа мог быть идентифицирован с помощью последовательности sizeof(unsigned char *)значений типа unsigned голец.

unsigned char*N{0,1}sizeof(unsigned char*){0,1}sizeof(unsigned char)Nsizeof(unsigned char*)Nω

На этом этапе следует проверить, что стандарт Си действительно допускает это.

sizeofZ

Алексей Б.
источник
1
Многие операции над целочисленными типами определены так, чтобы иметь результат, который «уменьшается по модулю на единицу больше максимального значения, представляемого в типе результата». Как это будет работать, если этот максимум является не конечным порядковым числом?
Жиль "ТАК - перестань быть злым"
@ Жиль Это интересный момент. На самом деле не ясно, какова будет семантика uintptr_t p = (uintptr_t)sizeof(void*)(помещая \ omega в нечто, содержащее целые числа без знака). Не знаю. Мы можем избежать определения результата равным 0 (или любому другому числу).
Алексей Б.
1
uintptr_tтоже должно быть бесконечным. Имейте в виду, этот тип является необязательным - но если у вас есть бесконечное количество различных значений указателя, то он sizeof(void*)также должен быть бесконечным, поэтому size_tдолжен быть бесконечным. Однако мое возражение по поводу сокращения по модулю не столь очевидно - оно вступает в действие только при переполнении, но если вы разрешаете бесконечные типы, они могут никогда не переполниться. Но с другой стороны, каждый тип имеет минимальное и максимальное значения, что, насколько я могу судить, подразумевает, что они UINT_MAX+1должны переполняться.
Жиль "ТАК - перестань быть злым"
Также хороший момент. Действительно, мы получаем набор типов (указатели и size_t), которые должны быть ℕ, ℤ или некоторую конструкцию на их основе (для size_t, если бы было что-то вроде ℕ ∪ {ω}). Теперь, если для некоторых из этих типов стандарт требует макроса, определяющего максимальное значение (PTR_MAX или что-то в этом роде), все станет волосатым. Но до сих пор мне удавалось финансировать только требование макросов MIN / MAX для типов без указателей.
Алексей Б.
Другая возможность для исследования - определить оба size_tтипа указателя, чтобы быть ℕ ∪ {ω}. Это избавляет от проблемы мин / макс. Проблема с семантикой переполнения все еще остается. Какая должна быть семантика, uint x = (uint)ωмне не ясно. Опять же, мы могли бы случайно взять 0, но это выглядит немного уродливо.
Алексей Б.