| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Центр помощи > [Теория алгоритмов]Машина Шёнфилда |
| Автор: breaking 11.1.2009, 14:02 |
| Помогите составить Машину Шёнфилда для следующей функции: f(x,y) = |x-y| |
| Автор: andrew_121 11.1.2009, 14:45 |
| breaking, Гугл тебе в руки. |
| Автор: breaking 13.1.2009, 22:42 |
| Понимаешь тут особо и гуглить ничего не надо. Основную идею я понимаю, просто никак не могу понять один момент, сейчас объясню более конкретно. Программирование машин Шёнфилда чем-то напоминает программирование на языке Assembler: Машина Шёнфилда имеет бесконечное число регистров, пронумерованных натуральными числами, начиная с 0. Каждый из этих регистров может содержать любое натуральное число. Для любой программы нам будет необходимо лишь конечное число регистров, которое нетрудно заранее определить по программе. Кроме этого у машины есть специальная память для программы, а также счётчик команд, всегда содержащий некоторое натуральное число. Программа для машины Шёнфилда состоит из конечного списка команд, последовательно пронумерованных натуральными числами начиная с 0. Перед запуском в машину вводится программа, в регистры заносятся начальные данные, а в счётчик команд заносится значение 0. После этого шаг за шагом осуществляется работа машины. Шаг машины состоит в исполнении команды, номер которой указан в счётчике команд. Если такого номера команды нет, то машина останавливается. Существеует два типа команд:
Вот несколько макросов: Макрос GOTO n 0: INC 0 1: DEC 0, n Макрос ZERO I. Этот макрос, который обнуляет содержимое I-го регистра. Состоит такой макрос всего из одной команды - DEC I, 0. Макрос [i] -> [j], (k), где i, j != k. Этот макрос копирует содержимое i-го регистра в j-й регистр, используя k-й регистр в качестве вспомогательного. Содержимое i-го регистра при i != j не изменяется. Программа для макроса [i] -> [j], (k) при i != j выглядит так: 0: ZERO j 1: ZERO k обнулили j-й и k-й регистры 2: GOTO 5 переход на 5-ю команду 3: INC j 4: INC k 5: DEC i, 3 если в i-м регистре не 0, увеличим i-й и k-й регистры 6: GOTO 8 7: INC i 8: DEC k, 7 копирование из k-го регистра в i-й Если i = j, то можно взять любую программу, которая ничего не меняет, например 0: GOTO 1 Макрос F([i1], ..., [ik] -> [j] вычисляет значение функции F, вычислимой по Шёнфилду с помощью программы P, от содержимого регистров [i1], ..., [ik], записывает это значение в j-й регистр и при этом не изменяет значения остальных регистров. Следующая машина определяет функцию сложения sum(x, y) = x + y 0: [2] -> [0] 1: GOTO 3 2: INC 0 3: DEC 1, 2 Для функции умножения mult(x, y) = x * y 0: ZERO 0 1: GOTO 3 2: sum([0], [2]) -> [0] 3: DEC 1, 2 А теперь возвратимся к моей задаче - f(x,y) = |x-y|. Как можно прочитать выше регистры могут содержать только натуральные числа, т.е. отрицательных там быть не может. В таком случае как же реализовать нужную мне функцию и, к примеру, функцию вычитания - sub(x,y) = x - y??? Вот мой пример реализации sub(x,y) = x - y 0: [1] -> [0] 1: INC 0 2: DEC 0, 4 3: GOTO 5 4: DEC 2, 2 Но он по ходу неверный... |
| Автор: solverr 15.1.2009, 12:40 |
| 0. DEC 1, 2 1. GOTO 4 2. DEC 2, 0 3. INC 1 4. ZERO 0 5. DEC 1, 7 6. GOTO 9 7. INC 0 8. GOTO 5 9. DEC 2, 11 10. GOTO 13 11. INC 0 12. GOTO 9 13. HAPPY END |
| Автор: Aplles 7.5.2009, 09:53 |
| Преветcтвую всех. Что-то никак не вникну в смысл машин Шёнфилда, и потому помогите плиз составить машину Шёнфилда для функции: f(x,y) = x^y и f(x,y) =|sqrt(x)| |