Хорошо, т.е. Вы исходите из того, что мы дикарю не произнесем ни одного высказывания вида

, где

-- cчетное множество,

-- предикат.
Нет, я исхожу из того, что мы не потребуем от «дикаря» самостоятельных выводов, требующих мат. индукции.
Но, к сожалению, Вы уже произнесли ему такое высказывание:
Слово состоит из букв.
А обобщённые утверждения (типа этого), которые закладываются в качестве аксиомы, допустимы. Мы ведь не требуем от «дикаря», чтобы он их доказывал по индукции.
Кстати, в арифметике Робинсона есть такая аксиома:

,
которая является утверждением с квантором всеобщности. Однако почему-то никто не считает, что эта аксиома имеет отношение к индукции.
А с чего Вы взяли, что результатом работы данного НАМ всегда будет либо ``да'', либо ``нет'' для каждого переданного ему слова, а может он для какого-то слова ответит что-то третье? Уж не посмели ли Вы неосознанно использовать математическую индукцию (ай-я-яй)?
Ни с чего я это не взял. Мало того, я совершенно точно знаю, что для любой физической реализации алгоритма можно подобрать такое слово, которое он не сможет распознать. Потому что не хватит вычислительных ресурсов. Просто я считаю что такие слова заведомо выходят за пределы сферы наших интересов.
-- Вс апр 15, 2012 22:56:16 --При формализации понятия строки, к которому мы привыкли, потребуется довольно много арифметики. И боюсь, что для доказательства свойств строк где-нибудь да вылезет индукция.
Тут весь вопрос в том, что считать формализацией понятия строки, т.е. какую степень формализации в каких базовых понятиях следует считать достаточной. Например, я знаю, что в компьютерной технике строковый тип переменных повсеместно используется. И я не вижу здесь особой необходимости доказывать какие-то свойства строк, используя индукцию: железяку-то как-то собрали и запрограммировали, теперь она более или менее работает. Причём тут доказательство общих свойств? А эта железяка - и есть «формализация», которая на не слишком длинных строках будет нормально работать.