Как такое определение https://i.stack.imgur.com/Q2Jbi.png согласуется с определением из Википедии (There is an algorithm that enumerates the members of S. That means that its output is simply a list of the members of S: s1, s2, s3, ... . If necessary, this algorithm may run forever.)?

Определение на скриншоте почему-то требует, чтобы на ленте не появлялись бесконечные последовательности 0 и 1. Имеется ли там в виду, что машина печатает двоичные записи натуральных чисел и разделяет их бланками?

И вместо машины Тюринга можно просто взять регистровую машину? Она тоже на пустом входе бы выдавала последовательности из 0 и 1, разделенные бланком.

задан 21 Май 6:30

Специфика машины тут не важна, и формат записи чисел также не важен. Оговорка о том, что на ленте написано лишь конечное число непустых символов (отличны от #), связана с тем, что в противном случае на ленте представлен бесконечный объём информации. Такого положения дел надо избегать, так как машина с уже имеющейся бесконечной "шпаргалкой" в принципе способна отвечать на любые вопросы, и при этом смысл понятия вычислимости теряется.

(21 Май 13:38) falcao

А почему бесконечные последовательности вида 101#101011###101111##1011... не представляют собой бесконечный объем информации, тогда как последовательности без решеток представляют?

(22 Май 1:36) logic
10|600 символов нужно символов осталось
1

Комментарии только что работали, и снова "сдохли". Не понимаю, КТО и ЧТО делает с этим сайтом?

Отвечаю на предыдущий комментарий. Символ # считается пустым. Когда машина работает, то лента считается конечной. Это нужно для того, чтобы избегать ситуаций типа "волшебной шпаргалки".

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

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

ссылка

отвечен 22 Май 1:47

Но в его соглашении же не говорится о том, что должно появляться конечное число единиц и нулей. А если так, то я всё равно не вижу разницы между тем, будет ли у нас бесконечное число нулей и единиц или бесконечное число нулей, единиц и бланков. Во втором случае все равно может быть бесконечное число нулей и единиц. Но тем не менее почему-то второй случай допускается, а первый нет.

(22 Май 2:09) logic

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

(22 Май 2:23) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×408

задан
21 Май 6:30

показан
38 раз

обновлен
22 Май 2:23

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru