АУ
MaxGraey
Нет. DFA например не Тьюниг полные но подвержены halting problem
Ага, а есть что-то, что полное по Тьюрингу, но не подвержено?
Size: a a a
2020 January 27
AK
Ага, а есть что-то, что полное по Тьюрингу, но не подвержено?
afaik нет
АУ
Ну вот, я про это и говорю. Есть Тьюринг-полнота - получаем проблему останова на сдачу 🤷♀️
EO
halting problem кажется вместе с полнотой по Тьюрингу в комплекте идёт? 🤔
Их обычно берут вместе, да, но сами по себе это отдельные вещи.
История появления halting problem на это тоже намекает немного. Когда Тьюринг придумал свою машину, он вскоре задумался вопросом, а можно ли сделать такую машину, которая была бы противоречием самой себе.
В общем, ему стало интересно поиздеваться над машиной Тьюринга :)
Так впоследствии и появилась halting problem (которая все еще парадокс вроде?)
История появления halting problem на это тоже намекает немного. Когда Тьюринг придумал свою машину, он вскоре задумался вопросом, а можно ли сделать такую машину, которая была бы противоречием самой себе.
В общем, ему стало интересно поиздеваться над машиной Тьюринга :)
Так впоследствии и появилась halting problem (которая все еще парадокс вроде?)
h
Eugene
не, крутизна языка должна оцениваться тем, насколько легко на нём сделать собственный интерпретатор )))
мало кто тут сможет превзойти полстранички лиспа 1956 г...
мало кто тут сможет превзойти полстранички лиспа 1956 г...
транслятор в машкод интереснее.
M
afaik нет
Почему?
Что такое полнота по Тюрингу? Это когда при конечных входных данных мы получаем конечное выходные данные выполнив конечное число шагов. Если «конечность» всего этого гарантиркуется на этапе компиляции, то у нас не будет проблемы остановы. Рзве нет?
Что такое полнота по Тюрингу? Это когда при конечных входных данных мы получаем конечное выходные данные выполнив конечное число шагов. Если «конечность» всего этого гарантиркуется на этапе компиляции, то у нас не будет проблемы остановы. Рзве нет?
EO
MaxGraey
Почему?
Что такое полнота по Тюрингу? Это когда при конечных входных данных мы получаем конечное выходные данные выполнив конечное число шагов. Если «конечность» всего этого гарантиркуется на этапе компиляции, то у нас не будет проблемы остановы. Рзве нет?
Что такое полнота по Тюрингу? Это когда при конечных входных данных мы получаем конечное выходные данные выполнив конечное число шагов. Если «конечность» всего этого гарантиркуется на этапе компиляции, то у нас не будет проблемы остановы. Рзве нет?
Можно компилятор загнать в проблему останова, тем самым он не сможет доказать конечность твоего кода.
AK
MaxGraey
Почему?
Что такое полнота по Тюрингу? Это когда при конечных входных данных мы получаем конечное выходные данные выполнив конечное число шагов. Если «конечность» всего этого гарантиркуется на этапе компиляции, то у нас не будет проблемы остановы. Рзве нет?
Что такое полнота по Тюрингу? Это когда при конечных входных данных мы получаем конечное выходные данные выполнив конечное число шагов. Если «конечность» всего этого гарантиркуется на этапе компиляции, то у нас не будет проблемы остановы. Рзве нет?
Из такого определения следует, что язык не может одновременно быть тюринг-полным и иметь проблему останова, а это очевидно не так
AT
MaxGraey
Почему?
Что такое полнота по Тюрингу? Это когда при конечных входных данных мы получаем конечное выходные данные выполнив конечное число шагов. Если «конечность» всего этого гарантиркуется на этапе компиляции, то у нас не будет проблемы остановы. Рзве нет?
Что такое полнота по Тюрингу? Это когда при конечных входных данных мы получаем конечное выходные данные выполнив конечное число шагов. Если «конечность» всего этого гарантиркуется на этапе компиляции, то у нас не будет проблемы остановы. Рзве нет?
А откуда взялось условие конечности выходных данных и числа шагов???
AT
У машины Тьюринга ленты-то бесконечные.
M
У машины Тьюринга ленты-то бесконечные.
В смысле бесконечные? Критерии то выхода всегда есть
AT
MaxGraey
В смысле бесконечные? Критерии то выхода всегда есть
В смысле по определению бесконечные. 😃
Нет никаких критериев выхода. Можно тривиально сделать бесконечный цикл, который печатает на выходную ленту одно и то же раз за разом. Полностью валидная машина Тьюринга.
Нет никаких критериев выхода. Можно тривиально сделать бесконечный цикл, который печатает на выходную ленту одно и то же раз за разом. Полностью валидная машина Тьюринга.
E
транслятор в машкод интереснее.
оптимизирующий транслятор в разные машкоды ещё интереснее.
и понеслась...
и понеслась...
FO
Eugene
оптимизирующий транслятор в разные машкоды ещё интереснее.
и понеслась...
и понеслась...
вот бы завезли оптимизирующий транслятор исходники->исходники
h
Eugene
оптимизирующий транслятор в разные машкоды ещё интереснее.
и понеслась...
и понеслась...
изврат беспределен, и это метод оптимизации некоторых задач (читай - управление обществом, human-bio-centric democratic algocracies) - один пример такой демо-алго-кратии это
telnet lambdamoo.moo.mud.org 8888 request programmer bit
и lambdamoo - крайне извратная система
какое отношение к оптимизации и компиляторам? а у lambdamoo крайне извратный внутренний язык.
telnet lambdamoo.moo.mud.org 8888 request programmer bit
и lambdamoo - крайне извратная система
какое отношение к оптимизации и компиляторам? а у lambdamoo крайне извратный внутренний язык.
M
В смысле по определению бесконечные. 😃
Нет никаких критериев выхода. Можно тривиально сделать бесконечный цикл, который печатает на выходную ленту одно и то же раз за разом. Полностью валидная машина Тьюринга.
Нет никаких критериев выхода. Можно тривиально сделать бесконечный цикл, который печатает на выходную ленту одно и то же раз за разом. Полностью валидная машина Тьюринга.
Мы говоим про то, существует ли такая машина тьюринга у которой не будет проблемы останова) Самом собой, что существует машина тьюринга у которой она будет) Этого никто не отрицает
E
вот бы завезли оптимизирующий транслятор исходники->исходники
легко -- берёшь оптимизирующий компилятор в машинный код, получаешь бинарник, декомпилируешь этот бинарник -- и вуаля! готовы исходники после оптимизирующей трансляции!
M
Иными словами, если у нас такая машина / язык у которых нету проблемы останова, но при этом будет выполняться полнота по Тьюрингу?
FO
Eugene
легко -- берёшь оптимизирующий компилятор в машинный код, получаешь бинарник, декомпилируешь этот бинарник -- и вуаля! готовы исходники после оптимизирующей трансляции!
не. я хочу оптимизацию на уровне исходных кодов (хотя бы ветки в правильном порядке ставить, удалять лишние goto метки) без трансляции в машкоды
E
нужен неполный по тюрингу язык без проблемы останова, на котором можно написать его собственный транслятор!!!