I
А, и всё🤔?
Тогда Си не полон? Бесконечная лента не бесконечная?
Тогда Си не полон? Бесконечная лента не бесконечная?
Ни одна машина в мире не имеет бесконечной памяти, ergo ни один язык программирования не полон по тьюрингу.
Size: a a a
2020 January 27
RB
А полна ли машина Тьюринга по Тьюрингу?🤔
AV
Некотрые языки ограничены физически (см лисп), а некоторые ограничены по стандарту см UCHAR_MAX в си
AV
Правда если пройти по ссылкам, то написано как это обойти
AV
Так что я уже даже не уверен, в правоте своего утверждения
M
А полна ли машина Тьюринга по Тьюрингу?🤔
При том, что у нее всего один регистр общего назначения то был
I
А полна ли машина Тьюринга по Тьюрингу?🤔
Если построить физическую тьюринг-машину, то не будет полна. Но если рассматривать языки как их спецификации, то, к примеру, Си полон по Тьюрингу.
RB
Интересно 🤔
I
Реализовать Тьюринг-машину на нем же.
Гда там, кстати, моя любимая ссылка на реализацию Тьюринг-машины на плюсовых шаблонах
RB
На самом деле, Си полностью полон по Тьюрингу, но из-за слабого железа и малой памяти ПК пользователя, этого невозможно увидеть))
AK
Если построить физическую тьюринг-машину, то не будет полна. Но если рассматривать языки как их спецификации, то, к примеру, Си полон по Тьюрингу.
В итоге получается, что ни одна из реализаций не соответствует спецификации? )
I
В итоге получается, что ни одна из реализаций не соответствует спецификации? )
Именно! Все языки - это сократовские идеи, а их реализации - манифестации этих идей в реальном мире и, как любая манифестация, они не идеальны.
YS
О, вот
Допустим у меня есть язык А
Как мне проверить, что язык А полный по Тьюрингу?
Есть статья? Или это определяется автоматически?
Допустим у меня есть язык А
Как мне проверить, что язык А полный по Тьюрингу?
Есть статья? Или это определяется автоматически?
Если Вам это нужно для практических целей, разве это не +- тривиально?
Т.е., если есть циклы / рекурсия (можно их реализовать) + доступная память не жёстко ограничена — да, полон.
Т.е., если есть циклы / рекурсия (можно их реализовать) + доступная память не жёстко ограничена — да, полон.
RB
А, круто
YS
Полон
Вроде давали же ссылку уже, где написано, что теоретически — нет (а практически, конечно, да)... вообще, какой в этом толк, я не пойму? ;)
AV
Но в каждой конкретной реализации си память ограничена. Но это абсолютно не важно
AV
Можно рассматривать как анекдот
SM
Если построить физическую тьюринг-машину, то не будет полна. Но если рассматривать языки как их спецификации, то, к примеру, Си полон по Тьюрингу.
Си не полон по тьюрингу, мы это уже обсуждали раньше. Но он скорее исключение. Но похоже с11 все таки полон но только изза "хака" с тредами: https://cstheory.stackexchange.com/a/37006
I
Си не полон по тьюрингу, мы это уже обсуждали раньше. Но он скорее исключение. Но похоже с11 все таки полон но только изза "хака" с тредами: https://cstheory.stackexchange.com/a/37006
Эээээ, "But Turing machines with a tape infinitely progressing in only one direction are just as powerful as Turing machines with a tape infinitely progressing in two directions. Apart from that, multiple threads can be simulated by a scheduler. Anyways, we do not even require a threading library."