Нормальные алгорифмы Маркова

[Solarise]

Последняя надежда на вас, уважаемые форумчане=)
а проблема моя заключается в том как с помощью НАМ перевести любое произвольно выбранное натуральное число в натуральное конструктивное число...
на всякий случай напомню, что натуральное конструктивное число представляет собой последовательность единиц, которых ровно столько, сколько их содержится в числе:
1 - 010
2 - 0110
3 - 01110
и тд
Помогите, пожалуйста=)

[e7e5]

Solarise писал(а):

с помощью НАМ перевести любое произвольно выбранное натуральное число в натуральное конструктивное число...
на всякий случай напомню, что натуральное конструктивное число представляет собой последовательность единиц, которых ровно столько, сколько их содержится в числе:
1 - 010
2 - 0110
3 - 01110
и тд
Помогите, пожалуйста=)

А проще можете без "НАМ"? В чем проблема?

[Solarise]

перевести произвольно заданное натуральное число, заданное в десятичной системе счисления, в конструктивное натуральное число в теле нормального алгоритма Маркова ( другими словами: с помощью натурального алгорифма Маркова)

Вообще задание представляет собой вот что:
Построить нормальный алгорифм, который вычисляет остаток от деления заданного натурального числа, заданного в десятичной системе счисления, на 5.

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

[Brukvalub]

Solarise в сообщении #150759 писал(а):

Построить нормальный алгорифм, который вычисляет остаток от деления заданного натурального числа, заданного в десятичной системе счисления, на 5.

Этот остаток совпадает с остатком от деления на 5 последней цифры числа. Если последняя цифра равна 0, 1, 2, 3, 4, то остаток ей и равен, если же последняя цифра равна 5, 6, 7, 8, 9, то остаток соответственно равен 0, 1, 2, 3, 4. То есть алгоритм отыскания остатка примитивен. Это трудно реализовать в форме НАМ?

[e7e5]

Solarise писал(а):

нормальный алгорифм

А что такое "алгорифм"? Да еще нормальный?

[Solarise]

Brukvalub писал(а):

Этот остаток совпадает с остатком от деления на 5 последней цифры числа. Если последняя цифра равна 0, 1, 2, 3, 4, то остаток ей и равен, если же последняя цифра равна 5, 6, 7, 8, 9, то остаток соответственно равен 0, 1, 2, 3, 4. То есть алгоритм отыскания остатка примитивен. Это трудно реализовать в форме НАМ?

ой, какой же я клинический дурак! Х_х
спасли, спасибо)

Вот правду говорят, все гениальное -просто=) а я начала заменять пять первых единичек с нулем на ноль, а остаток, если он равен 0, 1, 2, 3 или 4 палочкам выводить как ответ)
ужас)

Добавлено спустя 3 минуты 36 секунд:

e7e5 писал(а):

Solarise писал(а):

нормальный алгорифм

А что такое "алгорифм"? Да еще нормальный?

http://ru.wikipedia.org/wiki/%D0%9D%D0% ... 1%84%D0%BC

пожалуйста

[Brukvalub]

e7e5 в сообщении #150762 писал(а):

А что такое "алгорифм"? Да еще нормальный?

Это стандартный термин из теории алгорифмов. Для записи алгорифмов нужен единый, понятный всем способ ("язык"). На самом деле таких канонических способов - несколько. Один из них - запись алгорифма как программы из команд для машины Тьюринга. Др. способ - в виде нормального алгорифма Маркова. Есть и др. способы. См., например, http://leded.newmail.ru/docs/doc1.htm

[e7e5]

Solarise писал(а):

e7e5 писал(а):

Solarise писал(а):

нормальный алгорифм

А что такое "алгорифм"? Да еще нормальный?

http://ru.wikipedia.org/wiki/%D0%9D%D0% ... 1%84%D0%BC

пожалуйста

Можно ли пояснить, почему называют нормальным алгорифмом Маркова? Понятно, что "Понятие нормального алгорифма введено А. А. Марковым", при чем здесь слово "нормальный"?

[Brukvalub]

e7e5 в сообщении #150768 писал(а):

Можно ли пояснить, почему называют нормальным алгорифмом Маркова?

Как это понимаю я : слово "нормальный" является в этом названии неким эквивалентом слов "универсальный", "очень удобный", "всеобъемлющий", и т.п.

[e7e5]

Brukvalub писал(а):

Как это понимаю я : слово "нормальный" является в этом названии неким эквивалентом слов "универсальный", "очень удобный", "всеобъемлющий", и т.п.

Ага, вроде как "понятный" и "естественный" алгорифм
Ясно.

[Профессор Снэйп]

Изложите свои идеи, покажите попытки решения. Решить для Вас эту задачу мне труда не составит, однако такие вещи запрещены правилами форума.

Почему у Маркова алгоритмы (алгорифмы) называются "нормальными", я не знаю. Вероятно, это вопрос к самому Маркову. Книжка Маркова и Нагорного у меня на полке стоит, но выискивать в ней ответ на этот вопрос мне что-то лень

[Someone]

e7e5 в сообщении #150768 писал(а):

при чем здесь слово "нормальный"?

А.А.Марков назвал нормальными алгорифмами детерминированные правила преобразований слов, которые можно записать по определённым правилам. И сформулировал "принцип нормализации": каждый алгорифм (в интуитивном смысле) в заданном алфавите эквивалентен некоторому нормальному алгорифму (может быть, в расширенном алфавите). Слово "нормальный", видимо, введено для того, чтобы отличать определённые Марковым алгорифмы от алгорифмов в интуитивном смысле. Почему Марков и его последователи говорят "алгорифм", в то время как чаще встречается написание "алгоритм" - не знаю.

[Solarise]

Someone писал(а):

Почему Марков и его последователи говорят "алгорифм", в то время как чаще встречается написание "алгоритм" - не знаю.

слово "алгоритм" до революции писалось через фиту, то есть "алгорифм", Марков, видимо, придерживался старого варианта.

Добавлено спустя 33 минуты 4 секунды:

- Пусть E, M и N принадлежат алфавиту V, алфавит V - состоит из чисел от 0 до 9
- A и B не принадлежат алфавиту V:

A E -> E A
B M A -> [.] M , M={0, 1, 2, 3, 4}
B 5 A -> [.] 0
B 6 A -> [.] 1
B 7 A -> [.] 2
B 8 A -> [.] 3
B 9 A -> [.] 4
B E-> B
-> A
-> B

Верно?

[Профессор Снэйп]

Solarise писал(а):

Пусть E, M и N принадлежат алфавиту V, алфавит V - состоит из чисел от 0 до 9 - A и B не принадлежат алфавиту V:

A E -> E A
B M A -> [.] M , M={0, 1, 2, 3, 4}
B 5 A -> [.] 0
B 6 A -> [.] 1
B 7 A -> [.] 2
B 8 A -> [.] 3
B 9 A -> [.] 4
B E-> B
-> A
-> B

Верно?

Нет, не верно. $A$ возникнет в начале десятичной записи, "пройдёт" в конец, потом возникнет новая $A$ и т. д. До $B$ дело так и не дойдёт.

Hint: можно обойтись только символами алфавита $V$

[Solarise]

ммм, если использовать только дополнительную букву А?)
то есть при появлении записи A E A делать преобразования? То есть так?)


A M A -> [.] M , M={0, 1, 2, 3, 4}
A 5 A -> [.] 0
A 6 A -> [.] 1
A 7 A -> [.] 2
A 8 A -> [.] 3
A 9 A -> [.] 4
A E -> E A
-> A

Думать над оптимизацией поздно Х_х 6 часов до сдачи работы)