Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 19
Если уж сортировать «тьюринговые трясины» по важности, то надо начинать с основных — математических, на которых всё строилось, а потом уж добавлять в список новомодную эзотерику вроде Brainfuck.
В таком случае это будут:
Во «второй эшелон» попадут-таки машина Поста, блок-схема Поста, комбинаторное исчисление Шейнфинкеля, и, если уж добавлять современные «эзотерические языки программирования» в список — Brainfuck со товарищи.
И, будьте добры, не называйте «тьюринговы трясины» эзотерическими системами. Это сейчас BF и ему подобные — эзотерические языки программирования на фоне современных высокоуровневых, а машина Тьюринга и эквивалентные ей создавались не чувство юмора программиста потешить, а математически понятие вычислимости и алгоритмистики исследовать, это совершенно разные вещи.
Как-то так.
В таком случае это будут:
- машина Тьюринга (машину Поста знаю, конечно, но популярности она не приобрела);
- лямбда-исчисление Черча;
- рекурсивные функции Черча;
- нормальные алгоритмы Маркова.
Во «второй эшелон» попадут-таки машина Поста, блок-схема Поста, комбинаторное исчисление Шейнфинкеля, и, если уж добавлять современные «эзотерические языки программирования» в список — Brainfuck со товарищи.
И, будьте добры, не называйте «тьюринговы трясины» эзотерическими системами. Это сейчас BF и ему подобные — эзотерические языки программирования на фоне современных высокоуровневых, а машина Тьюринга и эквивалентные ей создавались не чувство юмора программиста потешить, а математически понятие вычислимости и алгоритмистики исследовать, это совершенно разные вещи.
Как-то так.
Я бы поставил комбинаторное исчисление если в самый верх, то точно в первый список. Комбинаторов S и K достаточно для моделирования лямбда-исчисления. Кстати, эзотерический язык программирования Unlambda, который как раз построен на этих комбинаторах, гораздо элегантнее BrainFuck и действительно знакомит пользователя с комбинаторами. Комбинаторное исчисление лежит в основе APL и ряд более современных языков очень высокого уровня. И не уверен, что сегодня стоит разделять лямбда-исчисление и рекурсивные функции. Лямбда-исчисление было придумано Черчем как простая формализация рекурсивных функций.
Да, про лямбда-исчисление забыл.
«Эзотерическими системами» я назвал только алгоритмы Маркова и Brainfuck ввиду их _современного_ применения. В Тьюринге вообще ничего особо веселого нет.
«Эзотерическими системами» я назвал только алгоритмы Маркова и Brainfuck ввиду их _современного_ применения. В Тьюринге вообще ничего особо веселого нет.
На 9 состояний короче:
0:!
1: 0 // main loop
2: →
3:? 2: 4
4: →
5: 0 // loop by second multiple
6: →
7:? 6: 8
8: →
9:? 8: 10
10: 1
11: ←
12:? 11: 13
13: ←
14:? 13: 15
15: 1
16: →
17:? 5: 18
18: ←
19:? 18: 20
20: ←
21:? 22: 25
22: ←
23:? 22: 24
24: → 1
25: →
26: → // erase second multiple
27:? 28: 0
28: 0 26
Честно говоря, машина Тьюринга мне кажется логичнее (если используются только те символы, которые есть в условии задачи — т.е. для унарного умножения только 0 и 1). Все-таки, в отличие от машины Поста в ней не 5-7 команд, а одна, хотя и длинная. И там нет разночтений в синтаксисе (типа «возможен ли переход не на следующую команду», «есть ли условный переход с двумя метками, или два отдельных перехода if(0) и if(1)») — эти мелочи могут сильно влиять на то, какой алгоритм кодируется короче.
0:!
1: 0 // main loop
2: →
3:? 2: 4
4: →
5: 0 // loop by second multiple
6: →
7:? 6: 8
8: →
9:? 8: 10
10: 1
11: ←
12:? 11: 13
13: ←
14:? 13: 15
15: 1
16: →
17:? 5: 18
18: ←
19:? 18: 20
20: ←
21:? 22: 25
22: ←
23:? 22: 24
24: → 1
25: →
26: → // erase second multiple
27:? 28: 0
28: 0 26
Честно говоря, машина Тьюринга мне кажется логичнее (если используются только те символы, которые есть в условии задачи — т.е. для унарного умножения только 0 и 1). Все-таки, в отличие от машины Поста в ней не 5-7 команд, а одна, хотя и длинная. И там нет разночтений в синтаксисе (типа «возможен ли переход не на следующую команду», «есть ли условный переход с двумя метками, или два отдельных перехода if(0) и if(1)») — эти мелочи могут сильно влиять на то, какой алгоритм кодируется короче.
Кстати, третью задачу я не понял. Что такое n? Константа, от которой будет зависеть длина программы? Или это число тоже будет записано на ленте?
Не очень удачно сформулировано. Про ленту ничего не известно, про кол-во отметок тоже. Каретка неизвестно где. Естественно, работа должна идти вечно.
Жестоко. С первой попытки получилось 60 состояний, примерно 15 из них — поиск первой отметки, и примерно столько же — борьба с разнообразными начальными условиями :) Основной цикл — 26 состояний.
1. ? 2, 3 2. 1 .вместо поиска первой метки 3. → .создание опорных меток 4. ? 5, 3 5. → 6. ? 7, 3 7. 1 8. ← 9. ? 10, 8 10. ← 11. ? 12, 8 12. 1 20 .. 13. ← .цикл слева 14. ? 15, 16 15. 1 20 16. → 17. ? 16, 18 18. ← 19. 1 20. → 21. ? 20, 22 22. → 23. ? 24, 22 24. → 25. ? 24, 26 26. 0 27. → справа 28. ? 29, 30 29. 1 34 30. ← 31. ? 30, 32 32. → 33. 1 34. ← 35. ? 34, 36 36. ← 37. ? 38, 36 38. ← 39. ? 38, 40 40. 0 13 ..
с трудом представляю, как за 15 строк можно найти первую отметку.
В программе до конца не разобрался, но уже первые три строчки вызывают подозрение: при переходе к состоянию 3 у нас потерялась информация — поставили мы новую единицу, или нет.
Кстати, в команде "? a, b" в каком порядке идут состояния? Вики предлагает сначала состояние для заполненной ячейки, потом для пустой.
Проверил свою программу — у меня ошибка. Неправильно отрабатывается найденная первая метка. Так что размер был бы еще больше (на 8 состояний). Если бы можно было оставить блок не из n, а из n+1 единицы, все было бы гораздо проще.
Интересно, считать ли корректым решением то, в котором блок из n единиц возникает только в некоторых точках программы, и при этом постепенно уползает в бесконечность.
Задачка попроще: на ленте записано число n (каретка стоит на правой его ячейке), а справа от него записано n чисел, разделенных неизвестным числом пробелов. Требуется найти их сумму.
Кстати, в команде "? a, b" в каком порядке идут состояния? Вики предлагает сначала состояние для заполненной ячейки, потом для пустой.
Проверил свою программу — у меня ошибка. Неправильно отрабатывается найденная первая метка. Так что размер был бы еще больше (на 8 состояний). Если бы можно было оставить блок не из n, а из n+1 единицы, все было бы гораздо проще.
Интересно, считать ли корректым решением то, в котором блок из n единиц возникает только в некоторых точках программы, и при этом постепенно уползает в бесконечность.
Задачка попроще: на ленте записано число n (каретка стоит на правой его ячейке), а справа от него записано n чисел, разделенных неизвестным числом пробелов. Требуется найти их сумму.
n в итоге будет или n+1 меток — не так уж важно, суть в сборе меток. Так
я просто опустил поиск, потому что не вижу, как его реализовать хотя бы в 20 строк.
? j, k
if 0: j; else: k
1. ? 2, 3 2. 1 .вместо поиска первой метки
я просто опустил поиск, потому что не вижу, как его реализовать хотя бы в 20 строк.
? j, k
if 0: j; else: k
У меня с поиском получилось 52 (если нигде не ошибся)
1: → // ищем пустое место
2:? 3, 1 // (пусть через запятую будет if(0) 3; else 1, а через двоеточие — наоборот :) )
3: 1 // первая оборная метка
4: → // ищем два нуля подряд
5:? 6, 4
6: →
7:? 8, 4
// здесь могла бы быть вторая опорная метка. Но мы бы ее сразу стерли, поэтому и ставить не будем
8: →
9:? 12, 10 // нашли ли ячейку?
10: ← // да — возвращаемся к первой опорной метке и выходим из цикла
11:? 10, 22
12: 1 // нет — ставим новую метку и возвращаемся к первой
13: ←
14? 13, 15
15: 0 // стерли первую метку
16: ←
17:? 18, 22 // нашли ли ячейку?
18: 1 // нет — продолжаем поиск
19: →
20:? 19, 21 // поиск правой опорной метки
21: 0 8 // стерли и ушли на цикл
// сейчас у нас поставлены две опорных метки и стерта ровно одна ячейка. Мы не левой опорной метке, между метками хотя бы два нуля
22: →
23: →
24: 1 // создали центральный блок. Он может оказаться вплотную к правой метке, но это не страшно
25: → // пошел главный цикл
26:? 25, 27
27: 0
28: →
29:? 30, 33
30: 1
31: ←
32:? 31, 37
33: ←
34:? 33, 35
35: →
36: 1
37: ←
38:? 39, 37
39: ←
40:? 39, 41
41: 0
42: ←
43:? 44, 47
44: 1
45: →
46:? 45, 51
47: →
48:? 47, 49
49: ←
50: 1
51: →
52:? 51, 25
Можно написать код в 23 состояния (слегка переделав первую часть программы), в результате работы которого на ленте окажутся два расползающихся в разные стороны блока из 1 и n+1 метки.
1: → // ищем пустое место
2:? 3, 1 // (пусть через запятую будет if(0) 3; else 1, а через двоеточие — наоборот :) )
3: 1 // первая оборная метка
4: → // ищем два нуля подряд
5:? 6, 4
6: →
7:? 8, 4
// здесь могла бы быть вторая опорная метка. Но мы бы ее сразу стерли, поэтому и ставить не будем
8: →
9:? 12, 10 // нашли ли ячейку?
10: ← // да — возвращаемся к первой опорной метке и выходим из цикла
11:? 10, 22
12: 1 // нет — ставим новую метку и возвращаемся к первой
13: ←
14? 13, 15
15: 0 // стерли первую метку
16: ←
17:? 18, 22 // нашли ли ячейку?
18: 1 // нет — продолжаем поиск
19: →
20:? 19, 21 // поиск правой опорной метки
21: 0 8 // стерли и ушли на цикл
// сейчас у нас поставлены две опорных метки и стерта ровно одна ячейка. Мы не левой опорной метке, между метками хотя бы два нуля
22: →
23: →
24: 1 // создали центральный блок. Он может оказаться вплотную к правой метке, но это не страшно
25: → // пошел главный цикл
26:? 25, 27
27: 0
28: →
29:? 30, 33
30: 1
31: ←
32:? 31, 37
33: ←
34:? 33, 35
35: →
36: 1
37: ←
38:? 39, 37
39: ←
40:? 39, 41
41: 0
42: ←
43:? 44, 47
44: 1
45: →
46:? 45, 51
47: →
48:? 47, 49
49: ←
50: 1
51: →
52:? 51, 25
Можно написать код в 23 состояния (слегка переделав первую часть программы), в результате работы которого на ленте окажутся два расползающихся в разные стороны блока из 1 и n+1 метки.
не смог привести этот код в рабочее состояние.
В строке 14 пропущено двоеточие
в строке 52 перепутаны адреса — должно быть
52:? 25, 51
строки с 29 по 37 должны выглядеть так:
29:? 33, 30
30: ←
31:? 30, 32
32: → 24
33: 1
34: ←
35:? 34, 37
36:! // сэкономленное состояние, никогда не выполняется
37: ←
Мне пока не удалось ее обмануть (пришлось написать свой интерпретатор — код на Java, если это не .jar, я запускать не умею)
в строке 52 перепутаны адреса — должно быть
52:? 25, 51
строки с 29 по 37 должны выглядеть так:
29:? 33, 30
30: ←
31:? 30, 32
32: → 24
33: 1
34: ←
35:? 34, 37
36:! // сэкономленное состояние, никогда не выполняется
37: ←
Мне пока не удалось ее обмануть (пришлось написать свой интерпретатор — код на Java, если это не .jar, я запускать не умею)
Числа Фибоначчи — 43 состояния (включая остановку). Каретка вначале стоит на левой метке числа.
0:!
1: ←
2: ←
3: 1
4: →
5: ?4,6
6: 0
7: →
8: ?36,9
9: ←
10: ?9,11
11: 0
12: ←
13: ?14,12
14: ←
15: ?16,14
16: ←
17: ?18,16
18: 1
19: →
20: ?21,19
21: →
22: ?23,21
23: →
24: ?29,25
25: →
26: ?27,25
27: 1
28: ← 11
29: 1
30: ←
31: 1
32: →
33: ?34,32
34: ←
35: 0 4
36: ←
37: ?36,38
38: ←
39: ?40,38
40: ←
41: ?0,42
42: 0 40
0:!
1: ←
2: ←
3: 1
4: →
5: ?4,6
6: 0
7: →
8: ?36,9
9: ←
10: ?9,11
11: 0
12: ←
13: ?14,12
14: ←
15: ?16,14
16: ←
17: ?18,16
18: 1
19: →
20: ?21,19
21: →
22: ?23,21
23: →
24: ?29,25
25: →
26: ?27,25
27: 1
28: ← 11
29: 1
30: ←
31: 1
32: →
33: ?34,32
34: ←
35: 0 4
36: ←
37: ?36,38
38: ←
39: ?40,38
40: ←
41: ?0,42
42: 0 40
Деление с остатком — 31 состояние:
0:!
1: 0
2: →
3: ?4,2
4: →
5: ?25,6
6: →
7: ?8,6
8: ←
9: 0
10: ←
11: ?12,10
12: ←
13: ?14,12
14: 1
15: →
16: ?17,1
17: ←
18: ?19,17
19: ←
20: ?21,19
21: 1
22: →
23: ?24,22
24: → 1
25: ←
26: ←
27: ?29,28
28: 0 26
29: ←
30: ?0,29
На ленте записан делитель, потом (через один 0) делимое. Делимое может быть нулем. Каретка стоит на левой единице делителя.
В конце каретка оказывается на ячейке с нулем. Слева от нее — частное, справа — остаток. И то, и другое может быть нулем.
Кто сделает короче?
0:!
1: 0
2: →
3: ?4,2
4: →
5: ?25,6
6: →
7: ?8,6
8: ←
9: 0
10: ←
11: ?12,10
12: ←
13: ?14,12
14: 1
15: →
16: ?17,1
17: ←
18: ?19,17
19: ←
20: ?21,19
21: 1
22: →
23: ?24,22
24: → 1
25: ←
26: ←
27: ?29,28
28: 0 26
29: ←
30: ?0,29
На ленте записан делитель, потом (через один 0) делимое. Делимое может быть нулем. Каретка стоит на левой единице делителя.
В конце каретка оказывается на ячейке с нулем. Слева от нее — частное, справа — остаток. И то, и другое может быть нулем.
Кто сделает короче?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Программирование на машине Поста