Обсуждение:Занятый бобер

(рейтинг B-класс, средний приоритет)

	Математический портал Эта статья находится в рамках WikiProject Mathematics , совместной работы по улучшению освещения математики в Википедии. Если вы хотите принять участие, посетите страницу проекта, где вы можете присоединиться к обсуждению и увидеть список открытых задач. Математика Wikipedia:WikiProject Mathematics Шаблон:WikiProject Mathematics статьи по математике
Б	Эта статья была оценена как B-класс по шкале качества проекта .
Середина	Эта статья имеет средний приоритет по шкале приоритетности проекта .

Лучшее введение

Редактировать (29-12-15): изменение было применено. -- Негрулио ( обсуждение ) 01:33, 29 декабря 2015 г. (UTC) [ ответить ]

Редактировать (28-12-15): я иду на это изменение завтра. -- Негрулио ( обсуждение ) 16:00, 28 декабря 2015 г. (UTC) [ ответить ]

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

В теории вычислимости занятый бобер — это машина Тьюринга, которая достигает максимального количества выполненных шагов или максимального количества непустых символов на ленте среди всех машин Тьюринга в определенном классе. Машины Тьюринга этого класса должны соответствовать определенным конструктивным требованиям и должны в конечном итоге останавливаться после запуска с пустой ленты.

Вопросы введения

Он начинается с определения занятого бобра как машины Тьюринга. Я думаю, это все усложняет. В оригинальной статье, опубликованной Тибором Радо в 1962 году, «Busy Beaver» описывается как игра, которая включает в себя создание двоичного алфавита, остановку машин Тьюринга, которые печатают наибольшее количество единиц на ленте, начинающейся только с 0. Не лучше ли было бы просто описать игру, а затем описать машины Тьюринга, которые ей требуются?
Это слишком абстрактно. Упоминание «определенного класса» и «определенных спецификаций дизайна» делает его слишком сложным. Обобщение оригинальной игры, упомянутой Радо, может сделать ее более понятной.
Он определяет две разные концепции: машину Тьюринга bb и функцию bb. Я бы оставил определение функции в новом разделе статьи.

Предлагаемое новое введение

Предлагаю следующее введение:

Игра Busy Beaver состоит из проектирования останавливающейся машины Тьюринга с двоичным алфавитом, которая записывает наибольшее количество единиц на ленту, используя только ограниченный набор состояний. Правила игры с двумя состояниями следующие: (i) машина должна иметь два состояния в дополнение к состоянию остановки, и (ii) лента начинается только с нулей. Как игрок, вы должны понимать, что каждое состояние должно быть нацелено на максимальный вывод 1 с на ленту, при этом убедитесь, что машина в конечном итоге остановится.

N - й занятой бобр или BB-n — это машина Тьюринга, которая выигрывает игру Busy Beaver с N-состоянием. То есть он достигает максимального количества единиц среди всех других возможных конкурирующих машин Тьюринга с N-состояниями. Например, машина Тьюринга BB-2 достигает четырех единиц за шесть шагов .

Игра занятого бобра имеет значение в теории вычислимости , проблеме остановки и теории сложности . Эта концепция была впервые введена Тибором Радо в его статье 1962 года «О невычислимых функциях». Негрулио ( обсуждение ) 15:51, 27 декабря 2015 г. (UTC) [ ответить ]

Занятые функции бобра

На данный момент упоминаются только Σ (количество ненулевых значений в результате) и S (количество сделанных шагов). Есть и другие, которые могут быть исследованы:

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

.... -- Smjg 15:11, 27 сентября 2005 г. (UTC) [ ответ ]

В нем говорится, что в этом разделе есть [4(n+1)]^(2n) машин... разве там не только [4n+2]^(2n)? Или 1-левая и 1-правая разные???

использованная литература

Я наткнулся на ссылки Sci Am в своей старой записной книжке; они "непроверенные" в том смысле, что я не видел их уже 20 с лишним лет. Ссылка Rado фактически появляется в ссылках Бута на его главу 9 под названием «Машины Тьюринга». Так что это тоже "квази-непроверено". Я смотрю на страницы книги Бута, так что, думаю, мы можем утверждать, что ссылка проверена. wvbailey22:08, 6 января 2006 г. (UTC)

Ссылка на «Вычисление функции занятого бобра» Чайтина не работает

PDF-файл в настоящее время доступен по этому URL-адресу:

https://www.cs.auckland.ac.nz/~chaitin/bellcom.pdf

Я не знаю, как правильно редактировать ссылки, извините.

68.7.137.69 ( разговор ) 04:32, 26 мая 2016 (UTC) [ ответ ]

Ссылка на «Проблему занятого бобра: АТАКА НОВОГО ТЫСЯЧЕЛЕТИЯ» также не работает — предыдущий неподписанный комментарий добавлен 199.203.204.197 ( обсуждение ) 06:50, 28 июня 2022 г. (UTC) [ ответ ]

Может быть, его можно заменить на https://homepages.hass.rpi.edu/heuveb/Research/BB/index.html ? Похоже, та же ссылка по другому адресу — предыдущий неподписанный комментарий добавлен 199.203.204.197 ( обсуждение ) 06:53, 28 июня 2022 г. (UTC) [ ответ ]

Или это должно быть https://homepages.hass.rpi.edu/heuveb/Research/BB/status.html ? 199.203.204.197 ( разговор ) 06:55, 28 июня 2022 г. (UTC) [ ответ ]

Обозначение

«1s» против «1s» против «единиц»

В статье непоследовательно используются «единицы», «единицы» и «единицы» для обозначения множественного числа от «1». Как это должно быть стандартизировано? Кроме того, что означает обозначение « S _RTM ( n )»? Pmdboi 14:24, 8 марта 2006 г. (UTC) [ ответ ]

Если в Википедии нет стандарта, противоречащего моему мнению, я голосую за «1», когда единицы являются множественным числом символа «1» из двоичного набора символов {0, 1}. Стандартная американская проза/литература хочет/использует/ожидает «один» и «один». Интересно, что международный символ OFF — O , а ON — | (вертикальная косая черта, а не порядковый номер «1»: в соответствии с IEC - не могу вспомнить точный номер спецификации IEC-317, символы?). Эмиль Пост указал "знак" = { | } и "blank" = {} в его моделях. Вероятно, это должно быть «|», как во множественном, так и в единственном числе, но я бы придерживался «1» в аргументе: «Если Биллу это нравится, это должно быть хорошо». (Надеюсь это поможет).

По состоянию на декабрь 2015 года я не могу найти ни «1», ни «0» . Все заменено на "1" и "0" . В английском языке нет стандарта написания множественного числа однозначных цифр. Оксфордские словари онлайн предлагают не добавлять апостроф для образования множественного числа числа, за исключением случаев , когда это одна цифра, и в этом случае «вы можете использовать апостроф, чтобы показать множественное число одиночных чисел». Обратите внимание на «можно». Таким образом, эта статья написана правильно. Негрулио ( обсуждение ) 14:17, 27 декабря 2015 г. (UTC) [ ответить ]

Использование обозначения со стрелкой вверх по сравнению с обозначением с начальным верхним индексом

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

{\ displaystyle ^ {b} a = a \ uparrow \ uparrow b}

Но в тексте в настоящее время мы имеем кажущееся ненужным смешение двух обозначений и неспособность идентифицировать альтернативную форму:

  ${\ displaystyle \ Sigma (2k)> 3 \ uparrow ^ {k-2} 3> A (k-2, k-2) \ quad (k \ geq 2),}$  где - обозначение стрелки вверх Кнута, а - функция Аккермана . ${\ Displaystyle \ стрелка вверх}$

Если мы придерживаемся только одного обозначения, оно должно быть эквивалентно либо:

  ${\ displaystyle \ Sigma (2k)> 3 \ uparrow (3 \ uparrow \ uparrow (k-2))> A (k-2, k-2) \ quad (k \ geq 2)}$

ИЛИ ЖЕ

  ${\ displaystyle \ Sigma (2k)> 3 ^ {3 \ uparrow \ uparrow (k-2))}> A (k-2, k-2) \ quad (k \ geq 2)}$

Наконец, я нахожу использование одинарного числа \quadсбивающим с толку (потому что это просто выглядит как добавление дополнительного пробела или около того, и все же умножение, а не более четкое разграничение), поэтому вместо этого я бы предпочел что-то вроде:

  ${\ displaystyle \ Sigma (2k)> 3 ^ {(3 \ uparrow \ uparrow (k-2))}> A (k-2, k-2) \ где \ (k \ geq 2)}$

Я отмечу, что я не полностью склоняюсь к этой последней модификации, если это что-то действительно стандартное, чего я просто не видел или не замечал раньше. Спасибо. — Кояэ ( обсуждение ) 06:28, 25 декабря 2014 г. (UTC) [ ответ ]

Если кто-то думает об изменении статьи в ответ на это, пожалуйста, не делайте этого. Здесь нет смешения обозначений; означает , где k-2 — количество стрелок. 78.146.215.183 ( разговор ) 15:52, 28 апреля 2015 г. (UTC) [ ответ ]

{\ Displaystyle 3 \ вверх ^ {к-2} 3}

{\ Displaystyle 3 \ вверх \ cdots \ вверх 3}

Ошибка?

Я заметил небольшую проблему с этим доказательством. Предполагается, что количество состояний, необходимых для EvalS, постоянно, независимо от значения n0. Что, если количество состояний, необходимых для EvalS, зависит от n0? Возможно, кодирование EvalS машиной Тьюринга можно вычислить из n0?

Нет. Если бы существовала машина Тьюринга M, которая могла бы создать EvalS на основе n0, то мы могли бы запустить M на n0, чтобы создать EvalS, а затем запустить EvalS, получив таким образом машину фиксированного размера, которая запускает EvalS. Это некоторое оправдание нашего определения вычислимости как вычислимости машины Тьюринга. - Sligocki 03:14, 9 декабря 2006 г. (UTC) [ ответ ]

Я заметил, что в артикуле указано, что символ 2, значение состояния 3 равно 14 с шестью напечатанными единицами, однако в другом месте я видел упоминание о том, что «В 1965 году Радо вместе с Шэнь Линь доказал, что BB(3) равно 21». Я не знаю, где искать этот конечный автомат или найти окончательное доказательство в любом случае, это было просто то, что я поймал, просматривая страницу вики и эту другую статью. -- 72.94.0.116 ( разговор ) 06:27, 22 марта 2008 г. (UTC) (Draco18s) [ ответ ]

Доступность

Привет,

эта статья довольно хороша, но она очень сложна! Я считаю, что у меня все в порядке с математикой и минимум вычислений, но большая часть этого выходит за рамки моей головы. Википедия должна быть доступна для неспециалистов, и хотя это сложно, когда ты эксперт, а аудитория нет, я думаю, что редакторы должны немного упростить это ! Если ученик средней школы, не обладающий навыками математики или вычислений, не может полностью понять статью, то ей не место в энциклопедии! Если что-то нельзя упустить, то как минимум дайте ссылки. -- Бен 18:03, 11 июля 2006 г. (UTC) [ ответ ]

Есть ли категория, куда мы можем поместить запросы на доступность? Я смотрю на это, и кажется, что если у вас нет опыта в том, о чем говорится в этой статье, вы не сможете ее понять. например, эта последовательность "1, 4, 6, 13, ≥ 4098" вообще не имеет никакого смысла. Среднестатистическому человеку определенно следует прояснить причины незнания пятого числа, когда оно известно. что оно не может быть больше, чем 4098. Кроме того, какой смысл во всем этом?Статья, кажется, не дает понять, почему все это имеет какое-либо значение для чего-либо, например, почему кто-то когда-либо захочет знать, что такое пятый значение меньше 4098, и как знание этого числа может что-то изменить. Определенно не удобно для пользователя Carterhawk 08:23 , 26 августа 2006 (UTC)[ ответить ]

Ты прав. Цифры «взрываются» после 4 инструкций (состояний). А "трудолюбивым бобрам" земного проку...пока. Но кто может сказать? Когда-нибудь из их изучения может получиться что-то невероятное. А вот "занятые бобры" - тема "тяжелая". «Бобр-трудяга» бросает вызов самым лучшим ученым-компьютерщикам, людям с многолетним опытом работы с компьютерами. wvbailey

В игре The Busy Beaver рассмотрим машину Тьюринга с двоичным алфавитом {0, 1}... Теперь начнем с пустой ленты (т. е. в каждой ячейке есть 0) и ТАБЛИЦЫ из n инструкций. сбивает с толку в контексте классической машины Тьюринга, которая имеет входной алфавит Σ и ленточный алфавит Г, причем последний содержит первый плюс (по крайней мере) пустой символ. Кажется, здесь у нас есть ТМ с ленточным алфавитом {0, 1}, где 0 — символ пробела. Конечно, на самом деле нас не волнует входной алфавит, так как вход фактически равен ε, но все это следует прояснить. Страницы Паскаля Мишеля, упомянутые в статье, хотя и не раскрывают сути, прямо утверждают, что 0 — это пустой символ. Онкельрингельхут15:22, 27 января 2007 г. (UTC) [ ответить ]

Игра Busy Beavers: простое объяснение

Это двухсимвольный Busy Beaver с тремя состояниями. Он работает на ленте, изначально напечатанной с 0 / пробелами. Робот посмотрел на символ в окне (символ 0), прочитал инструкцию («состояние») C и собирается НАПЕЧАТАТЬ 1. Затем он нажмет на ленту ВЛЕВО. Наконец, он будет смотреть на инструкцию («состояние») B . (Механизм печати/стирания находится вне поля зрения, под окном.)

«Бобры хлопоты» — это игра . Цель? Чтобы найти «инструкции», которые заставят вас, как занятого бобра, напечатать большинство из них на кусочке бумажной ленты. Но, как и во всех играх, здесь есть правила, и чтобы играть, сначала вам нужно их выучить.

Правило № 1 : Знайте, что такое « двухсимвольная машина Тьюринга ». Машину Тьюринга НЕ легко понять. Но думайте об этом как о действительно странной, неуклюжей, простодушной счетной машине, самом сложном в использовании карманном калькуляторе на планете, но самом мощном. Через него проходит очень длинный кусок бумажной ленты (размеченный на «квадраты») и 4 кнопки: ПЕЧАТЬ, СТИРАТЬ, ОДИН КВАДРАТ ЛЕВЫЙ, ОДИН КВАДРАТ ПРАВЫЙ, робот, который нажимает на кнопки, и список инструкций. называется «Таблица», за которой должен следовать робот.

Как занятой бобер вы будете роботом. У вас есть лента, бегущая мимо вас. У вас будет список инструкций. Вы (как бобр с двумя состояниями) можете ПЕЧАТЬ только 1 (счетные отметки) или СТИРАТЬ их (другими словами, делать пробелы, печатать 0) на этой полностью пустой (все 0) ленте. Вы можете печатать или накладывать, стирать или стирать, но только одну отметку на одном квадрате за раз. Вы можете перемещать ленту только на одну клетку ВЛЕВО или ВПРАВО за раз. Лента такая длинная, как вы хотите. Если вы предпочитаете, вы можете использовать кнопочную консоль, а не делать это вручную.

ПРАВИЛО № 2 : Занятый бобер всегда следует своему неизменному списку инструкций. Вам нужно будет знать, как их читать, и вы должны следовать им в обязательном порядке. См. ниже, с примером.

ПРАВИЛО №3 : Всегда соблюдайте правила №1 и №2. В конце концов, вы теперь компьютер/робот.

Если вы сможете выполнить ПРАВИЛО № 1, № 2 и № 3 без ошибок, вы тоже сможете покинуть мир людей и вступить в ряды занятых бобров!

Ваша миссия :

Ваша миссия (и ваша жизнь) как занятого бобра будет состоять из трех частей:

Миссия Часть I :

> Ваша миссия в качестве «делового бобра» (если вы решите принять ее):

>> В начале вам будет предоставлен список инструкций. (После этого либо вы, либо ваши кураторы измените инструкции в Части II). Точно следуйте инструкциям и выведите столько единиц, сколько указано в инструкциях, прежде чем остановиться. Чтобы добиться успеха, вы должны напечатать несколько единиц и, в конце концов, ОСТАНОВИТЬСЯ!

> Ваша «лента Тьюринга» готова — она пуста. Ваша инструкция №1. Нет ограничения по времени, никого не волнует (слишком много), сколько времени вы возьмете. Просто следуйте правилам и печатайте единицы на пустой ленте.

> Роботы, вы готовы?

> Иди!

Миссия Часть II :

Роботы, ваши бобровые испытания окончены. Вам это удалось: вы либо ОСТАНОВИЛИСЬ, либо не ОСТАНОВИЛИСЬ (откуда мы это узнали? -- ааа, интересный вопрос!), ЛИБО вы напечатали какие-то. Счетчики стоят рядом, готовые пересчитать ваши и записать инструкции, которым вы следовали.

> Ваша новая миссия (если вы решите ее принять):

Измените инструкции, которые вам дали, чтобы они по-прежнему были настоящей «занятой программой Тьюринга бобра» и имели такое же количество инструкций. Например: если ваша миссия состоит в том, чтобы найти 6 лучших инструкций, у вас должно быть 6 инструкций. Но если в инструкции № 3 вы видите ERASE, вы можете изменить это на PRINT, а там, где вы можете видеть LEFT, вы можете изменить это на RIGHT).

сделать часть I снова.

Миссия Часть III :

Повторяйте часть I и часть II навсегда! Это жизнь «делового бобра». Разве ты не рад, что ты робот, а не человек!

>>>>>> <<<<<<<<

Как читать инструкции занятого бобра :

Вот таблица инструкций для занятого бобра с двумя состояниями на машине Тьюринга .

	Текущая инструкция А :			Текущая инструкция B :
	ПЕЧАТЬ/СТИРАТЬ:	Переместить ленту:	Следующее состояние:	ПЕЧАТЬ/СТИРАТЬ:	Переместить ленту:	Следующее состояние:
символ ленты равен 0:	РАСПЕЧАТАТЬ	ПРАВИЛЬНО	Б	РАСПЕЧАТАТЬ	ОСТАВИЛ	А
символ ленты равен 1:	РАСПЕЧАТАТЬ	Оставил	Б	РАСПЕЧАТАТЬ	НИКТО	ЧАС

Занятые бобры всегда начинают с «инструкции А » с пустой ленты (инструкции обычно называются «состояниями» в мире Тьюринга). «ГОЛОВА» — это место, где находится отсканированный квадрат — куда смотрит ваш глаз (поэтому «глаз» может быть более подходящим словом).

				ГЛАВА						В начале инструкции:
										А

В таблице инструкций посмотрите вниз столбец слева. Отсканированный квадрат (в кнопочной консоли или перед вами на ленте, под HEAD) пустой (или 0), или там написано 1? Он должен быть пустым/0, потому что мы начинаем с нуля. Поскольку он пустой/0, под A следуйте верхней строке слева направо и выполните следующие действия в этом порядке:

ПЕЧАТЬ (отметьте квадрат цифрой 1)

ВПРАВО (переместите ленту вправо)

ПЕРЕЙТИ К ИНСТРУКЦИИ Б

ГЛАВА		В начале инструкции:
		А
	1	Б

В инструкции B мы смотрим, является ли отсканированный символ 1 или пробелом/0. Поскольку мы знаем, что это пробел/0, мы снова идем по верхней строке, но под B, и делаем следующее:

ПЕЧАТЬ (отметьте квадрат)

ВЛЕВО (лента слева)

ПЕРЕЙТИ К ИНСТРУКЦИИ А

	ГЛАВА		В начале инструкции:
			А
		1	Б
1	1		А

Теперь, когда мы обнаруживаем, что на отсканированном квадрате напечатана 1. Итак, мы следуем по нижнему ряду под A и находим следующие инструкции:

РАСПЕЧАТАТЬ

ОСТАВИЛ

ПЕРЕЙТИ К ИНСТРУКЦИИ Б

		ГЛАВА		В начале инструкции:
				А
			1	Б
	1	1		А
1	1			Б

Мы продолжаем это, когда, наконец, нажимаем инструкцию HALT. Были сделаны!:

			ГЛАВА		В начале инструкции:
					А
				1	Б
		1	1		А
	1	1			Б
1	1	1			А
	1	1	1	1	Б
	1	1	1	1	ЧАС

Вы, как занятой бобер, напечатали 4 шт. Они не должны были быть все подряд, но это действительно хорошая работа. Вы справились так же хорошо, как и любой "двухсимвольный занятой бобер с двумя состояниями". Теперь пришло время перейти к инструкции с тремя состояниями. Роботы: вы готовы?

Конец.

>>>>>> <<<<<<<<

Пример «маленького» занятого бобра — работающего бобра с одним, двумя, тремя или четырьмя состояниями — можно «запустить» в любой электронной таблице, например в Excel. Занятые бобры с пятью и шестью штатами не могут — их «производство» — количество, которое они могут напечатать, — слишком велико, чтобы вместиться. Вам понадобится помощь в настройке модели. Это поможет вам узнать, что делает инструкция ИНДЕКС(....) (например, ИНДЕКС(B5:B20,,A3)), но вы можете создать машину Тьюринга на электронной таблице и без этого. Все равно как-то хлопотно. Пример того, как выглядит «бег» занятого бобра, см. в разделе Примеры машин Тьюринга и Машины пост-Тьюринга .wvbailey Wvbailey 17:39, 8 сентября 2006 г. (UTC) [ ответ ]

Пример занятого бобра с 4 состояниями

Запустите в Экселе. Транспонировано боком, чтобы поместиться на странице. Машина А. Брэди.

Ниже приведен тестовый пример, чтобы увидеть, как это выглядит. Это будет выглядеть лучше с просмотрщиком Netscape. Вы можете найти 2-символьного занятого бобра с 2 состояниями на машине Пост-Тьюринга и, как упоминалось в статье, 2-символьного занятого бобра с 3 состояниями на машинах Тьюринга в примерах . wvbailey Wvbailey 20:37, 22 августа 2006 г. (UTC) [ ответить ]

wvbailey

пример wvbailey должен быть на главной странице. Главная страница в настоящее время не имеет смысла для тех, кто еще не понимает предмет. Его объяснение и пример были вполне понятны и, по крайней мере, позволили мне понять, о чем идет речь в основной статье. Спасибо за это wvbailey!

Слишком технично

Несколько читателей (см. выше) попросили, чтобы статья содержала некоторый контекст, объяснение и пример. Я не чувствую себя компетентным, чтобы обращаться здесь к более техническим частям (я мог бы заняться исторической частью — например, я хочу увидеть статью Радо). Я бы предложил следующее:

Дайте понять, что занятые бобры — это «игра» (хотя и странная математическая игра), в которую может играть каждый. У него нет очевидного «применения» — см. следующий пункт.
Исторический контекст: почему компания Rado предложила занятых бобров? Брэди намекает, что это связано с вопросами, связанными с «проблемой остановки», экземпляры крошечных машин должны поддаваться решению «проблемы», но даже эти крошечные машины практически «неразрешимы».
Кто работает на занятых бобров? Единственное имя, которое я знаю, это Аллен Х. Брейди; см. ссылку на его статью.
Краткое описание алгоритма (алгоритмов), используемого для поиска самого занятого бобра.

Откуда мы знаем, что конкретный тестируемый бобер (например, с 6 состояниями) не зациклен? Откуда мы знаем, когда «сдаться» и «на этом закончить»?
Эвристики: они используются? Может ли случайный читатель понять, какие bb не будут работать и почему? (конечно, некоторые из них тривиальны, например, любое доступное состояние, в котором 0 и 1 возвращаются обратно к себе (чтобы сделать круг)
Генетические алгоритмы как-то использовались? Параллельные алгоритмы, используемые для просеивания возможных вариантов?

Примеры простейших случаев. Например , пост-машина Тьюринга и примеры машин Тьюринга, где я использовал двухсимвольные занятые бобры с 2 и 3 состояниями в качестве примеров (таким образом избегая «оригинального исследования»). Но на самом деле их следует повторить здесь, или особенно занятый бобер на примерах машины Тьюринга должен быть здесь, а статья о машине Тьюринга находится здесь.
Почему проблема «взрывается»? Кажется, что он взрывается двумя способами: как по количеству возможных bb на количество состояний, так и (ii) по количеству состояний, через которые может пройти конкретный тестируемый экземпляр.

Предоставьте простое объяснение количества возможных занятых бобровых машин на количество состояний N (мне кажется, что это (8 * N) ^ N). Но многие глупы, отсюда и потребность в эвристике.

Лучше (больше) печатных ссылок, а также встроенных ссылок. Есть ли какие-нибудь книги конкретно о занятых бобрах?

Предложения? Комментарии? wvbailey Wvbailey 14:47, 15 сентября 2006 г. (UTC) [ ответ ]

Обновление контента

Я добавил довольно много новой информации, основанной на оригинальной статье Rado и некоторых ваших комментариях на этой странице обсуждения. Я надеюсь, что это сделало страницу более читабельной и доступной. Из-за значительного изменения содержания я удалил с этой страницы тег Confusing. Я надеюсь, что вы все просмотрите страницу, чтобы увидеть, следует ли ее вернуть или нет. Если у вас есть какие-либо комментарии или пожелания, мне было бы очень интересно их услышать.

Счастливый занят Beavering! Sligocki 17:30, 12 декабря 2006 г. (UTC) [ ответ ]

Я очень ценю то, что вы здесь сделали. Я обыскал библиотеку Дартмута в поисках копии оригинальной статьи Радо, но не смог ее найти. У меня есть вторая статья — статья Лин-Радо — но не самая оригинальная. Я вижу, что кто-то добавил еще один тег внизу. Но без оригинальной статьи Rado я чувствую себя не готовым к эффективному обзору/редактированию. Где можно найти копию оригинальной статьи? Дай знать, спасибо. wvbailey Wvbailey 21:39, 27 января 2007 г. (UTC) [ ответить ]

Невычислимость Σ : подчеркивая возможную ловушку

В статье утверждается, что, хотя сама функция занятого бобра невычислима, любая конечная последовательность Σ(0),...,Σ(n) вычислима. Конечно, это верно — на самом деле, это верно для любого конечного набора натуральных чисел: простой алгоритм, который на входе n выводит значение Σ(n), решает проблему. Иными словами, это означает только то, что Σ, ограниченное [1, N], может быть описано финитно — что очевидно — и ничего более: хотя теоретически невозможно вычислить Σ(n) для некоторого заданного n, возможно, мы никогда не сможем этого сделать, даже с невообразимо мощными машинами. Статья, возможно, может предложить непосвященному читателю какое-то более сильное свойство. Я пытаюсь аккуратно перефразировать. Dabsent ( разговор ) 11:12, 31 мая 2008 г. (UTC) [ ответить]

Спасибо, что указали на место для улучшения формулировки, но это не то, что я написал; то, что я написал, было

Хотя Σ — невычислимая функция, тем не менее для каждого натурального числа n конечная последовательность Σ(0), Σ(1), Σ(2),..., Σ(n) вычислима.

Это утверждение правильное и недвусмысленное, имхо, но чтобы подчеркнуть ловушку, которая возникает у любого, кто склонен к «количественной дислексии», я переформулировал его. Это, в конце концов, именно тот вопрос, который я изначально хотел подчеркнуть. Я также заменил ваше объяснение ссылкой на поясняющие примеры в вычислимой функции#Примеры (см. первый и последний примеры, приведенные там). -- res ( talk ) 21:32, 31 мая 2008 г. (UTC) [ ответ ]

Я согласился, что это совершенно верно, и мне не следовало говорить «двусмысленно», потому что технически это не так. Моя формулировка здесь была менее точной, чем в оригинале, но моя точка зрения — боюсь, я не объяснилась должным образом — заключалась не в том, что присутствие квантификатора было недостаточно ясным: трудность, как я полагаю, заключается в в идее, что для каждой конечной последовательности существует алгоритм для ее вычисления, или, точнее, что с нашим определением «алгоритмически решаемой» каждый конкретный экземпляр проблемы может быть тривиально «алгоритмически решаемой» без самой проблемы. «алгоритмически решаемый». Формальное определение, например, машины Тьюринга делает это очевидным, но с точки зрения интуиции это тонкость, а не тривиальность, если не считать

Меня устраивает текущая формулировка и ссылка, так лучше.

Dabsent ( обсуждение ) 18:29, 1 июня 2008 г. (UTC) [ ответ ]

На самом деле, возможность разработки концепции «эффективной вычислимости/невычислимости», которая применялась бы к вычислению одного отдельного целого числа — и, следовательно, сильно отличалась от стандартного в настоящее время понятия (не-)вычислимости , — была основным мотивом для Радо. и Лин. Вот цитата из их статьи 1965 года:

Наш интерес к этим очень специальным проблемам был мотивирован тем фактом, что в настоящее время не существует формального понятия для «эффективной вычислимости» отдельных четко определенных целых чисел, таких как Σ(4), Σ(5), .... (Мы благодарны профессору Клини из Университета Висконсина за эту информацию.) Поэтому мы чувствовали, что фактическая оценка Σ(3), SH(3) может дать некоторые подсказки относительно формулировки плодотворной концепции эффективной вычислимости (и невычислимости ) отдельных корректно определенных целых чисел.

(Цитата содержится в «Отслеживании невычислимости» Л. Де Моля , стр. 462.) Хотя настоящий раздел статьи посвящен невычислимости , возможно, этот пункт о поиске другого типа «невычислимости» должен быть подчеркнуто больше?

-- res ( обсуждение ) 01:17, 2 июня 2008 г. (UTC) [ ответить ]

Хм, если я правильно понимаю, означает ли это, что, например, существует детерминистический, хотя и долговременный алгоритм для определения истинности любого конкретного универсального утверждения над счетным множеством с вычислимым предикатом, таким как гипотеза Гольдбаха? Если это так, то это может показаться противоречащим некоторым аргументам в отношении проблемы остановки, почему неразрешимость проблемы остановки является «неудивительной» или «интуитивной». Dcoetzee 08:19, 2 июня 2008 г. (UTC) [ ответ ]

Поскольку «исчисляемый» не означает «конечный», я бы сказал, что ответ на ваш вопрос «нет». Но при ограничении конечным числом случаев неразрешимая иначе проблема принятия решений обязательно становится разрешимой, потому что разрешимость, как и вычислимость, технически относится к простому существованию требуемого алгоритма, а не к тому, кто фактически «производит» алгоритм. Радо, очевидно, изучал возможность того, что такой алгоритм, хотя технически и существует для вычисления одного конечного экземпляра (например, единственного целого числа Σ(n ₀ ) для некоторого отдельного целого числа n ₀ ), тем не менее может быть логически невыполнимым (мой термин), в отличие от просто из-за того, что в подавляющем большинстве случаевнецелесообразно производить и/или выполнять . Насколько я знаю, это все еще открытый вопрос.

-- res ( обсуждение ) 13:35, 2 июня 2008 г. (UTC) [ ответить ]

Спасибо Res за ссылку и информацию; это очень интересно. Я подумаю об этом.

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

Относительно вопроса Дкотзи: идея процедуры, основанной на занятом бобре, состоит в том, чтобы создать машину Тьюринга (или какую-то программу в более широком смысле), способную проверить правильность гипотезы для любого заданного n. Допустим, эта программа имеет размер s . Вы вычисляете S(s) , затем запускаете S(s) операций вашей программы. Теперь, если вы рассмотрите набор проблем того типа, который вы описали, все из которых могут быть описаны программами размером меньше s , у вас действительно есть алгоритм, способный решить их все, который включает значение S (s) или эквивалентно алгоритм его вычисления: одна и та же процедура применяется ко всем из них. С другой стороны, если учесть всепроблемы, которые вы упомянули, размер программ, необходимых для проверки предположений о некоторых значениях n , не будет ограничен. Таким образом, аналогичной процедуре потребуются значения S для бесконечного множества s , то есть потребуется внедрить алгоритм вычисления S , которого не существует. Итак: такой общей процедуры не должно существовать. Надеюсь я правильно понял вопрос?

Dabsent ( обсуждение ) 15:56, 2 июня 2008 г. (UTC) [ ответ ]

Да, но я был неясен - я хотел сказать, что для любой фиксированной машины Тьюринга T существует алгоритм (зависящий от T ), решающий ее проблему остановки; но теперь, когда я смотрю на это снова, это на самом деле довольно очевидно, поскольку будет достаточно постоянного алгоритма, возвращающего либо истину, либо ложь (в зависимости от T ). Тот факт, что после фиксирования T вы можете решить проблему его остановки, сначала решив функцию занятого бобра для его размера состояния, является довольно окольным способом сделать это. Dcoetzee 16:53, 2 июня 2008 г. (UTC) [ ответ ]

Судя по статье Чайтена «Вычисление функции занятого бобра», я, по-видимому, слишком поторопился с ответом Дкотзи «нет » . Там утверждается, что на основе теории информации для гипотезы с предикатом P типа, о котором спрашивал Dcoetzee, существует натуральное число m такое, что если P проверяется для конечного числа натуральных чисел n < m , то P должно выполняться для всех n :

«...было бы достаточно иметь ограничение на то, насколько необходимо проверить P , прежде чем утвердить гипотезу, если не было найдено контрпримера, и, конечно, отвергнуть ее, если он был обнаружен. Σ дает эту оценку, для если P имеет сложность размера программы или содержание алгоритмической информации k , то достаточно проверить первые Σ(k + O(1)) натуральных чисел, чтобы решить, всегда ли P истинно». (стр. 3)

Каким бы удивительным это ни казалось, похоже, что на вопрос Дкотзи он отвечает утвердительно.

-- res ( обсуждение ) 19:11, 2 июня 2008 г. (UTC) [ ответить ]

Мне кажется, именно это и стоит в настоящей статье в частном случае гипотезы Гольдбаха (раздел Приложения); это легко обобщается. Но, как я уже сказал, алгоритм зависит от задачи: он не может стать общим алгоритмом именно потому, что функция занятого бобра невычислима. Итак, нет алгоритма, способного определить истинность «какого-то конкретного...», но «Для каждого частного...» алгоритм существует. Квантификаторы, выраженные на естественном языке, являются бесконечным источником непонимания — прошу прощения.

Dabsent ( обсуждение ) 21:01, 2 июня 2008 г. (UTC) [ ответить ]

В разделе «Приложения» такой результат уже хорошо рассматривается непосредственно в терминах функции Радо S , а не Σ , и без ссылки на алгоритмическую теорию информации. На самом деле (более слабый) результат в терминах Σ легко следует из результата в терминах S с помощью любого из различных неравенств, установленных Джулстромом и др. (например, S(n) ≤ Σ(3n+6) ). Я сомневаюсь, что стоит вводить какие-либо из этих поворотов в этот раздел, поскольку он и так читается очень хорошо.

-- res ( обсуждение ) 08:03, 3 июня 2008 г. (UTC) [ ответить ]

Бесконечные занятые бобры?

Мне было интересно, можно ли расширить понятие машин Тьюринга на трансфинитное число состояний или символов. Если, например, мы обозначили состояния натуральными числами (а не в алфавитном порядке) и использовали два алгоритма для определения инструкций в каждом состоянии для символа 0 и для символа 1, можно ли было бы создать машину, которая останавливается после бесконечное количество шагов и/или печатает бесконечное количество единиц? В качестве альтернативы, можем ли мы использовать бесконечное число символов и конечное число состояний? Или бесконечное количество символов и состояний?

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

Наконец, если такое возможно, будет ли иметь значение, какое бесконечное количество шагов оно предпринимает ( vs. vs. vs. и т. д .)? Эбстер Великий ( разговор ) 03:49, 1 октября 2008 г. (UTC) [ ответ ] ${\ Displaystyle \ омега}$ ${\ Displaystyle \ омега +1}$ ${\ Displaystyle \ омега ^ {\ омега}}$ ${\ Displaystyle \ омега _ {1}}$

Это очень классная идея, но я не думаю, что вы сможете построить такую вещь. Вот в чем суть: что значит для ТМ останавливаться после бесконечного количества шагов? Мы можем легко определить состояние, в котором он будет находиться в любой конечный момент времени, но как мы определим, где он будет находиться в данный момент времени ? Возможно, если ТМ находится в очень простом цикле, в котором она остается в одном и том же состоянии все время ≥n, то мы могли бы сказать, что она будет находиться в этом состоянии в момент времени . Но тогда все равно не остановится. Вы столкнетесь и с другими проблемами, например, у вас может закончиться лента (только она длинная!). Извините, Sligocki ( обсуждение ) 12:53, 23 ноября 2008 г. (UTC) [ ответить ]

{\ Displaystyle \ омега}

{\ Displaystyle \ омега}

{\ Displaystyle \ омега}

Идея состоит в том, что ТМ тоже имеет бесконечное количество состояний. Например, если у ТМ есть состояния, и каждое состояние имеет инструкции, следующие какому-то алгоритму, который можно обобщить до бесконечного числа шагов и состояний, то оказывается, что он может выполнять бесконечное количество шагов, проходя через бесконечное число состояния (возможно, некоторые более одного раза) и все равно останавливаются. Длина ленты не будет проблемой, потому что ее всегда можно увеличить. Например, вместо ленты, разделенной на квадраты, вы могли бы иметь плоскость, разделенную на квадраты, и все было бы в порядке. Я не говорю, что такое обобщение возможно (или полезно), но кажется, что оно должно быть. Эбстер Великий ( разговор ) 21:41, 25 ноября 2008 г. (UTC)

{\ Displaystyle \ омега}

{\ Displaystyle \ омега}

\omega \times \omega

[ ответить ]

Вы не можете сделать это точно, поскольку машина Тьюринга с бесконечным количеством состояний потенциально может распознать любую конечную строку или уйти сколь угодно далеко, прежде чем остановиться. Насколько я понимаю, вы можете спросить об эквивалентах Busy Beaver, когда у вас есть доступ к какой-нибудь достаточно простой машине Oracle . JoshuaZ ( обсуждение ) 22:00, 25 ноября 2008 г. (UTC) [ ответить ]

Приложения, гипотеза Гольдбаха

Мне это не кажется правильным. По-видимому, речь идет о гипотезе Гольдбаха: «Существует такое N, что если не существует контрпримеров n < N, то не существует и контрпримеров n > N». И мы находим N, придумывая машину Тьюринга для последовательной проверки контрпримеров, а затем подставляем ее количество состояний и количество символов в функцию занятого бобра.

Итак, во-первых, это массивное заявление. И я полагаю, что это нуждается в некоторой цитате. Во-вторых, я в это не верю, но трудно сказать, почему. Конечно, если вы представляете компьютерную программу, ищущую контрпримеры, память и т. д., это означает, что всегда есть предел тому, как высоко вы можете смотреть. (Думаю, при 2 ГБ ОЗУ мой компьютер не смог бы искать контрпримеры дальше 2^16 000 000 000, по крайней мере, не обращаясь к жесткому диску.) Но мне также трудно представить себе машину Тьюринга, которая могла бы решить эту проблему. — Предыдущий неподписанный комментарий добавлен 58.96.121.81 ( обсуждение ) 05:31, 16 декабря 2008 г. (UTC) [ ответ ]

Это довольно глубокое утверждение. Но хорошо поддерживается. Я добавил документ Chaitin, в котором конкретно указано, что было написано здесь. К сожалению, в этой статье содержится меньше деталей, чем в этой статье в Википедии (она предназначена для теоретиков алгоритмической информации), поэтому она может не помочь вам понять эту концепцию.

Для меня проблема занятого бобра настолько захватывающая из-за того, как много неинтуитивных (или даже невероятных) свойств она имеет. Многие люди рассматривали это странное свойство, и один из способов думать о нем состоит в том, что для нахождения S(n) требуется решить все математические задачи, которые можно закодировать в машине Тьюринга с n состояниями. Следовательно, мы могли бы решить гипотезу Гольдбаха, если бы знали достаточно большое S(n), но для доказательства этого S(n) потребовалось бы решение гипотезы Гольдбаха. Боюсь, что это немного скатывается в философию, но надеюсь, что поможет понять это свойство занятых бобров. Пожалуйста, не стесняйтесь обращаться ко мне, если вы хотите поговорить больше. Sligocki ( обсуждение ) 21:24, 16 декабря 2008 г. (UTC) [ ответить ]

Кроме того, я не знаю, как правильно ссылаться на источники, поэтому тот, кто знает, должен исправить мою попытку. Спасибо! Sligocki ( обсуждение ) 21:26, 16 декабря 2008 г. (UTC) [ ответить ]

Слигоцки, к сожалению, это не очень серьезное утверждение, поскольку функция занятого бобра *невычислима*. Быть невычислимым действительно довольно странно и все такое. Вы не можете найти ответы на проблему занятого бобра в целом. Если бы гипотезу Гольдбаха можно было представить с помощью машины Тьюринга с x-состоянием, то решение сигмы (x) потребовало бы от вас доказательства или опровержения гипотезы Гольдбаха, среди многих других проблем. Решение гипотезы Гольдбаха — более простая задача, чем вычисление сигмы (x). Так что, хотя то, что вы говорите, технически верно, это все равно, что сказать, что огонь — это одно из приложений программы «Аполлон». Так что весь этот раздел, вероятно, следует удалить. 98.218.10.165 ( разговор ) 01:12, 8 мая 2009 г. (UTC) [ ответ ]

Именно в этом суть, на самом деле. Точно так же, как возможность решить проблему остановки позволила бы вам автоматически решить ряд открытых предположений, так же и возможность вычислить функцию занятого бобра. Это сделано для того, чтобы дать некоторое представление о том, почему это должно быть так «сложно». Dcoetzee 01:39, 9 мая 2009 г. (UTC) [ ответить ]

Я также не уверен в пригодности невычислимых функций для решения чего-либо, кроме самих себя. Но в чем я абсолютно уверен, как и все, у кого есть хотя бы некоторые академические математические знания, так это в том, что НЕТ НИ РАЗУ, чтобы конечная машина Тьюринга могла быть запрограммирована для проверки КАЖДОГО четного натурального числа во всем, для чего у них еще нет алгоритма. за. Я темпоральный финитист и не принимаю концепцию актуальной бесконечности, поэтому я рассматриваю натуральные числа не как бесконечное множество, а как сколь угодно большой класс наследственных конечных множеств, и даже я говорю, что Слигоцкий здесь просто не прав. Извиняюсь. Если вы принимаете стандартное понятие БЕСКОНЕЧНО много четных натуральных чисел, вы не можете ни одним КОНЕЧНЫМ методом проверить их ВСЕ по одному.

Но бесконечность не возникает из конечных объектов без определенной аксиомы. Теоремы, рассматривающие ВСЕ четные натуральные числа, могут быть доказаны только с помощью какой-либо индукции или демонстрации того, что они верны для произвольно выбранного числа. Не могу проверить их все. — Предыдущий неподписанный комментарий добавлен 91.133.35.83 ( обсуждение ) 18:42, 28 ноября 2009 г. (UTC)[ ответить ]

Существует алгоритм проверки гипотезы Гольдбаха для любого четного числа. Чтобы проверить это для N, мы просто вычисляем все простые числа p, меньшие N, и смотрим, является ли Np простым. Для этого существует множество вычислимых алгоритмов (например, решето Эратосфена ). Если это работает, мы продолжаем и проверяем следующее четное число, в противном случае мы терпят неудачу. Вопрос в том, терпим ли мы когда-нибудь неудачу? Если это так, то гипотеза Гольдбаха опровергнута контрпримером. Если этот алгоритм никогда не останавливается, то гипотеза Гольдбаха верна. Таким образом, знание числа занятых бобров сделало бы гипотезу Гольдбаха вычислимой. Ура, — sligocki ( обсуждение ) 08:47, 29 ноября 2009 г. (UTC) [ ответить ]

Вы правы, с помощью этого алгоритма мы не можем проверить все четные числа за конечное время. Но, если Гольдбах верен, в конце концов он проверит каждое четное число . Таким образом, он гарантированно найдет любой контрпример и гарантированно никогда не остановится, если контрпримеров нет. Таким образом, существует связь между значением функции занятого бобра и гипотезой Гольдбаха без ссылки на какие-либо бесконечности. Ура, — sligocki ( обсуждение ) 23:13, 30 ноября 2009 г. (UTC) [ ответить ]

Мои извинения г-ну Чайтину, который никогда не заявлял, что его константа или Занятые бобры могут быть использованы для решения задач Римана или Гольдбаха, в отличие от утверждений кого-то на странице констант Чайтина. Вы не можете проверить каждое четное число в конце концов«без ссылки на какие-либо бесконечности», если только вы не настоящий твердолобый ультрафинитист, отрицающий существование более чем конечного числа целых чисел. Если теорема Гольдбаха верна, то какую бы большую машину Тьюринга вы ни построили, она может проверять только первые n четных целых чисел. У вас не может быть алгоритма с вычислимой длиной, проверяющего все числа. Если вы не найдете контрпример ниже числа, полученного путем вычисления функции Занятого Бивера машин Тьюринга с программами длиной, равной числу Грэма, это ВСЕ ЕЩЕ не доказывает, что контрпримера не существует. Проверяя цифры, вы можете только доказать, что это неправильно, но никогда правильно. Чтобы доказать это правильно, вам нужна индукция или какая-то другая ТЕОРЕМА. Я не говорю, что Занятый Бобер Это может быть полезным инструментом для нахождения больших простых или совершенных чисел или для доказательства ошибочности Гольдбаха, если он неверен, и для получения сколь угодно больших нижних оценок для возможного контрпримера. НЕ "гарантировано найти какой-либо контрпример". Только любой контрпример ниже любой заданной границы, пусть большой, но все же конечный.

Конечно, существует крохотная проблема, заключающаяся в том, что Занятые Бобры невычислимы и растут быстрее, чем любая вычислимая функция, поэтому единственный способ найти Занятого Боба для класса машин Тьюринга — запустить каждую возможную программу и в какой-то момент доказать, что все все еще продолжается, никогда не закончится, сложность такого доказательства также растет с невычислимой скоростью, а затем объявляется машина, которая проработала дольше всего, прежде чем остановить самого занятого бобра. Во время этого процесса вы перебрали все возможные алгоритмы этого класса, но в следующий раз вы можете присвоить им другое значение. Я думаю, что создание квантового компьютера предлагает гораздо более осуществимые перспективы в поисках более крупных и лучших средств для дробления чисел.

Посетите веб-сайт Грегори Чайтина, он может многое сказать о многих предметах, вычислимость — лишь один из них. Я еще раз извиняюсь за то, что поспешно обвинил его в том, что кто-то сделал ложные выводы из его удивительной работы.

Довольно недавняя лекция о вычислимости, в которой он неоднократно заявляет, что вы можете доказать только гипотезу Римана или гипотезу об отсутствии нечетных совершенных чисел или вообще любую гипотезу, эквивалентную проблеме остановки, НЕПРАВИЛЬНО здесь: http://www.cs.auckland.ac. nz/~chaitin/wlu.html Хотя он конкретно не называет Гольдбаха или a,b,c,d>1 a^b+1=c^d только тогда, когда a=d=2 и b=c=3 там они также имеют тип, эквивалентный проблеме остановки. — Предыдущий неподписанный комментарий добавлен 91.133.35.83 ( обсуждение • вклад ) 07:56, 5 декабря 2009 г.

Уважаемый 91.133.35.83, я не понимаю вашего рассуждения об ультрафинитизме или дроблении чисел, но вы не правы. Чайтин ясно говорит в своей статье (стр. 3 в середине страницы):

“

Занятый Бобер также представляет значительный метаматематический интерес; в принципе было бы чрезвычайно полезно знать большие значения Σ( n ). Например, это позволило бы решить гипотезу Гольдбаха и гипотезу Римана , а фактически любую гипотезу, такую как гипотеза Ферма, которую можно опровергнуть числовым контрпримером.

”

и он продолжает объяснять, как именно. Он специалист в этой области, и он прав. Но позвольте мне пойти дальше, вот конечная программа на Python, которая будет искать контрпример к гипотезе Гольдбаха:

def  goldbach_check ():  """Проверяйте гипотезу Гольдбаха для каждого четного числа N, пока она не подведет. Если она никогда не подведет, никогда не возвращайтесь."""  N  =  4  while  True :  # Проверяйте гипотезу Гольдбаха для N.  if  not  sum_of_primes ( N ) :  return  N  # Если N не является суммой двух простых чисел, ошибка.  # В противном случае попробуйте следующее четное число.  Н  +=  2def  sum_of_primes ( N ):  """Является ли N суммой 2 простых чисел?"""  # Попробуйте все способы, которыми N может быть суммой 2 целых чисел.  для  k  в  диапазоне ( N ):  если  is_prime ( k )  и  is_prime ( N - k ):  вернуть  True  # N является суммой двух простых чисел (k и Nk)  # Если ничего не работает, то N не является суммой двух простых чисел .  вернуть  ложь

Теперь, если существует четное число N, не являющееся суммой двух простых чисел, goldbach_check() вернет его. Таким образом, если гипотеза Гольдбаха ложна, этот алгоритм предоставит контрпример. И наоборот, если эта программа никогда не останавливается, это означает, что гипотеза Гольдбаха верна. Как мы узнаем, будет ли программа останавливаться каждый раз? Занятые номера бобра. Ура, — sligocki ( обсуждение ) 09:42, 5 декабря 2009 г. (UTC) [ ответить ]

"и он продолжает объяснять, как именно" Объяснение выглядит следующим образом

«Экспериментальный подход заключается в использовании быстрого компьютера для проверки истинности Р, скажем, для «первого миллиарда натуральных чисел». проверить P, прежде чем утверждать гипотезу, если контрпример не найден, и, конечно, отклонить ее, если он был обнаружен. SIGMA обеспечивает эту оценку, поскольку, если P имеет сложность размера программы или алгоритмическую информативность k, исследуйте первые SIGMA(k + O(1)) натуральные числа, чтобы решить, всегда ли верно P. Обратите внимание, что сложность размера программы или алгоритмическая информативность известной гипотезы P обычно довольно малы; увлечься гипотезой, на изложение которой уйдет сотня страниц».

Ни Гольдбах, ни Риман не имеют такой же сложности, как программа, или алгоритмического информационного содержания. Прочитайте более новую статью.

Вот ошибка в программе: Подпрограмма

# Попробуйте все варианты, когда N может быть суммой двух целых чисел. для k в диапазоне (N): если is_prime(k) и is_prime(Nk): return True # N — сумма двух простых чисел (k и Nk) # Если ничего не работает, то N не является суммой двух простых чисел.

бесконечно усложняется. Проверять нужно только суммы нечетных целых чисел, то есть N/4 способов. Вы можете немного улучшить, но он будет расти со скоростью N/k, где k не так много. «скажем, для первого миллиарда натуральных чисел». Для N = 1 000 000 000 это, безусловно, более 1 000 000 шагов. Для N = 1 000 002 это то же количество НОВЫХ шагов, ни один из которых ранее не выполнялся. Программа конечна в Python, но ни одна конечная машина Тьюринга не является моделью даже для подпрограммы.

Также нет общей функции "is_prime". Общего конечного алгоритма также не существует. Решето Эрастотена длиннее для больших чисел. Конечно, нет машины Тьюринга или подпрограммы «is_prime». Для каждого нового N вам нужно проверить, является ли N-3 простым. Rantalaiho74 ( обсуждение ) 18:21, 1 октября 2010 г. (UTC) aka91.133.35.83 [ ответить ]

КТ-тезис

«Есть аналог функции Σ для машин Минского… Это следствие тезиса Черча-Тьюринга». Пожалуйста, извините меня, если я неправильно понимаю концепции здесь. Я думал, что эквивалентность регистровых машин и машин Тьюринга была математической теоремой, тогда как КТ-тезис был недоказанным философским утверждением. Если вместо этого будет сказано: «Существует аналог для регистровых машин, потому что кто-то доказал, что они эквивалентны», возможно, с последующим «вероятно, невозможно вычислить функцию каким-либо образом из-за тезиса CT». — Предыдущий неподписанный комментарий добавлен 24.2.48.202 ( обсуждение ) 20:02, 9 января 2009 г. (UTC) [ ответ ]

Это звучит как законное беспокойство для меня. Тезис Черча-Тьюринга не является теоремой, и нам следует избегать формулировок, ссылающихся на него как на таковой. Dcoetzee 21:05, 9 января 2009 г. (UTC) [ ответ ]

Да, я согласен, и это утверждение было излишним, исходя из вступительного абзаца к разделу, поэтому я удалил его. Возможно, следует сказать кое-что о том, почему в любой формальной модели вычислений есть аналогия с занятым бобром. На самом деле похоже, что модель вычислений в статье Википедии скорее отсутствует. Sligocki ( обсуждение ) 21:03, 15 января 2009 г. (UTC) [ ответить ]

Нижние границы Грина

В разделе «Известные значения» настоящей статьи говорится следующее:

Милтон Грин построил набор машин, демонстрирующих, что
: (Где обозначение стрелки вверх Кнута, а A - функция Аккермана ) $\Sigma (2k+4)>3\ \uparrow ^{k}3>A(k,k)$  $\uparrow$ в его статье 1964 года «Нижняя граница сигма-функции Радо для бинарных машин Тьюринга».

Это кажется (возможно, неверным?) результатом кого-то другого, а не Грина. У меня нет статьи Грина, но у меня есть две статьи, в которых она обсуждается, и они, кажется, не поддерживают вышеуказанное неравенство. Первая статья называется « Улучшенные границы функций, связанных с занятыми бобрами » Бен-Амрама и Петерсена, 2002 г., в которой (на стр. 3) просто цитируется работа Грина 1964 г., показывающая, что Σ(4n + 3) > A(n,n), где А — функция Аккермана. (Обратите внимание на «4n + 3», а не на «2n + 4».) Вторая статья - это функция Аккермана в числах единиц, сгенерированных машинами Грина, автор Джулстром, 2002. В этой статье обсуждается функция f _M(x, y) (чье определение очень похоже на определение функции Аккермана), которое представляет собой количество единиц, оставшихся на ленте машиной Грина с состоянием 2x при запуске с самой правой единицы ленты, содержащей блок y 1 с. Такой блок y 1 может быть получен с помощью TM с состоянием (y+1), запущенного на ленте со всеми 0, поэтому, очевидно, имеется нижняя граница Σ(2x+y+1) ≥ f _M (x,y) ; например, y = 3 дает Σ(2x+4) ≥ f _M (x, 3). Однако это не поддерживает неравенство, указанное в статье, поскольку обычно f _M (x, 3) > 3 ^ ^ ... ^ 3 (со стрелками вверх) не так; например, можно найти f _M (3,3) = 45 < 3^^^3. Возможно, неравенство должно быть Σ(2k+4) > 3^^...^3 (с k-2 3s) > A(k-2,k-2)?

- рез 14:52, 16 ноября 2009 г. (UTC) [ ответ ]

Да, я написал эту часть, и некоторые из них являются моим собственным оригинальным исследованием, извините. Я посмотрю исходные уравнения, которые я использовал для этих неравенств, и вернусь к вам. Ура, — sligocki ( обсуждение ) 16:33, 16 ноября 2009 г. (UTC) [ ответить ]

К сожалению, я потерял копию статьи Грина, которая у меня была. Но я записал, что в своей статье он дает уравнение для роста своих машин, как

B_{n}(0)=1

B_{1}(m)=m+1

B_{n}(m)=1+B_{n-2}[1+B_{n}(m-1)]

а также

BB_{n}=B_{n-2}[B_{n-2}(1)]

для n нечетных и

BB_{n}=1+B_{n-3}[1+B_{n-3}(3)]

для п даже

BB _n — это оценки Sigma для машин Грина. Из этих повторений я вывел связь с функцией стрелки вверх и функцией Аккермана. ~~Меня также смутила переплетенная форма бумаги Бен-Абрама.~~ (ой, неправильно прочитал предыдущий пост — sligocki ( обсуждение ) 03:22, 18 ноября 2009 г. (UTC) ) Ура, — sligocki ( обсуждение ) 16:48, 16 ноября 2009 г. (UTC) [ ответ ]

Так,

B_{3}(m)=B_{3}(m-1)+3=3m+1>3m

B_{5}(m)=3B_{5}(m-1)+4>3B_{5}(m-1)>3\uparrow m

И предполагая :

B_{2(k-1)+3}(m)>3\uparrow ^{k-1}m

B_{2k+3}(m)>3\uparrow ^{k-1}B_{2k+3}(m-1)>3\uparrow ^{k}m

Так что:

BB_{2k+5}=B_{2k+3}(B_{2k+3}(1))>3\uparrow ^{k}(3\uparrow ^{k}1)=3\uparrow ^{k}3

BB_{2k+4}>B_{2k+1}(B_{2k+1}(3))>3\uparrow ^{k-1}(3\uparrow ^{k-1}3)=3\uparrow ^{k}3

Кроме того, на основе статьи о функции Аккермана . Это выводы, которые я сделал. Ура, — sligocki ( обсуждение ) 03:18, 18 ноября 2009 г. (UTC) [ ответить ]

3\uparrow ^{k}3>A(k+2,0)=A(k,A(k+1,0))>A(k,k)

Я повторно приобрел копию статьи Грина. ~~Примечательно: номера, которые я назвал здесь, он называет и $G_{n}$ $BB_{n}$~~ использует [Грин] для другой последовательности машин (машин класса G), которые, по-видимому, являются теми, на которые ссылается Бен-Абрамс. С другой стороны, Джулстрем говорит о машинах класса М, которые являются еще одним классом, используемым Грином в статье. Таким образом, я считаю, что все мы ограничиваем совершенно разные машины. Ура, — sligocki ( обсуждение ) 04:26, 18 ноября 2009 г. (UTC) [ ответить ] $G_{n}$

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

3\uparrow ^{k}3

- рез 15:32, 19 ноября 2009 г. (UTC) [ ответ ]

Спасибо за подтверждение. Я думаю, что выражение 3 ^ (k) 3 в основном совпадение. Если вы проанализируете машины класса M и класса G, вы обнаружите, что они растут с разной скоростью. Я думаю, что M-класс растет аналогично 2 ^(k) n+1 на ленте, начинающейся с n 1s, а G-класс растет аналогично 3 ^(k) n+2, но их можно легко определить даже для машин, которые будет расти как 2 ^(k) n+2. Тем не менее, я был очень доволен тем, насколько естественными были эти нижние границы, я также пытался получить некоторые верхние границы, и это было не так хорошо, вы можете увидеть некоторые из моих частичных анализов в User:sligocki/Green's numbers . Дайте мне знать, если у вас есть какие-либо идеи :) Ура, — sligocki ( обсуждение ) 23:34, 19 ноября 2009 г. (UTC) [ ответ ]

У меня не было времени изучить эти результаты столько, сколько мне бы хотелось. (Кстати, в вашей статье все еще есть ссылка на G _n , который предположительно должен быть BB _n .)

Однако в стороне я замечаю, что следствием

\Sigma (2k)>3\uparrow ^{k-2}3\quad (k\geq 2)

состоит в том, что она ставит в неловкое положение оценку для Σ(12), приведенную Дьюдни в настоящей статье. В частности, полученная оценка оказывается в точности числом g 1 в последовательности Грэма; то есть,

\Sigma (12)>3\uparrow ^{4}3=g_{1}

.

Обсуждение числа g 1 может помочь обычному читателю увидеть, насколько оно значительно больше экспоненциальной башни, приведенной у Дьюдни.

- рез 14:14, 22 ноября 2009 г. (UTC) [ ответ ]

Для, возможно, более прямого способа видения, который подразумевается в результатах Грина, мы можем определить $\quad \Sigma (2k)>3\uparrow ^{k-2}3\quad (k\geq 2)$

$b_{k}(n)=B_{2k+1}(n)\quad (k\geq 1,\ n\geq 0)\quad$ и , отметив, что $\quad c_{k}(n)=3\uparrow ^{k-1}n\quad (k\geq 1,\ n\geq 0)$

$b_{k-2}(n)=B_{2k-3}(n)\quad (k\geq 3,\ n\geq 0)$ и это . $c_{k}(c_{k}(3))=3\uparrow ^{k}3\quad (k\geq 1)$

Тогда определение Грина B-функций дает

$b_{1}(n)=3n+1\quad (n\geq 0)$

$b_{k}(0)=1\quad (k\geq 2)$

$b_{k}(n)=1+b_{k-1}(1+b_{k}(n-1))\quad (k\geq 2,\ n\geq 1)$

которое можно напрямую сравнить построчно с определением c-функций:

$c_{1}(n)=3n\quad (n\geq 0)$

$c_{k}(0)=1\quad (k\geq 2)$

$c_{k}(n)=c_{k-1}(c_{k}(n-1))\quad (k\geq 2,\ n\geq 1)$ ,

давая желаемое неравенство:

$BB_{2k}>B_{2k-3}(B_{2k-3}(3))=b_{k-2}(b_{k-2}(3))>c_{k-2}(c_{k-2}(3))=3\uparrow ^{k-2}3\quad (k\geq 3)$ .

Следовательно

$\Sigma (2k)>3\uparrow ^{k-2}3\quad (k\geq 2)$ ,

где случай k = 2 рассматривается отдельно и следует из известного значения Σ(4) = 13.

- рез 14:20, 23 ноября 2009 г. (UTC) [ ответ ]

Неинтересное заявление

В статье говорится: «Для каждого входа n существует алгоритм An, который выводит число Σ(n) (см. примеры)». Но что в этом примечательного? Это верно для всех целочисленных функций, и определение такого алгоритма тривиально. - Gigasoft 84.211.109.82 ( обсуждение ) 04:51, 3 апреля 2010 г. (UTC) [ ответить ]

Имхо, процитированное утверждение — банальность, которую стоит подчеркнуть для читателей, незнакомых с предметом. Я полагаю, что у таких читателей есть склонность, впервые столкнувшись с фактом, что «Σ невычислима», ошибочно думать, что это подразумевает, что существует некоторое n , для которого Σ( n ) невычислимо. — рез ( обсуждение ) 13:47, 3 апреля 2010 г. (UTC) [ ответить ]

То же. Это довольно тонкое различие, которое заслуживает должного внимания. Но не стесняйтесь редактировать формулировку, если вы не думаете, что причина этого акцента ясна. Ура, — sligocki ( обсуждение ) 04:29, 8 апреля 2010 г. (UTC) [ ответить ]

Раздел «Невычислимость Σ»

Здесь было написано:

Тривиальный, но примечательный факт состоит в том, что любая конечная последовательность значений Σ, такая как Σ(0), Σ(1), Σ(2),..., Σ( n ) для любого заданного n , вычислима.

Но почему "тривиально"? Возможно, для какого -то n существовала бы такая машина Тьюринга, что мы не могли бы определить, останавливается она или нет.

Eugepros ( обсуждение ) 11:18, 5 августа 2010 г. (UTC) [ ответить ]

О, извините, я понимаю. Машина Тьюринга сама по себе является таким алгоритмом: даже если мы не можем определить, останавливается она или нет, предикат «она останавливается» определяется как частично рекурсивная (но не обязательно полностью рекурсивная) функция. Может, стоит объяснить подробно?

Eugepros ( обсуждение ) 10:56, 9 августа 2010 (UTC) [ ответить ]

Примечателен тот факт, что для любого конечного n последовательность Σ(0), Σ(1), Σ(2),..., Σ( n ) тривиально вычисляется такой программой, как «PRINT <Σ(0 )>, <Σ(1)>, <Σ(2)>, ..., <Σ( n )>", где <x> обозначает десятичное представление x. Например, как упоминалось в Computable_function#Examples , «PRINT 0, 1, 4, 6, 13» тривиально вычисляет Σ(0), Σ(1), Σ(2), Σ(3), Σ(4). Подобная программа существует для каждого конечного n , тогда как для всей бесконечной последовательности такой программы не существует (поскольку программа по определению представляет собой строку конечной длины). Пожалуй, этот факт не следует называть тривиальным, поскольку онэто тривиально. Я переформулировал предложение соответствующим образом. — рез ( обсуждение ) 16:22, 9 августа 2010 г. (UTC) [ ответить ]

Еще один момент... Машина Тьюринга ББ, которая оставляет на ленте Σ( n ) единиц, может не служить алгоритмом для Σ( n ), потому что стандартные соглашения (в отличие от игры BB) требуют, чтобы '1', которые кодируют выходные данные, находиться в непрерывном блоке. (отредактировано) — рез ( обсуждение ) 01:51, 10 августа 2010 г. (UTC) [ ответить ]

Хм, я не понимаю, почему "Похожая программа существует для каждого конечного n ". На самом деле я знаю, что в нашем распоряжении нет даже программы для "PRINT <Σ(10)>". И мы можем столкнуться с фундаментальными математическими проблемами, пытаясь найти число Σ(10), потому что проблема остановки для некоторой машины Тьюринга (из 10 состояний) может оказаться неразрешимой. Разве мы не можем? — Eugepros ( разговор ) 11:22, 10 августа 2010 г. (UTC) [ ответить ]

О, прошу прощения за непреднамеренное применение конструктивной логики . Я понимаю, что вы выводите «Σ (10) существует » из «каждой 10-й машины Тьюринга состояния или останавливается, или нет ». Но эта аксиоматика для меня слишком сильна... Меня интересует, что могут сказать о вычислимости Σ( n ) те, кто не принимает закон исключенного третьего ... Евгений ( разговор ) 12:28, 10 авг. 2010 (UTC) [ ответить ]

Я думаю, что когда вы говорите: «И мы можем столкнуться с фундаментальными математическими проблемами, пытаясь найти число Σ(10), потому что проблема остановки для некоторой машины Тьюринга (с 10 состояниями) может оказаться неразрешимой. Разве мы не можем?», вы на самом деле задавая тот самый вопрос, который касался Радо и Лин в первую очередь. Как я отметил в предыдущем разделе «Невычислимость Σ: подчеркивая возможную ловушку », Радо и Лин прямо заявили, что они искали «подсказки относительно формулировки плодотворной концепции эффективной вычислимости (и невычислимости) отдельных четко определенных целые числа ». Насколько я знаю, такая концепция еще не сформулирована, и я не знаю, в какой степени конструктивная логика может играть роль.
( разговор ) 16:49, 10 августа 2010 (UTC) [ ответить ]

Что касается роли конструктивной логики: Насколько мне известно, она была специально разработана для ответов на такого рода вопросы. Конструктивное доказательство существования такого индивидуального целого числа (например, Σ(10)) должно быть доказательством его «эффективной вычислимости». Или я что-то неправильно понял? Eugepros ( обсуждение ) 08:44, 11 августа 2010 (UTC) [ ответить ]

Какую бы роль ни могла (или не могла) сыграть конструктивная логика в этом вопросе, очевидно, сами Радо и Лин считали ее неадекватной своим целям. Я говорю это потому, что конструктивная логика уже была хорошо развита, когда они написали (в 1963 г.), что «в настоящее время не существует формального понятия для «эффективной вычислимости» отдельных четко определенных целых чисел, таких как Σ(4), Σ(5) , ...", и что, следовательно, "конечно, невозможно сформулировать в точной форме гипотезу о том, что существуют значения n , для которых Σ( n ) не вычислима эффективно(Пожалуйста, извините за выделение жирным шрифтом, но я думаю, что это предположение важно и, как бы плохо оно ни было сформулировано, вероятно, заслуживает упоминания в статье.) Кроме того, Радо писал ранее в статье 1962 года, что «этот [принцип самый большой элемент] ... может вывести нас далеко за пределы области конструктивной математики», поэтому кажется, что они намеренно выходили за рамки конструктивной математики , чтобы сформулировать еще недоступные концепции
. UTC) [ ответить ]

Относительно гипотезы о том, что «существуют значения n , для которых Σ( n ) не поддается эффективному вычислению», я думаю, было бы точнее сказать, что можно сформулировать , но невозможно доказать . Эта гипотеза формализуется так же, как и в конструктивном исчислении предикатов . Но это не случай классического исчисления предикатов , потому что в последнем оно тривиально опровергнуто (используя закон исключенного третьего). $\exists n\not \exists x~x=\Sigma (n)$

В конструктивной логике (см. интерпретацию Брауэра-Гейтинга-Колмогорова ) доказательством является пара отдельного числа n и доказательство . Последнее доказательство — импликация к абсурду из догадки , означает, что мы должны найти такую индивидуальную машину Тьюринга M , для которой неразрешимо — останавливается она или нет. Мы не можем формализовать понятие «доказанной неразрешимости» для отдельной проблемы остановки машины Тьюринга. Таким образом, мы не можем доказать гипотезу , но можем ее сформулировать, и это утверждение не является «тривиально ложным» в конструктивном смысле. $\exists n\not \exists x~x=\Sigma (n)$ $\not \exists x~x=\Sigma (n)$ $\exists x~x=\Sigma (n)$ $\exists n\not \exists x~x=\Sigma (n)$

Это мое мнение, возможно, оно ошибочно... Eugepros ( обсуждение ) 10:18, 12 августа 2010 г. (UTC) [ ответить ]

Я бы сказал, что это определенно неправильно по уже указанным причинам. Радо и Лин ясно объясняют, что гипотеза пока не может быть точно сформулирована, потому что она включает понятие, которое еще не может быть должным образом формализовано. В частности , для данного значения n их понятие «Σ( n ) не является эффективно вычислимым», очевидно, не формализуется только посредством . Обратите внимание, что конструктивная логика, интерпретация BHK и интерпретация реализуемости Клини были хорошо развиты в то время, и именно Клини предоставил Радо и Лин информацию о том, что их концепция еще не может быть правильно сформулирована. - рез ( разговор ) 17:49, 12 августа 2010 г. (UTC)

(\not \exists x~x=\Sigma (n))

[ ответить ]

Начальное состояние

Я не могу найти никакого упоминания о начальном состоянии (начальном состоянии), с которого должен начинаться «запуск машины». Или я просто слепой?
- Х.Марксен ( разговор ) 16:35, 26 августа 2010 г. (UTC) [ ответ ]

Кажется, это было упущение. Я сделал это явным, а также попытался улучшить некоторые формулировки в этом разделе («Игра занятого бобра»).
— рез ( обсуждение ) 17:48, 27 августа 2010 г. (UTC) [ ответить ]

Хорошая переформулировка. — sligocki ( обсуждение ) 14:21, 28 августа 2010 г. (UTC) [ ответить ]

Σ(2,3) и S(2,3)

Привет, я недавно видел, что редактирование, в котором говорится, что Σ(2,3) = 9 и S(2,3) = 38, было отменено, поскольку «нет опубликованных доказательств». Однако на веб-сайте Паскаля Мишеля есть ссылка на Lafitte and Papazian 2007 в качестве доказательства, доступного по адресу http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.104.3021&rep=rep1&type=pdf#page= 231 Это считается неубедительным или не опубликовано? Спасибо - Yves - Предыдущий неподписанный комментарий добавлен 193.49.219.185 ( обсуждение ) 09:35, 3 сентября 2010 г. (UTC) [ ответ ]

Спасибо за ссылку! Да, я принимаю это как опубликованное доказательство, и я отметил пользователя: Sligocki , который сделал возврат. Может быть, теперь он хочет отменить возврат. -- Х.Марксен ( разговор ) 17:20, 3 сентября 2010 г. (UTC) [ ответить ]

Подождите... Я поторопился : дело еще не до конца решено, ИМХО. Я собираюсь продолжить с объяснением. -- Х.Марксен ( разговор ) 12:09, 4 сентября 2010 г. (UTC) [ ответить ]

У меня есть конкретное сомнение и общая проблема с представлением доказательства для некоторого значения Σ или S. Начну с моего конкретного сомнения:

На странице 222, раздел 3.1, Лафит и Папазян (сокращенно L&F) говорят: «Кроме того, мы принимаем первый переход (состояние A на 0) как запись 1, переход вправо и вход в состояние B».
Проблема с «записью 1»: это нормально для вычисления Σ, так как можно легко показать, что исключение всех «пишущих 0» машин не приведет к максимальному значению Σ.
Для вычисления S я не знаю такого доказательства. Я могу показать, что максимальное количество шагов при написании ПП-0 не более чем на (n-1) больше, чем максимальное количество шагов при написании ПП-1, но не более того.
Следовательно, у меня есть некоторые сомнения в том, что может существовать ТМ записи-0, которую L&P не учел в своих вычислениях, которая делает 38+(2-1) = 39 шагов и оставляет менее 9 пробелов.

Более общая проблема, с которой я столкнулся, заключается в следующем: сколько подробностей должно быть опубликовано, чтобы их можно было принять в качестве окончательного доказательства для частного случая Σ и/или S?

Для математического доказательства (то есть там, где мы находимся) традиционно нужно дать достаточно подробностей для знающего читателя, чтобы он мог переосмыслить это доказательство и полностью убедиться в его правильности.
В данном случае такое доказательство было бы слишком большим. Публиковать не имеет смысла.
Авторы никогда не писали такого доказательства. Они написали несколько программ, которые построили (или, по крайней мере, легко могли) построить такое доказательство. На стр. 225 L&P говорит: «Наша программа может вывести длинное доказательство…». Хорошо, но:
Как и все другие читатели их статьи, я не имею доступа к такому выводу, а также к программам, которые L&P использует для этого.

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

Это звучит "справедливо". Они действительно много работали над этим, и, возможно, программа никогда не планировалась к публикации (некрасива или не очищена внутри).
Это может быть хорошей идеей: вторая реализация — гораздо лучшая проверка, чем проверка только одной реализации.
Они дали достаточно информации о методах, используемых программой для подсчета ТМ.
Для обнаружения неостанавливающихся ТМ они не дают подробностей реализации, а дают подробную классификацию, например, «есть X ТМ, которые делают Y с периодом в Z шагов». Это можно считать подсказкой реализации и использовать для проверки правильности второй реализации.

На самом деле, я (пока) не написал такую вторую реализацию.

Теперь я не совсем уверен, как судить о газете L&P. Брейди в 1983 году дал гораздо больше деталей, чтобы установить (4,2), но это не означает, что все остальные должны делать то же самое. Я даже не уверен, действительно ли эта масса подробностей, приведенных Брейди, имеет значение, поскольку я не уверен, что любой читатель действительно может быть уверен, что проверил их все . Какое бремя может возложить автор на своих читателей?

Любые предложения или идеи?
-- Х.Марксен ( разговор ) 12:51, 4 сентября 2010 г. (UTC) [ ответить ]

Следить за собой... Очевидно, мне еще предстоит многому научиться. Тем временем я узнал о способе построения этой энциклопедии, например, WP:IRS . Кажется, я перепутал работу ученого с работой автора википедии. Последнее рассматривается не как оценка содержания научных публикаций, а скорее как оценка их достоверности.

В этом случае у нас есть доклад на конференции, написанный двумя математиками. Вроде вполне нормальный первоисточник. Никаких намеков на сомнения. Он опубликован и так же надежен, как и большинство других публикаций. Есть только 1 цитата из более поздней работы первого автора. В соответствии с рекомендациями Википедии вторичный источник был бы предпочтительнее, но тема «трудолюбивые бобры» настолько мала (по количеству публикаций), что вторичных публикаций по этой теме вообще не существует, и ожидание большего количества цитат или даже вторичные публикации означали бы удаление темы из Википедии, по крайней мере, частично.

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

Поскольку я все еще чувствую себя немного сбитым с толку, я хотел бы получить отзывы от людей с большим опытом работы в качестве автора википедии, прежде чем я продолжу и внесу изменения.
— Х.Марксен ( разговор ) 01:25, 6 сентября 2010 г. (UTC) [ ответить ]

Привет Хайнер, Прежде всего хочу поблагодарить Вас за Ваш экспертный анализ, я не осознавал степень сложности таких доказательств. Будучи гораздо больше читателем, чем редактором в Википедии (лишь изредка, часто для мелких правок, аккаунта у меня пока нет), могу лишь высказать свое мнение по данному конкретному вопросу. Для Σ(2,3) и S(2,3) опубликован только этот источник (L&P), и, видя ваш анализ, я могу предположить вероятную причину, по которой Слигоцкий сделал возврат: согласно веб-сайту Паскаля Мишеля, он нашел независимое доказательство но это еще не опубликовано; таким образом, у него есть экспертное заключение о степени достоверности доказательства, заявленного LP, и он не убежден до тех пор, пока не сможет опубликовать себя в качестве независимого подтверждения. Поэтому ситуация такова: Σ(2,3) и S(2, 3) были заявлены равными 9 и 38 в соответствии с L&P, но консенсус сообщества (включая вас) еще не достигнут. Я бы предложил изменить таблицу, но с этой оговоркой, которая будет хорошо видна. Мне было бы интересно узнать мнение Слигоцкого по этому поводу. - Ив — Предыдущий неподписанный комментарий добавлен 193.49.219.185 ( обсуждение ) 15:11, 6 сентября 2010 г. (UTC) [ ответ ]

Всем привет, простите, что так поздно на игру. Как и Хайнер, я раньше не слышал о работе Лафита и Папазяна и слышал только о заявленных неопубликованных доказательствах того, что класс 3-символьных машин с двумя состояниями вычислим. На самом деле, мы с отцом также классифицировали все ТМ 2x3 в нормальной форме дерева, хотя мы не были бы достаточно уверены в них, чтобы опубликовать статью. Тем временем я просмотрю статью, и если Хайнер или Паскаль сочтут это доказательство верным, я не стесняюсь добавить его обратно. Точно так же я полностью согласен с тем, что мы могли бы добавить примечание о том, что доказательство было представлено, хотя и не проверено. Счастливого занятого бобра, — sligocki ( обсуждение ) 17:24, 6 сентября 2010 г. (UTC) [ ответить ]

Привет (у меня тот же адрес, что и 193.49.219.185), спасибо, Шон, за твое вмешательство. Поскольку я не специалист в области компьютерных наук (моей областью является материаловедение), я не знаю точно, как проходит рецензирование статей на конференциях, таких как L&P. Однако можно сказать, что: (i) L&P представила свои доказательства публично, не получив опровержений, (ii) документ судебного разбирательства был проверен и, таким образом, вероятно, не содержит грубых методологических ошибок, (iii) документ не был опровергнут с тех пор, как затем (2007 г.) и (iv) он был процитирован П. Мишелем в качестве доказательства; П. Мишель, вероятно, внимательно прочитал его, не найдя серьезных возражений. Таким образом, доказательство в этом отношении выдерживает критику. Но, так же как и другая интересующая меня область (открытие сверхтяжелых ядер), хотя и ценная, это доказательство все еще является предположением, ожидающим независимого подтверждения. Из-за присущей ему сложности, нехватки специалистов и нехватки времени специалистов подтверждение AFAIK может занять несколько лет. Хороший пример приведен на форуме Д.Бриггса по завершению случая (5,2): разрешение 43 несоответствий — это только первый шаг доказательства, необходимый для снижения уровня неопределенности (на сегодняшний день один или несколько из этих возражений все еще могут, наконец, остановиться после миллиардов или триллионов шагов, взорвав нынешние значения Σ(5,2)/S(5,2)), но этого недостаточно для твердого установления доказательства, уровень сложности которого, безусловно, намного выше, чем для (2,3) случай. (кстати, я бы предложил добавить форум Д. Бриггса в качестве ссылки). - Ив форум по завершению дела (5,2): разрешение 43 несогласных - это только первый шаг доказательства, необходимого для снижения уровня неопределенности (на сегодняшний день один или несколько из этих несогласных все еще могут окончательно остановиться после миллиардов или триллионов шагов, взрывающих нынешние значения Σ(5,2)/S(5,2)), но недостаточных для твердого установления доказательства, уровень сложности которого, безусловно, намного выше, чем для случая (2,3). (кстати, я бы предложил добавить форум Д. Бриггса в качестве ссылки). - Ив форум по завершению дела (5,2): разрешение 43 несогласных - это только первый шаг доказательства, необходимого для снижения уровня неопределенности (на сегодняшний день один или несколько из этих несогласных все еще могут окончательно остановиться после миллиардов или триллионов шагов, взрывающих нынешние значения Σ(5,2)/S(5,2)), но недостаточных для твердого установления доказательства, уровень сложности которого, безусловно, намного выше, чем для случая (2,3). (кстати, я бы предложил добавить форум Д. Бриггса в качестве ссылки). - Ив 2) значения), но недостаточны для твердого доказательства, уровень сложности которого заведомо намного выше, чем для случая (2,3). (кстати, я бы предложил добавить форум Д. Бриггса в качестве ссылки). - Ив 2) значения), но недостаточны для твердого доказательства, уровень сложности которого заведомо намного выше, чем для случая (2,3). (кстати, я бы предложил добавить форум Д. Бриггса в качестве ссылки). - Ив — Предыдущий неподписанный комментарий добавлен 77.196.150.149 ( обсуждение ) 21:24, 9 сентября 2010 г. (UTC)[ ответить ]

У меня до сих пор не было возможности прочитать газету (всегда занят), но, похоже, она прошла некоторый разумный обзор. И, как я уже упоминал, я могу подтвердить факты (вплоть до небольшой возможной ошибки перечисления только машин древовидной нормальной формы). Я отменил свое предыдущее редактирование, чтобы сделать эти точные значения, пока кто-нибудь не возражает. Теперь я должен поздравить Лафита и Папазяна :) Ура, — sligocki ( обсуждение ) 05:03, 10 сентября 2010 г. (UTC) [ ответить ]

Спасибо еще раз. Как только у меня будет время, я намерен (i) добавить ссылку на L&P и предостережение и (ii) добавить ссылку на форум Бриггса по делу (5,2) - Yves — Предыдущий комментарий без подписи , добавленный 193.49 . 219.185 ( разговор ) 09:07, 10 сентября 2010 г. (UTC)[ ответить ]

Дополнения сделаны. Надеюсь, что формулировка об оговорке не является тяжелой или вводящей в заблуждение - Ив - Предыдущий неподписанный комментарий добавлен 77.197.251.244 ( обсуждение ) 13:48, 26 сентября 2010 г. (UTC)[ ответить ]

Еще одна мысль об эффективной вычислимости отдельных целых чисел, таких как $\Sigma (10)$

Утверждения типа "существует программа PRINT " выглядят для меня очень неубедительно, потому что они выведены из неочевидной аксиоматики. Но я предполагаю, что есть другой способ доказать, что целые числа, подобные эффективному вычислению. Если я ошибаюсь, поправьте. Мы должны выразить предложение « останавливается» (для любой данной машины Тьюринга ) на формальном языке арифметики. Я предполагаю, что умножение для этой цели нам не нужно, поэтому языка арифметики Пресбургера должно хватить. Но арифметика Пресбургера — полная и разрешимая теория. Последнее означает, что существует алгоритм, который решает, является ли предложение « останавливается» истинным или ложным. Таким образом, $<\Sigma (10)>$ $\Sigma (10)$ $M$ $M$ $M$ $\Sigma (n)$ $n$ .

Eugepros ( обсуждение ) 12:33, 21 октября 2010 г. (UTC) [ ответить ]

Вы доказали, что арифметика Пресбургера недостаточно мощна, чтобы описать проблему остановки :) — sligocki ( обсуждение ) 05:00, 27 октября 2010 г. ( UTC )

Хм, почему? Насколько мне известно, не существует теоремы о неразрешимости проблемы остановки для какой-либо отдельной машины Тьюринга. Алан Тьюринг доказал в 1936 году только то, что общего алгоритма решения проблемы остановки для всех возможных пар программа-ввод не существует.

Eugepros ( обсуждение ) 13:50, 28 октября 2010 г. (UTC) [ ответить ]

Ты прав. Это основа для поиска любых результатов Busy Beaver. Но вы сказали: «Таким образом, мы можем эффективно рассчитывать для любого заданного ». Это позволит вам решить общую проблему остановки. Ваше предположение состоит в том, что вы можете преобразовать любое предложение «M halts» в формальную арифметику Пресбургера. Но для этого не может быть общего алгоритма, иначе это нарушило бы проблему остановки.

\Sigma (n)

n

Ах, а может быть, вы имели в виду, что для каждого n вам потребуется новый и более оригинальный способ преобразования его в формальный язык? Это возможно, но помните, вам нужно проверить много машин! Ура, — sligocki ( обсуждение ) 22:13, 30 октября 2010 г. (UTC) [ ответить ]

Да, не может быть общего алгоритма для преобразования любого предложения «M halts» в формальную арифметику Пресбургера. Но, может быть, мы сможем доказать, что «М останавливается» преобразуется в формальный язык арифметики Пресбургера для любого М? Такое доказательство не означает построения общего метода преобразования.

Eugepros ( обсуждение ) 12:37, 11 ноября 2010 (UTC) [ ответить ]

Хм, эти обсуждения имеют тенденцию расходиться с полезностью. Но я могу доказать, что каждое утверждение «М останавливается» преобразуется в очень простой формальный язык для любого М? Этот простой язык — это язык с двумя предложениями: «истинно» и «ложно». Каждый M либо останавливается, либо нет, поэтому каждое утверждение «M останавливается» либо истинно, либо ложно :)

Я подозреваю, что это не то, на что вы надеялись. Я думаю, что основная проблема заключается в том, что вам нужно более общее решение, в котором формулировка формального языка напоминает исходный вопрос. Например, может быть интересно узнать, существует ли алгоритм для преобразования всех вопросов о машинах с 5 состояниями и 2 символами «останавливается ли M» в определенный формальный язык, если да, возможно, мы могли бы решить BB (5, 2) алгоритмически... — sligocki ( обсуждение ) 08:10, 13 ноября 2010 (UTC) [ ответить ]

Я понял тебя. Но проблема в том, что доказательства типа «утверждение можно преобразовать, потому что оно либо истинно, либо ложно» для меня ничего не значат. :( Я знаю, это классическая логика. Но я не могу доверять выводам, основанным только на законе исключенного третьего. Утверждение « останавливается», очевидно, может быть переведено примерно так: «Существует число такое, что = ‘стоп’, где состояния для каждого -го шага». Я не понимаю, почему последовательность не может быть определена рекурсивно, используя формальный язык, такой как арифметика Пресбургера... Или гипотеза о том, что функции рекурсивны для каждого , подразумевает, что , как функция обоих и , также является рекурсивной? $M$ $k$ $S_{M}(k)$ $S_{M}(i)$ $M$ $i$ $S_{M}(i)$ $f(i)=S_{M}(i)$ $M$ $S_{M}(i)$ $M$ $i$

Eugepros ( обсуждение ) 11:57, 13 ноября 2010 г. (UTC) [ ответить ]

Σ, сложность и недоказуемость

Я только что добавил этот раздел, но его формулировка несколько сложна. В настоящее время вывод ( «в контексте обычной математики нельзя доказать, что никакое конкретное число больше, чем Σ(10↑↑10)» ) несколько вводит в заблуждение, поскольку, по-видимому, подразумевает, что для n = Σ(10↑↑ 10), даже « n +1 > n » не является «доказуемым в обычной математике». Но предполагаемое значение состоит в том, что в данной формальной системе существует формула φ(< n >) (где < n > — унарная запись числа n ), которая выражает « n >Σ(10↑↑10)», и вывод состоит в том, что ни одно предложение вида φ(< n > ) доказуема в этой системе.
—res ( обсуждение ) 19:06, 16 ноября 2010 г. (UTC) [ ответить ]

Утверждение о вычислимости подмножеств Σ запутано и вводит в заблуждение.

В нем говорится следующее:

«Примечательным фактом является то, что теоретически любая конечная последовательность значений Σ, такая как Σ(0), Σ(1), Σ(2),..., Σ(n) для любого заданного n, является (тривиально) вычислима, хотя бесконечная последовательность Σ невычислима (см. примеры вычислимых функций)».

В моей самой снисходительной интерпретации этого предложения оно говорит что-то тривиально верное, но, возможно, вводящее в заблуждение и не слишком связанное с понятием вычислимости фактической последовательности Σ. Это все равно, что сказать, что «каждая цифра в десятичной записи невычислимого числа сама по себе является вычислимым числом, потому что «цифра» — это значение от 0 до 9 и, следовательно, натуральное число, а натуральные числа вычислимы». Это правда, но это похоже на этот случайный факт, который может легко направить кого-то в неправильном направлении. Это вводит в заблуждение, потому что очень похоже на то, что можно выяснить, даже помимо ограничений «практичности», каково значение Σ(n) для любого n. Это неверно.

Используя нашу метафору десятичного расширения/цифры, это все равно, что сказать, что можно выяснить, КАКАЯ ПОЗИЦИЯ в расширении содержит какие из этих вычислимых сущностей мы назвали «цифрами», и это просто неверно. Если бы это было правдой, число вовсе не было бы невычислимым. Кроме того, тот факт, что сама концепция «цифры», являющаяся значением от 0 до 9, является вычислимым числом, в основном не имеет отношения к тому, что здесь обсуждается. А в случае с Σ это еще более неуместно; если каждое значение Σ(n) является конечным натуральным числом, то мы уже знаем, что значения Σ(n) по определению принадлежат множеству всех вычислимых чисел. Мы уже говорили об этом, когда определяли Σ как отображение функции из N -> N. Поэтому нет необходимости утверждать, что, поскольку область значений Σ является множеством натуральных чисел,

Но затем следующее предложение после того, что написано выше, выглядит так, как будто оно говорит что-то просто ложное (первое предложение снова включено для справки:

«Примечательным фактом является то, что теоретически любая конечная последовательность значений Σ, такая как Σ(0), Σ(1), Σ(2),..., Σ(n) для любого заданного n, является (тривиально) вычислима, даже если бесконечная последовательность Σ невычислима (см. Примеры вычислимых функций). Кроме того, для достаточно малых n также практично вычислить Σ (n)».

Теперь кажется, что проблема с вычислением Σ(n) заключается в том, что по мере увеличения n задействованные вычисления становятся настолько сложными, что на самом деле невозможно вычислить Σ(100) или что-то в этом роде. Но это не совсем так. Неправда, что мы можем вычислить, что такое Σ(n) для любого выбора n - вообще-, независимо от какого-либо понятия «практичности», на чисто теоретическом уровне, даже если бы у нас было бесконечное количество времени. Мы вообще можем его вычислить только для некоторого n, и точка.

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

71.230.120.206 ( разговор ) 09:09, 19 января 2012 (UTC) [ ответить ]

Я согласен, слишком много внимания было уделено тому, как целые числа можно вычислить. Я удалил еще один абзац, в котором это подчеркивалось. Как это выглядит сейчас? Ура, — sligocki ( обсуждение ) 23:58, 12 февраля 2012 г. (UTC) [ ответить ]

Откуда мы знаем значение BB(6)

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

Bubby33 ( обсуждение ) 21:06, 18 апреля 2015 (UTC) [ ответить ]

Дальнейшее обсуждение

Безымянные комментарии ниже были взяты из верхней части страницы пользователем: Negrulio 28-12-2015 -- Negrulio ( обсуждение ) 16:03, 28 декабря 2015 г. (UTC) Было бы неплохо более конкретно описать, что такое термин " n-государственный автомат" означает. Будь то машина Тьюринга или произвольная машина с n состояниями. марек 19:38, 23 февраля 2006 (UTC) [ ответ ]

Существует UTM (2,22), поэтому BB(22) даст ответ на проблему остановки: нижние оценки для универсальных машин Тьюринга . Таким образом, BB(n) нельзя рассчитать для n>=22, что делает раздел приложений бесполезным. — Предыдущий неподписанный комментарий добавлен Rantalaiho74 ( обсуждение • вклад ) 16 октября 2010 г.

Нет, есть UTM с 22 состояниями, но он требует указания ввода на ленте . Busy Beaver запускается с пустой лентой. Без ввода. На самом деле, если вы посмотрите на определение UTM с 22 состояниями и попробуете запустить его на пустой ленте, поведение, вероятно, будет довольно простым, потому что пустая лента, вероятно, не кодирует очень интересные входные данные TM. Пожалуйста, прекратите редактировать эту страницу, если вы не можете указать надежный источник. Ура, — sligocki ( обсуждение ) 06:36, 17 октября 2010 г. (UTC) [ ответить ]

Доказательство факта «S(n) растет быстрее любой вычислимой функции F(n)» следует из свойств композиции Create_n ₀ |Double|EvalF|Clear, где n ₀ — размер в состояниях машины Double|EvalF| Чистый. Я думаю, что текущее доказательство в начале статьи очень сложное (использует log ₂ (n) и свойства UTM) и должно быть изменено. Скелет 08:26, 27 октября 2004 г. (UTC)

Точно так же доказательство «Σ(n) растет быстрее любой вычислимой функции F(n)» следует из свойств композиции Create_n ₀ |Double|EvalF|Increment. Скелет 08:31, 27 октября 2004 г. (UTC)

Мы можем решить проблему остановки для ТМ любого фиксированного размера. Каков здесь соответствующий принцип с точки зрения реальных языков программирования? Можем ли мы вычислить S(n) вплоть до фиксированного n, запустив определенную программу (возможно, большой счетчик ТМ?) большего размера? Знаем ли мы, насколько больше n должна быть машина для вычисления S(n)? Лунквилл 29 июня 2005 г. 07:28 (UTC)

Неа. Проще говоря, если бы мы знали, насколько большая машина Тьюринга нам нужна для вычисления S(n), то мы смогли бы вычислить S(n). -- Ihope127 16:59, 2 апреля 2006 г. (UTC) [ ответить ]

Удаление «ненадежных» источников

Это редактирование удалило из статьи «ненадежный» источник: https://en.wikipedia.org/w/index.php?title=Busy_beaver&diff=756743646 .

Я не думаю, что это оправдано. Я не говорю, что Викия — надежный источник. Но я хочу сказать, что отвергать это на основании надежности источника — это генетическая ошибка, потому что достоверность дедуктивного аргумента не зависит от надежности источника аргумента. Другими словами, дедуктивное доказательство является доказательством, независимо от того, откуда оно взято или опубликовано. Однако в то же время я понимаю, что Викия не является WP:RS и, соответственно, не должна быть включена в Википедию. Но поскольку удаление этого источника снижает качество статьи, добавляя непроцитированное нетривиальное утверждение, и удаляет место, где люди могут узнать больше о том, о чем говорится, я думаю, что это требует WP:IAR. IWillBuildTheRoads ( обсуждение ) 20:07,[ ответить ]

Максимальная длина ленты

Как называется функция, которая подсчитывает максимальный сдвиг вправо, R(n)? Как она растет пропорционально? 91.66.15.241 ( разговор ) 21:08, 13 марта 2017 (UTC) [ ответ ]

Меньше ходов для занятого бобра с 3 состояниями

Очень хорошая статья. BB с 3 состояниями в примерах раздела занимает 14 шагов. Следующая машина выполняет 12 шагов и всегда записывает 1.

	А	Б	С
0	1RC	1РА	1 фунт
1	1РА	1LC	1 ч

Стоит ли это упоминать? Поступай с моим замечанием, как хочешь.

Jacob.Koot ( обсуждение ) 18:38, 11 апреля 2017 г. (UTC) [ ответить ]

Ниже представлена таблица ходов. ((x...) (yz...)) представляет собой ленту (x...yz...) с головкой ленты в точке y.

.......................................... исходная лента: (() (0 )) 
ход 1, состояние A -> C, символ 0 -> 1, ход: R, новая лента: ((1) (0)) 
ход 2, состояние C -> B, символ 0 -> 1, ход: L , новая лента: (() (1 1)) 
ход 3, состояние B -> C, символ 1 -> 1, ход: L, новая лента: (() (0 1 1)) 
ход 4, состояние C -> B, символ 0 -> 1, ход: L, новая лента: (() (0 1 1 1)) 
ход 5, состояние B -> A, символ 0 -> 1, ход: R, новая лента: ((1 ) (1 1 1)) 
ход 6, состояние A -> A, символ 1 -> 1, ход: R, новая лента: ((1 1) (1 1)) 
ход 7, состояние A -> A, символ 1 -> 1, ход: R, новая лента: ((1 1 1) (1)) 
ход 8, состояние A -> A, символ 1 -> 1, ход: R, новая лента: ((1 1 1 1) (0)) 
ход 9, состояние A -> C, символ 0 -> 1, ход: R, новая лента:((1 1 1 1 1) (0))
ход 10, состояние C -> B, символ 0 -> 1, ход: L, новая лента: ((1 1 1 1) (1 1)) 
ход 11, состояние B -> C, символ 1 -> 1, ход :Л, новая лента: ((1 1 1) (1 1 1))
ход 12, состояние C -> H, символ 1 -> 1, ход: , новая лента: ((1 1 1) (1 1 1))

(Я улучшил макет -- H.Marxen ( обсуждение ) 18:58, 3 мая 2017 г. (UTC)) [ ответить ]

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

Достижение того же (большого) количества меток ленты с меньшим количеством шагов - логически - должно быть интересно. Следовательно, да, эксперт может счесть это достойным изучения. В противном случае... такое исследование еще не проводилось, насколько я знаю, поэтому мы не можем ссылаться на такую работу. -- Х.Марксен ( разговор ) 18:58, 3 мая 2017 г. (UTC) [ ответить ]

Спасибо за улучшение макета. Я пробовал это сам, но не знал, как это сделать. Я согласен, что неопубликованные работы не должны быть включены. Тем не менее, мой пример сам по себе является доказательством и может быть интерпретирован как публикация через Википедию. Кажется, Википедия не принимает публикации, сделанные через Википедию? Jacob.Koot ( обсуждение ) 16:20, 12 мая 2017 г. (UTC) [ ответить ]

https://en.wikipedia.org/wiki/Turing_machine_examples#3-state_Busy_Beaver показывает занятого бобра, который делает 12 шагов и всегда пишет 1. Это не совсем то же самое, что и мой, но все работает одинаково. Ссылка: «взято из Peterson (1988), стр. 198, рис. 7.15». Я думаю, мы можем включить пример Петерсона. Jacob.Koot ( обсуждение ) 17:24, 21 июня 2017 (UTC) [ ответить ]

Требование точного количества шагов

В статье упоминается, что «указание точного количества шагов, необходимых для достижения состояния остановки», необходимо, потому что без него «проблема проверки каждой потенциальной записи неразрешима», ссылаясь на проблему остановки. Однако не заключается ли проблема остановки в том, чтобы определить остановку произвольной машины при ПРОИЗВОЛЬНОМ ВВОДЕ, и последнее требование является ключом к доказательству?

Если существует обобщение теоремы об остановке, запрещающее создание алгоритма, который для одного конкретного входа предсказывал бы, остановится ли произвольная машина, такое обобщение обязательно должно быть упомянуто на соответствующей странице «Проблема остановки», а текущая статья должна содержать ссылку именно к этому обобщению. В противном случае в текущей статье необходимо отразить, что «точное количество шагов» требуется только потому, что мы не знаем алгоритма для проверки и даже не знаем, может ли такой алгоритм существовать. — Предыдущий неподписанный комментарий добавлен 104.53.222.39 ( обсуждение ) 01:37, 2 июня 2020 г. (UTC) [ ответ ]

Код C (4 состояния, 2 символа, занятый бобер)

#include <stdio.h> #define STATE_N (4) #define SYMBOL_N (2) #define TAPE_N (16)int move_tb [ SYMBOL_N ] [ STATE_N ] =   { { + 1 , -1 , + 1 , + 1 },      { -1 , -1 , -1 , + 1 }      };int state_tb [ SYMBOL_N ] [ STATE_N ] =   { { 1 , 0 , -1 , 3 },      { 1 , 2 , 3 , 0 }      };int write_tb [ SYMBOL_N ] [ STATE_N ] =   { { 1 , 1 , 1 , 1 },      { 1 , 0 , 1 , 0 }      };целая лента [ TAPE_N ]; int основной ( недействительный ) { заголовок int = 11 ;    целое состояние = 0 ;    интервал шаг = 0 ;    пока ( 1 )  { printf ( "%4d" , шаг );  для ( int я = 0 ; я < TAPE_N ; ++ я )         printf ( "%c%c" , i == заголовок ? "hABCD" [ 1 + состояние ] : ' ' , "_1" [ лента [ i ]]);           printf ( " \n " ); если ( состояние == -1 )    перерыв ; int read = лента [ заголовок ];    лента [ заголовок ] = write_tb [ чтение ] [ состояние ];   заголовок += move_tb [ чтение ] [ состояние ];   состояние = состояние_tb [ чтение ] [ состояние ];   если ( заголовок == -1 || заголовок == TAPE_N )        { printf ( "ОШИБКА: закончилась лента (заголовок=%d) \n " , заголовок );  перерыв ; } шаг ++ ; } вернуть 0 ; }

-- MkMkMod ( обсуждение ) 07:53, 17 июля 2020 г. (UTC) [ ответить ]

Функция максимальных сдвигов S(n)

Я подозреваю, что раньше S(n) было невычислимым, но в 2013 году, когда была определена теория множеств первого порядка (то есть Rayo(n)), S(n) стало вычислимым.

В этом видео Карбрикссити рассказал причину, по которой число Райо невычислимо. Причина была такова: «Никто никогда не определит число с помощью гугол - символов». Проблема, кажется, заключается в количестве символов. В наблюдаемой вселенной недостаточно места для символов гугола. Эмк показал, что Rayo(7901) > S(2 ⁶⁵⁵³⁶ −1), где S(n) — функция максимальных сдвигов. Всего 7901 символ (которые можно легко записать) и уже 2 ⁶⁵⁵³⁶ −1 состояний. Вот почему я подозреваю, что S(n) стало вычислимым после определения Rayo(n).

Та же проблема с символами возникает при доказательстве TREE(3) в строго конечной математике. Для этого потребуется 2 ^ ^ 1000 символов. Никто никогда не сможет закончить такое доказательство, потому что в наблюдаемой вселенной недостаточно места для такого количества символов. Эта причина изначально была написана в этом видео . Итак, пользователь: 84.154.72.51 написал эту идею для точного значения (или, по крайней мере, действительно хорошей оценки) TREE(3). Идея заключается в теории множеств первого порядка для TREE(3) в символах. Теория множеств первого порядка — это Rayo(n), где n — количество символов. Здесь показано, что Σ(2000) > число грузчиков ≫ ДЕРЕВО(3). Здесь показано, что S(n) ≥ Σ(n) для всех n. И конечно 2⁶⁵⁵³⁶ −1 ≫ 2000. Таким образом, теория множеств первого порядка уменьшит «необходимое количество символов для TREE(3)» с 2^^1000 до менее 7901. — Предыдущий беззнаковый комментарий добавлен 80.142.18.145 ( обсуждение ) 20:41, 25 октября 2020 г. (UTC) [ ответить ]

Σ(17) > число Грэма и другие сравнения

Показано, что Σ(17) > числа Грэма .

Какой тип Σ(n) будет примерно таким же большим, как TREE(3) , SSCG(3) , SCG(13) , число грузчика, число Райо и число рыбы 7 ?

Ошибка в примерах

Примеры и визуализации бобра с 4 состояниями и 2 символами не совпадают. Примеры имеют 1RH для символа состояния C 0, а визуализации имеют 0RH для символа состояния C 0. Пример утверждает, что 4-состоятельный, 2-символьный занятой бобёр производит 13 единиц за 107 шагов, и он говорит «см. изображение». Визуализации производят только 12 единиц, когда останавливаются. Это следует исправить. — Предыдущий неподписанный комментарий добавлен 50.206.176.154 ( обсуждение ) 04:17, 3 февраля 2021 г. (UTC) [ ответ ]

@ OrdinaryArtery : также может быть шанс векторизовать эту диаграмму! ~~ Ebe 123 ~~ → отчет 17:11, 21 апреля 2021 г. (UTC) [ ответить ]