Обсуждение:Полнота по Тьюрингу

2023-10-17T03:39:19Z

77.37.160.152:

Нужны ссылки на источники, больше истории.
Почему полнота "по Тьюрингу", а не "по Посту" (см. [[машина Поста]])?
У каких российских учёных есть аналоги (пусть и позже иностранных, но оригинальные исследования, а не работа переводчиков)?
[[Special:Contributions/77.37.160.152|77.37.160.152]] 03:39, 17 октября 2023 (UTC)

ANSI C не полон по Тьюрингу, потому что не может адресовать бесконечное количество памяти. Это хороший пример различия теории и практики :) --- [[Участник:Lispnik|Lispnik]]

[ненормативная лексика] Где сказано что не может? [[user:212.19.157.154|212.19.157.154]]

: Урезал ваш комментарий, и просьба подписываться (<nowiki>--~~~~</nowiki>). --[[Участник:Yurik|Yurik]] 19:08, 22 Апр 2005 (UTC)
: Первое, согласно стандарту, char должен иметь конечный размер. Второе, все типы должны иметь конечный размер в char (sizeof). Т.о. указатели могут адресовать не более чем (MAX_CHAR_VALUE-MIN_CHAR_VALUE)^(sizeof(void*)) элементов, где ^ означает возведение в степень. --- [[Участник:Lispnik|Lispnik]]

:: Из того, что указатели не могут что-то там адресовать, ничего не следует. Можно использовать относительные указатели (продолжение по смещению +N символов), и их можно использовать любое количество (см. "связный список"). [[Special:Contributions/77.37.160.152|77.37.160.152]] 03:39, 17 октября 2023 (UTC)

Неверное определение. Неверно говорить, что полные по Тьюрингу исполнители -- это те, которых можно сэмулировать на Универсальной Машине Тьюринга. Универсальная Машина Тьюринга может эмулировать только машины Тьюринга, в том числе саму себя. На вход она может получать только описание машины тьюринга и входа для этой машины. Машину Поста, например, она не может эмулировать в принципе.
ПРЕДЛОЖЕНИЯ:
# Полноту по Тьюрингу включить в статью про Машину Тьюринга (что я уже сделал). А Здесь сделать редирект.
# Можно сделать также статью [[Языки программирования полные по Тьюрингу]], либо сделать эту тему разделом статьи [[Машина Тьюринга]].
# Использовать слово "имитация", а не "эмуляция". -- [[Участник:Greck|greck]] 08:06, 18 апреля 2006 (UTC)
: Полнота по Тьюрингу — это важное понятие, достойное отдельной статьи. Она не сводится только к машине Тьюринга и даже важнее её, поэтому я против включения. Скорее статью о машине Тьюринга можно сделать частью статьи о полноте по Тьюрингу, как пример вычислителя, полного по Тьюрингу. С остальной критикой я согласен. Надо подумать, проконсультироваться с литературой типа книг Маркова или Роджерса и переписать статью. [[Участник:Lispnik|Lispnik]] 08:16, 20 апреля 2006 (UTC)

Я вот почитал определения и так никуя и не понял - пишите понятно (Дмитрий)
: поддерживаю. нихуя не понятно и из примеров. [[Special:Contributions/77.176.20.19|77.176.20.19]] 19:40, 7 июля 2008 (UTC)

Взаимоисключающие параграфы: полнота характеризует исполнитель, и некоторые формальные грамматики не являются полными. Грамматика - не исполнитель.

Тьюринг полнота времени компиляции в Haskell "появляется", только если использовать расширения к стандарту языка, доступные в одном из компиляторов. Хотя нужно признать, что этот компилятор и эти его расширения очень популярны. Подробности, например, здесь: http://www.haskell.org/pipermail/haskell/2006-August/018355.html [[User:Ierton|Ierton]] 19:40, 10 апреля 2011 (UTC)

wiki12 - Вклад [ru]

Обсуждение:Полнота по Тьюрингу