Я пытался объяснить кому-то, что C завершена по Тьюрингу, и понял, что на самом деле не знаю, действительно ли он технически завершен по Тьюрингу. (C как в абстрактной семантике, а не как в реальной реализации.)
«Очевидный» ответ (грубо говоря: он может адресовать произвольный объем памяти, поэтому он может эмулировать машину с ОЗУ, поэтому он завершается по Тьюрингу), на самом деле, насколько я могу судить, не совсем корректен, хотя стандарт C позволяет для того, чтобы size_t был сколь угодно большим, он должен быть фиксирован на некоторой длине, и независимо от того, на какой длине он фиксирован, он по-прежнему конечен. (Другими словами, хотя вы могли бы при произвольной остановке машины Тьюринга выбрать длину size_t так, чтобы она работала «правильно», нет способа выбрать длину size_t так, чтобы все останавливающие машины Тьюринга работали правильно).
Итак: завершен ли C99 по Тьюрингу?
Ответы:
Я не уверен, но я думаю, что ответ - нет, по довольно тонким причинам. Я спросил о теоретической информатике несколько лет назад и не получил ответа, который выходит за рамки того, что я здесь представлю.
В большинстве языков программирования вы можете моделировать машину Тьюринга:
Конкретная реализация, работающая на компьютере, могла бы исчерпать память, если бы лента стала слишком длинной, но идеальная реализация могла бы точно выполнять машинную программу Тьюринга. Это можно сделать ручкой и бумагой или покупкой компьютера с большим объемом памяти и компилятором, ориентированным на архитектуру с большим количеством битов на слово и т. Д., Если программе когда-либо не хватает памяти.
Это не работает в C, потому что невозможно иметь связанный список, который может расти вечно: всегда есть какое-то ограничение на количество узлов.
Чтобы объяснить почему, мне сначала нужно объяснить, что такое реализация на Си. C на самом деле семейство языков программирования. Стандарт ISO C (точнее, конкретная версия этого стандарта) определяет (с уровнем формальности, который допускает английский язык) синтаксис и семантику семейства языков программирования. C имеет много неопределенного поведения и поведения, определенного для реализации, «Реализация» C кодифицирует все поведение, определяемое реализацией (список вещей для кодификации приведен в приложении J для C99). Каждая реализация C - это отдельный язык программирования. Обратите внимание, что значение слова «реализация» немного своеобразно: оно действительно означает языковой вариант, может быть несколько разных программ компилятора, которые реализуют один и тот же языковой вариант.
В данной реализации C байт имеет возможных значения CHAR_BIT . Все данные могут быть представлены в виде массива байтов: тип имеет максимум 2 CHAR_BIT × sizeof (t) возможных значений. Это число варьируется в разных реализациях C, но для данной реализации C оно является константой.2CHAR_BIT 2CHAR_BIT×sizeof(t)
t
В частности, указатели могут принимать только . Это означает, что существует конечное максимальное количество адресуемых объектов.2CHAR_BIT×sizeof(void*)
Значения
CHAR_BIT
иsizeof(void*)
являются наблюдаемыми, поэтому, если у вас не хватает памяти, вы не можете просто возобновить работу своей программы с большими значениями для этих параметров. Вы будете запускать программу под другим языком программирования - другой реализацией Си.Если программы на языке могут иметь только ограниченное число состояний, то язык программирования не более выразителен, чем конечные автоматы. Фрагмент C, который ограничен адресным хранилищем, допускает самое большее состояний программы, где n - размер абстрактного синтаксического дерева программы (представляющего состояние потока управления), поэтому это Программа может быть смоделирована конечным автоматом с таким количеством состояний. Если C более выразителен, это должно быть сделано с помощью других функций.n × 2CHAR_BIT × sizeof (void *) N
C напрямую не навязывает максимальную глубину рекурсии. Реализация может иметь максимум, но также может не иметь. Но как мы общаемся между вызовом функции и ее родителем? Аргументы бесполезны, если они адресуемы, потому что это косвенно ограничило бы глубину рекурсии: если у вас есть функция,
int f(int x) { … f(…) …}
то все вхождения вx
активных кадрахf
имеют свой собственный адрес, и поэтому число вложенных вызовов ограничено числом возможных адресов дляx
.Программа AC может использовать неадресуемые хранилища в виде
register
переменных. «Нормальные» реализации могут иметь только небольшое конечное количество переменных, которые не имеют адреса, но теоретически реализация может позволить неограниченный объемregister
памяти. В такой реализации вы можете делать неограниченное количество рекурсивных вызовов функции, пока ее аргумент естьregister
. Но поскольку аргументы таковыregister
, вы не можете сделать на них указатель, и поэтому вам необходимо явно копировать их данные: вы можете передавать только конечный объем данных, а не структуру данных произвольного размера, состоящую из указателей.С неограниченной глубиной рекурсии и ограничением, что функция может получать данные только от своего прямого вызывающего (
register
аргументы) и возвращать данные своему прямому вызывающему (возвращаемое значение функции), вы получаете мощность детерминированных автоматов выталкивания .Я не могу найти способ пойти дальше.
(Конечно, вы можете заставить программу хранить содержимое ленты внешне, через функции ввода / вывода файла. Но тогда вы не будете спрашивать, является ли C завершенным по Тьюрингу, но является ли C плюс бесконечная система хранения полным по Тьюрингу, чтобы ответ - скучное «да». Вы также можете определить хранилище как вызов оракула Тьюринга
fopen("oracle", "r+")
,fwrite
начальное содержимое ленты иfread
обратно конечное содержимое ленты.)источник
Добавление C99
va_copy
к API с переменным аргументом может дать нам задний ход к полноте по Тьюрингу. Поскольку становится возможным повторять список переменных аргументов более одного раза в функции, отличной от той, которая первоначально получила аргументы,va_args
можно использовать для реализации указатель без указателя.Конечно, реальная реализация API аргументов с переменным аргументом, вероятно, где-то будет иметь указатель, но в нашей абстрактной машине он может быть реализован с использованием магии.
Вот демонстрационная версия, реализующая 2-стопочный автомат с произвольными правилами перехода:
Примечание. Если
va_list
тип массива, то на самом деле существуют скрытые параметры указателя на функции. Так что, вероятно, было бы лучше изменить типы всехva_list
аргументов наwrapped_stack
.источник
va_list
переменныхstack
. Эти переменные должны иметь адрес&stack
, и мы можем иметь только ограниченное число из них.register
Может быть, это требование можно обойти, объявив каждую локальную переменную ?register
.int
быть обязательным иметь ограничение, если кто-то не использует ограничение илиsizeof(int)
?int
имеет значение между некоторыми конечными границамиINT_MIN
иINT_MAX
. И если значениеint
переполняет эти границы, происходит неопределенное поведение. С другой стороны, стандарт намеренно не требует, чтобы все объекты физически присутствовали в памяти по определенному адресу, поскольку это позволяет оптимизировать, например, сохранять объект в регистре, сохранять только часть объекта, представляя его иначе, чем стандарт макет или вообще его опуская, если он не нужен.Возможно, нестандартная арифметика?
Итак, похоже, что проблема заключается в конечном размере
sizeof(t)
. Тем не менее, я думаю, что знаю обходной путь.Насколько я знаю, C не требует реализации, чтобы использовать стандартные целые числа для своего целочисленного типа. Поэтому мы могли бы использовать нестандартную модель арифметики . Тогда мы установили
sizeof(t)
бы нестандартное число, и теперь мы никогда не достигнем его за конечное число шагов. Поэтому длина ленты машин Тьюринга всегда будет меньше «максимальной», так как максимум буквально невозможно достичь.sizeof(t)
просто не число в обычном смысле этого слова.Это одна из техничностей, конечно: теорема Тенненбаума . В нем говорится, что единственная модель арифметики Пеано является стандартной, что, очевидно, не подходит. Однако, насколько мне известно, C не требует реализаций для использования типов данных, которые удовлетворяют аксиомам Пеано, и не требует, чтобы реализация была вычислимой, так что это не должно быть проблемой.
Что должно произойти, если вы попытаетесь вывести нестандартное целое число? Ну, вы можете представить любое нестандартное целое число, используя нестандартную строку, поэтому просто передавайте цифры из передней части этой строки.
источник
sizeof(t)
само по себе является значением типаsize_t
, поэтому оно является натуральным целым числом от 0 доSIZE_MAX
.ИМО, сильным ограничением является то, что адресуемое пространство (через размер указателя) конечно, и это невозможно восстановить.
Можно утверждать, что память может быть «перенесена на диск», но в какой-то момент адресная информация сама превысит адресуемый размер.
источник
На практике эти ограничения не имеют отношения к полноте по Тьюрингу. Реальное требование - позволить ленте быть произвольной длины, а не бесконечной. Это создало бы проблему остановки другого типа (как вселенная "вычисляет" ленту?)
Это так же фальшиво, как сказать: «Python не завершен по Тьюрингу, потому что вы не можете сделать список бесконечно большим».
[Редактировать: спасибо мистеру Уитледжу за разъяснение, как редактировать.]
источник
size_t
конечно. Проблема в том, что вы не можете установить границу,size_t
которая действительна на протяжении всего вычисления: для любой грани программа может ее переполнить. Но язык C утверждает, что существует предел дляsize_t
: в данной реализации он может расти только доsizeof(size_t)
байтов. Также будь милым . Сказать, что люди, которые критикуют вас, «не могут думать самостоятельно» - это грубо.Съемные носители позволяют нам обойти проблему неограниченной памяти. Возможно, люди подумают, что это злоупотребление, но я думаю, что все в порядке и, по сути, неизбежно в любом случае.
Исправить любую реализацию универсальной машины Тьюринга. Для ленты мы используем съемные носители. Когда головка стекает с конца или начала текущего диска, аппарат предлагает пользователю вставить следующий или предыдущий. Мы можем использовать специальный маркер для обозначения левого конца моделируемой ленты или иметь ленту, которая не ограничена в обоих направлениях.
Ключевым моментом здесь является то, что все, что должна делать программа на C, конечно. Компьютеру требуется только достаточно памяти для симуляции автомата, и он
size_t
должен быть достаточно большим, чтобы можно было адресовать тот (на самом деле, довольно маленький) объем памяти и дисков, которые могут иметь любой фиксированный конечный размер. Поскольку пользователю предлагается только вставить следующий или предыдущий диск, нам не нужно неограниченно большие целые числа, чтобы сказать: «Пожалуйста, вставьте диск с номером 123456 ...»Я полагаю, что главным возражением, вероятно, будет участие пользователя, но это кажется неизбежным в любой реализации, потому что, кажется, нет другого способа реализации неограниченной памяти.
источник
Выберите
size_t
быть бесконечно большимВы можете выбрать
size_t
быть бесконечно большим. Естественно, невозможно реализовать такую реализацию. Но это не удивительно, учитывая конечную природу мира, в котором мы живем.Практические последствия
Но даже если бы можно было реализовать такую реализацию, возникли бы практические проблемы. Рассмотрим следующее утверждение C:
SIZE_MAX
SIZE_MAX
size_t
SIZE_MAX
printf
К счастью, для наших теоретических целей я не смог найти в спецификации никаких требований, которые гарантировали бы
printf
прекращение для всех входных данных. Итак, насколько мне известно, мы не нарушаем здесь спецификацию C.О вычислительной полноте
Осталось доказать, что наша теоретическая реализация является Тьюринг-Полной . Мы можем показать это, внедрив «любую машину Тьюринга с одной лентой».
Большинство из нас, вероятно, внедрили Машину Тьюринга как школьный проект. Я не буду вдаваться в подробности конкретной реализации, но вот часто используемая стратегия:
Теперь посмотрим, что требуется для реализации такой реализации:
MAX_INT
быть бесконечным. (В качестве альтернативы мы могли бы использовать другие объекты для представления состояний и символов.)malloc
, но есть еще кое-что, что мы должны рассмотреть:malloc
потерпеть неудачу, если, например, доступная память была исчерпана. Таким образом, наша реализация по-настоящему универсальна только в том случае, еслиmalloc
никогда не потерпит неудачуmalloc
в сбое. Без нарушения стандарта C наша реализация гарантирует, чтоmalloc
никогда не подведет.Таким образом, приведенный выше список - это то, что необходимо для реализации машины Тьюринга в нашей гипотетической реализации на Си. Эти функции должны быть прекращены. Однако все остальное может быть прекращено (если это не требуется стандартом). Это включает в себя арифметику, IO и т. Д.
источник
printf("%zu\n",SIZE_MAX);
напечатать на такой реализации?sizeof(size_t)
(илиCHAR_BITS
). Вы не можете выйти из нового состояния, вам нужно начать заново, но выполнение программы может быть другим, теперь, когда эти константы разныеОсновным аргументом здесь было то, что размер 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) все еще возможно, вам нужен только исчисляемый размер, поэтому допустим, что вы берете все четы (или похожий трюк).
источник
sizeof
должен вернутьsize_t
. Таким образом, вы должны выбрать определенное значение.Да, это.
1. Цитируемый ответ
В качестве реакции на большое количество отрицательных ответов на мои (и другие) правильные ответы - по сравнению с пугающе высоким подтверждением ложных ответов - я искал менее теоретически глубокое альтернативное объяснение. Я нашел это . Я надеюсь, что это покрывает некоторые из здесь распространенных ошибок, так что немного больше понимания. Существенная часть аргумента:
Короче говоря, потому что для каждой вычислимой функции есть решение на языке C (из-за неограниченных верхних границ), каждая вычислимая задача имеет программу на C, таким образом, C полна по Тьюрингу.
2. Мой оригинальный ответ
Существуют широко распространенные противоречия между математическими понятиями в теоретической информатике (такими как полнота по Тьюрингу) и их практическим применением, то есть методами в практической информатике. Полнота по Тьюрингу не является свойством физически существующих машин или моделей, ограниченных в пространстве и времени. Это просто абстрактный объект, описывающий свойства математических теорий.
C99 полон по Тьюрингу независимо от ограничений на основе реализации, как и практически любой другой распространенный язык программирования, поскольку он способен выражать функционально полный набор логических связок и в принципе имеет доступ к неограниченному объему памяти. Люди указали, что C явно ограничивает доступ к произвольной памяти, но это ничто, что никто не мог бы обойти, так как это дополнительно заявленные ограничения в стандарте C, в то время как полнота по Тьюрингу уже подразумевается без них :
Вот очень простая вещь о логических системах, которой должно хватить для неконструктивного доказательства. Рассмотрим исчисление с некоторыми аксиомными схемами и правилами, такими, что набор логических следствий равен X. Теперь, если вы добавите некоторые правила или аксиомы, набор логических последствий возрастает, то есть должен быть надмножеством X. Вот почему, например, например, , модальная логика S4 правильно содержится в S5, Точно так же, когда у вас есть под спецификация, полная по Тьюрингу, но вы добавляете некоторые ограничения сверху, они не предотвращают каких-либо последствий в X, т. Е. Должен быть способ обойти все ограничения. Если вы хотите не полный по Тьюрингу язык, исчисление должно быть сокращено, а не расширено. Расширения, которые утверждают, что что-то было бы невозможно, но на самом деле, только добавляют несогласованность. Эти несоответствия в стандарте C могут не иметь практических последствий, так же как полнота по Тьюрингу не связана с практическим применением.
Моделирование произвольных чисел на основе глубины рекурсии (т. Е. Это ; с возможностью поддержки нескольких чисел через планирование / псевдопотоки; теоретического ограничения глубины рекурсии в C не существует ) или использование файлового хранилища для имитации неограниченной памяти программы ( идея ) вероятно, только две из бесконечных возможностей конструктивно доказать полноту по Тьюрингу C99. Следует помнить, что для вычислимости сложность времени и пространства не имеет значения. В частности, допущение ограниченной среды для фальсификации полноты по Тьюрингу является просто циклическим рассуждением, поскольку это ограничение исключает все проблемы, которые превышают предполагаемую границу сложности.
( ПРИМЕЧАНИЕ . Я написал этот ответ только для того, чтобы не дать людям получить математическую интуицию из-за ограниченного мышления, ориентированного на приложения. Очень жаль, что большинство учеников прочтут ложный принятый ответ из-за того, что за него проголосовали фундаментальные недостатки рассуждения, так что больше людей распространят такие ложные убеждения. Если вы отрицаете этот ответ, вы просто являетесь частью проблемы.)
источник
CHAR_BITS
.