LINUX.ORG.RU

На самом деле, UB оказалось не нужно

 , , ,


1

7

Привет, ЛОР!

Как тебе известно, языки Си и Си++ кишат неопределённым поведением, случаи которого вызывают много боли у программистов на этих языках. Обычно это оправдывается возможностью для оптимизаций, но почему-то никто не был в состоянии привести примеры того, насколько связанные с неопределённым поведением оптимизации действительно улучшают производительность кода. До нынешнего момента.

Исследователи из университета Бухареста и технического университета Лиссабона провели испытания с инструментарием LLVM, в котором была отключена эксплуатация UB, и оказалось, что производительность кода в результате изменилась крайне незначительно, а в некоторых случаях даже улучшилась. В дополнение, в случаях, где без эксплуатации UB производительность просела, можно зачастую было применить другие оптимизации, спасающие ситуацию.

Ссылка: https://web.ist.utl.pt/nuno.lopes/pubs/ub-pldi25.pdf

В общем, по всему выходит, что тысячи и тысячи людей уже десятки лет страдают абсолютно зря, и все эти ужасы на самом деле были абсолютно впустую. Такие дела, ЛОР.

★★★★★

Последнее исправление: hateyoufeel (всего исправлений: 1)
Ответ на: комментарий от hateyoufeel

Собственно, компилятор, выкидывающий ошибку компиляции при наличии UB

UB не всегда что-то, что можно выловить в коде. При оптимизации это скорее вещи, позволяющие компилятору лучше рассуждать о коде, что-то вроде: «о, тут переполнение, если j > 7, что UB, а значит на самом деле всегда j <= 7, т.е. где-то есть код, выбрасывающий исключение для выхода из цикла или этот код вообще никогда не вызывается» или «тут доступ по указателю, а дальше проверка, что он не null, можно выкинуть эту проверку и сэкономить пару тактов, т.к. иначе был бы UB».

unC0Rr ★★★★★
()
Ответ на: комментарий от firkax

Только не надо тут говорить что это и есть UB.

Оно самое и есть. Попытка обратиться к соседней переменной через арифметику указателей - это UB (язык не определяет поведение программы в этом случае). И именно этот факт позволяет компиляторам делать вот это:

Расположение переменных в стеке/памяти не обязано быть каким-то конкретным

Так что искать методом тыка соседние переменные в памяти - задача безнадёжная

Ну как-же. Для определенной версии определенного компилятора с определенными настройками на определенной платформе расположение будет вполне конкретным. Почему разработчики компилятора должны слушать этих графоманов из комитета по стандартизации и считать, что программист не может воспользоваться этим фактом?

red75prim ★★★
()
Последнее исправление: red75prim (всего исправлений: 1)
Ответ на: комментарий от red75prim

Ну вот если ты точно знаешь это конкретное расположение, то можешь и использовать адресную арифметику между переменными специально. Но не знаю зачем, это ведь удобств не добавляет никаких. Ну разве что писателям эксплойтов бывает полезно. И повторю, UB тут не больше, чем в том факте что sizeof(int) на разных платформах разный.

Попытка обратиться к соседней переменной через арифметику указателей - это UB (язык не определяет поведение программы в этом случае)

Я выше написал, что именно определяет язык. А именно, «обратиться к ячейке оперативной памяти с таким-то адресом». Будет ли по этому адресу какая-то переменная, или код, или пустое место, или невыделенная память (в результате чего ОС прибьёт прогу с сегфолтом) - уже за пределами спецификации языка (это не его задача! он только дал тебе возможность обратиться к памяти), и зависит от компилятора, платформы и ещё кучи условий. Ты, если хочешь, можешь их даже специально учесть и использовать, но, повторюсь, по-моему это нецелесообразно кроме как для хакерства.

firkax ★★★★★
()
Ответ на: комментарий от firkax

Ну вот если ты точно знаешь это конкретное расположение, то можешь и использовать адресную арифметику между переменными специально. Но не знаю зачем, это ведь удобств не добавляет никаких. Ну разве что писателям эксплойтов бывает полезно. И повторю, UB тут не больше, чем в том факте что sizeof(int) на разных платформах разный.

Авторы GCC с тобой несогласны.

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61502

Можешь сходить рассказать им, что они неправы.

hateyoufeel ★★★★★
() автор топика
Ответ на: комментарий от hateyoufeel

Да, не правы.

То что -O2 сломан я в курсе (и выше писал же: оптимизатор производит неэквивалентные преобразования, ломающие часть кода). Компилирую им только скоростекритичный код типа функций вычисления хешей больших блоков или других числодробилок, и в них внимательно проверяю чтобы у компилятора не было поводов ломаться.

firkax ★★★★★
()
Ответ на: комментарий от firkax

То что -O2 сломан я в курсе (и выше писал же: оптимизатор производит неэквивалентные преобразования, ломающие часть кода).

Он не сломан с точки зрения стандарта Си. То есть, мы опять приходим к тому, что сломан стандарт. А значит, сломан сам язык, описанный этим стандартом, потому что другого описания языка Си нет.

Как я уже писал множество раз: существует на самом деле три разных языка Си. Есть Си, описанный в стандарте. Есть Си как его понимают разработчики компиляторов. И есть Си, существующий в головах сишников. И это три разных языка, хоть первые два и могут быть крайне похожи. А хотелось бы, чтобы был один и тот же.

hateyoufeel ★★★★★
() автор топика
Последнее исправление: hateyoufeel (всего исправлений: 2)
Ответ на: комментарий от hateyoufeel

И это три разных языка, хоть первые два и могут быть крайне похожи. А хотелось бы, чтобы был один и тот же.

Да, я ещё в 2019 году начал свой компилятор (и мануалы-спецификации к нему) писать, но через некоторое время (вроде полтора месяца) мне стало лень. Правда там речь не столько про UB была, сколько про свою «редакцию» языка вообще.

firkax ★★★★★
()
Последнее исправление: firkax (всего исправлений: 1)
Ответ на: комментарий от firkax

И это три разных языка, хоть первые два и могут быть крайне похожи. А хотелось бы, чтобы был один и тот же.

Да, я ещё в 2019 году начал свой компилятор (и мануалы-спецификации к нему) писать, но через некоторое время (вроде меньше месяца) мне стало лень. Правда там речь не столько про UB была, сколько про свою «редакцию» языка вообще.

Ну вот есть kencc – портированный из Plan 9 компилятор от Кена Томпсона. Многие на него дрочат. Правда, большую часть кода в лялексе он собрать не может.

Вообще, ситуация крайне улучшилась бы, если бы для сишки существовал набор тестов на соответствие стандарту: куски кода, которые после сборки должны либо выдавать строго определённое поведение, либо падать при сборке с конкретной ошибкой. Но для си и тем более плюсов такого, насколько мне известно, в открытом доступе нет.

hateyoufeel ★★★★★
() автор топика
Последнее исправление: hateyoufeel (всего исправлений: 1)

Вот я подозревал, что все глупости в программировании не для скрытой пользы, доступной лишь избранным, но просто от плохого, древнего проектирования. И вообще, программирование всё же должно быть человекочитаемым. Чтобы каждая кухарка,как говорится, а то придумали себе египетские иероглифы и по китайски их пишут, чтобы казаться умнее :)

R_He_Po6oT ★★★★★
()
Ответ на: комментарий от static_lab
// добавляет бесконечный цикл вот сюда
for (int j = 0; j < 9; ++j) {

Думаю, что компилятор полагается на то, что результат j * 0x20000001 не может вызвать переполнения, а потому j не может превысить значение, необходимое для выхода из цикла.

ты не мог бы пояснить? я не знаю C достаточно хорошо, но в тексте программы нет записи в j результатов вычислений с 0x120000009. (j * 0x20000001) не должен влиять на j. все записи в j в программе это инициализация и ++j. в программе нет ничего, что позволит j приобрести значение отличное от 0-9. каким образом цикл может выполняться бесконечно? как такое поведение можно назвать приемлемым?

asdpm
()
Ответ на: комментарий от asdpm

В j он ничего и не записывает, он эту переменную вообще выкинул «за ненадобностью», и сделал виртуальную новую, в которой записано бывшее j, сразу умноженное на 0x20000001, и следит только а ней. Поскольку j было нужно в условии j<9, он это условие переделал в (j*0x20000001)<(9*0x20000001). Это переделанное условие не равноценно исходному, но багоделам, которые писали компилятор, плевать.

firkax ★★★★★
()
Последнее исправление: firkax (всего исправлений: 2)
Ответ на: комментарий от anonymous

тролль он или дурак

А есть разница? Ведь здоровый человек никогда не будет притворяться больным.

Если это шутовство и актёрство, которое развлекает и учит публику, почему бы и нет.

Однако в предельном варианте, когда троллинг становится удовлетворением нездоровых потребностей, эти крайности смыкаются и для внешнего наблюдателя уже неотличимы, верно.

ОП не дурак конечно, его треды пока что интересные.

anonymous
()
Ответ на: комментарий от hateyoufeel

сломан сам язык

Просто стандарт Си раскрывает теорему Гёделя о неполноте простыми словами (в терминах стандарта). Либо непротиворечивость, либо полнота (возможность написать любую хрень).

Хотите непротиворечивость и полноту (формальную доказуемость [отсутствия UB]) - пишите на ограниченных языках.

anonymous
()
Ответ на: комментарий от anonymous

Просто стандарт Си раскрывает теорему Гёделя о неполноте простыми словами (в терминах стандарта). Либо непротиворечивость, либо полнота (возможность написать любую хрень).

Теорема о неполноте относится к описанию формальных систем внутри них же самих. То есть, чтобы она тут вообще была релевантна хоть как-то, стандарт Си должен быть написан на Си, а не на английском.

Извини, анон. Попытка хороша, но мимо. Есть Тьюринг-полные языки без UB.

hateyoufeel ★★★★★
() автор топика
Последнее исправление: hateyoufeel (всего исправлений: 1)
Ответ на: комментарий от hateyoufeel

Теорема о неполноте относится к описанию формальных систем внутри них же самих.

Теорема о неполноте о формулах (программах) в формальных системах (стандарте языка Си).

Тьюринг-полные языки без UB

Есть такие же без «проблемы остановки»? UB может быть бесконечным циклом. Как доказать, что программа завершиться, не имеет UB приводящий к бесконечному цику?

anonymous
()
Ответ на: комментарий от anonymous

Теорема о неполноте о формулах (программах) в формальных системах (стандарте языка Си).

Повторюсь: Гёдель писал о том, что в любой самореферентной формальной системе будут либо правдивые утверждения, которые нельзя доказать (т.е. аксиомы), либо ложные утверждения, которые доказать можно (т.е. херота). Си здесь никаким боком не при делах.

Есть такие же без «проблемы остановки»?

Проблема останова является свойством любой Тьюринг-полной системы, но к UB отношения не имеет.

Самый (почти) простой и банальный пример Тьюринг-полного ЯП без UB: Brainfuck.

UB может быть бесконечным циклом.

Не может. Это вполне определённое поведение.

В моём примере выше бесконечный цикл появился в результате трансформаций кода компилятором, но точно так же так мог появиться любой другой дефект.

Как доказать, что программа завершиться, не имеет UB приводящий к бесконечному цику?

Причём здесь Си?

hateyoufeel ★★★★★
() автор топика
Последнее исправление: hateyoufeel (всего исправлений: 1)
Ответ на: комментарий от hateyoufeel

будут либо правдивые утверждения, которые нельзя доказать

Нет, будет формула, которая не выводима - нельзя ни доказать, ни опровергнуть. Можно написать хрень, и не проверишь херота это или нет.

Си здесь никаким боком не при делах.

Если рассматривать стандарт Си как непротиворечивую (допустим!) формальную систему, то можно написать хрень (возможно) содержащую UB и никак не докажешь, что эта хрень содержит UB, узнаешь только по факту (форматирования жесткого диска).

Тьюринг-полного ЯП без UB: Brainfuck

Потому что там нет опреления/аксиомы UB. Нет «неназываемого» значит оно не существует. В стандарте Си хотя бы честно признаются, что есть то, что выходит за границы стандарта в отличии от других.

UB может быть бесконечным циклом.

Не может. Это вполне определённое поведение.

И какой у него наблюдаемый результат/поведение? Я конечно перегнул с термином «цикл». UB - бесконечная «хрень».

anonymous
()
Ответ на: комментарий от anonymous

Зачем нам доказывать что программа завершится? Использую кучу разных программ, которые завершаются только по причине внешних проблем (например сдохло железо), а так их задача - быть включёнными хоть месяц, хоть год, хоть сто лет без перерыва.

firkax ★★★★★
()
Ответ на: комментарий от firkax

Зачем нам доказывать что программа завершится?

Потому что очень многие проблемы в CS часто можно легко свести к проблеме останова. Соответственно, если программа, их описывающая, завершается, то у проблемы есть решение. Но для этого, конечно же, используются языки без Тьюринговой полноты.

В данном контексте, ты наверняка очень хочешь, чтобы компилятор гарантированно завершался при любых входных данных, потому что нахрен тебе зависший компилятор-то?

hateyoufeel ★★★★★
() автор топика
Ответ на: комментарий от anonymous

Нет, будет формула, которая не выводима - нельзя ни доказать, ни опровергнуть

Это и называется аксиомой.

Если рассматривать стандарт Си как непротиворечивую (допустим!) формальную систему

Если рассматривать член как палец, его можно засунуть в дверь и прищемить. Но так делать, конечно же, не следует.

Повторюсь: стандарт Си не является формальной системой даже близко. Насколько мне известно, есть формальные описания языка Си, но они порождены из стандарта. Если интересуешься, посмотри в сторону Compcert – при его разработке что-то такое делали.

hateyoufeel ★★★★★
() автор топика
Последнее исправление: hateyoufeel (всего исправлений: 1)
Ответ на: комментарий от hateyoufeel

Гарантированное завершение компилятора, в его теоретическом понимании, мне неинтересно совершенно. Мне интересно, уложится ли он в разумное время. То есть если он завершится где-то через год, пусть и гарантированно - это компилятор негодный и по факту зависший (ну или исходник негодный, вроде в с++ шаблонах можно такое устроить).

Вообще я считаю, что всякие алгоритмические теоретизирования, особенно из середины прошлого века, когда нормальных компов не существовало, на текущий момент для практики бесполезны и не надо их за пределы изысканий теоретиков вытаскивать. Но графоманы (современные) они такие - им лишь бы что-нить написать, да подлиннее, вот и находят любые темы лишь бы подлиннее написать.

firkax ★★★★★
()
Ответ на: комментарий от hateyoufeel

Это и называется аксиомой

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

Если рассматривать член как палец

Тогда нечего пытаться предьявлять логические (формальные) требования. Раз предьявляешь логические (формальные) требования, то абстрагируйся и рассматривай «член как палец».

стандарт Си не является формальной системой даже близко

Нет эквивалентной непротиворечивой формальной системы.

Compcert

Это как раз попытка это сделать.

anonymous
()
Ответ на: комментарий от anonymous

Аксиому можно вывести

Нет, нельзя. Если её можно вывести, это не аксиома. Хотя бы в Википедию сходи, я не знаю.

Аксио́ма (др.-греч. ἀξίωμα «утверждение, положение», от άξιοω — считаю достойным, настаиваю, требую), или постула́т[1][2] (от лат. postulatum — букв. требуемое[3]) — исходное положение какой-либо теории, принимаемое в рамках данной теории истинным без требования доказательства и используемое при доказательстве других её положений, которые, в свою очередь, называются теоремами

hateyoufeel ★★★★★
() автор топика
Ответ на: комментарий от firkax

Гарантированное завершение компилятора, в его теоретическом понимании, мне неинтересно совершенно.

Да и насрать? Ты явно не шаришь в теме, поэтому твои интересы здесь не играют никакой роли. Как я уже пояснил: очень многие проблемы сводятся к проблеме останова, поэтому её довольно легко и приятно использовать в доказательствах.

Вообще я считаю, что всякие алгоритмические теоретизирования, особенно из середины прошлого века, когда нормальных компов не существовало, на текущий момент для практики бесполезны и не надо их за пределы изысканий теоретиков вытаскивать.

А это не из середины прошлого века. Всякие теории типов Мартина-Лёфа начали появляться в 70х-80х, а в коде их запилили и того позже – в 90х. Для сишника типа тебя это прямо свежачок!

Вообще, между теорией и реализациями в более-менее пригодных для использования инструментах проходит в среднем лет 20. Линейные типы, например, были придуманы как раз в 90х, но реализация в виде Idris и более известного Rust появилась только лет 10 назад. Ждём когда в язычках появятся штуки из HoTT (Гомотопическая Теория Типов).

hateyoufeel ★★★★★
() автор топика
Последнее исправление: hateyoufeel (всего исправлений: 1)
Ответ на: комментарий от zurg

Ждём когда в язычках появятся штуки из HoTT (Гомотопическая Теория Типов).

А что там за штуки, чем интересны, полезны?

Пока никто не знает. Узнаем лет через 10-15. Я пока только библиотечку для Агды видел, но я в HoTT не особо шарю.

Навскидку, это может вылиться в более удобную систему типов с лучшим поиском ошибок, либо в более простой поиск доказательств корректности всякими статическими анализаторами.

hateyoufeel ★★★★★
() автор топика
Последнее исправление: hateyoufeel (всего исправлений: 3)
Ответ на: комментарий от anonymous

Невыводимая/неопровержимая из аксиом теории формула - это не аксиома теории.

Нет, это просто какая-то хрень за пределами области применимости теории.

Есть теории с избыточными аксиомами, которые можно вывести из других аксиом.

Если это можно вывести, это не аксиома. Из некоторых теорий можно убрать часть аксиом, но тогда получатся уже другие теории, как это случилось у Лобачевского с геометрией. Геометрии с аксиомой о параллельности и без неё – это две разные геометрии.

hateyoufeel ★★★★★
() автор топика
Ответ на: комментарий от hateyoufeel

Нет, это просто какая-то хрень за пределами области применимости теории.

Это корректные формулы в теории, эти формулы нельзя вывести или опровергнуть, которые ты назвал «аксиомами» На самом деле, UB оказалось не нужно (комментарий)

anonymous
()
Ответ на: комментарий от hateyoufeel

Ты явно не шаришь в теме, поэтому твои интересы здесь не играют никакой роли

Нет, это ты не шаришь.

очень многие проблемы сводятся к проблеме останова

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

поэтому её довольно легко и приятно использовать в доказательствах.

Доказательствах чего?

firkax ★★★★★
()
Ответ на: комментарий от anonymous

Любая формула, в отношении некоей теории, является либо аксиомой (постулат, на котором основывается теория), либо верной формулой, которая следует из аксиом, либо неверной формулой, которая противоречит аксиомам, либо формулой за рамками теории, если она с аксиомами никак не коррелирует.

Только к языкам программирования это всё имеет малое отношение, никто их в таких терминах не рассматривает.

firkax ★★★★★
()
Последнее исправление: firkax (всего исправлений: 1)

Как тебе известно, языки Си и Си++ кишат неопределённым поведением, случаи которого вызывают много боли у программистов на этих языках. Обычно это оправдывается возможностью для оптимизаций, но почему-то никто не был в состоянии привести примеры того, насколько связанные с неопределённым поведением оптимизации действительно улучшают производительность кода. До нынешнего момента.

Набор каких-то тупых утверждений, потому что

  1. Не кишат. В современном С++20 можно упрограммироваться в хламину ни разу не встретившись с UB.

  2. «оправдывается возможностью для оптимизаций». Какой-то моралофажеский термин. Что значит оправдывается? Кто перед кем что оправдывает? UB является просто следствием устройства языка, модели памяти и прочих вещей. Хочешь устраиваешь себе UB, хочешь не устраиваешь.

lesopilorama
()
Ответ на: комментарий от static_lab

gcc как раз прекрасно разворачивает. В отличие от g++. И не тупит с «оптимизациями».

$ cat main.c
#include <stdio.h>

int main(){
  char buf[50] = "y";
  for (int j = 0; j < 9; ++j){
      printf("%i\n", (j * 0x20000001));
      if (buf[0] == 'x')break;
  }
}$gcc main.c -O3
main.c: In function ‘main’:
main.c:6:7: warning: iteration 4 invokes undefined behavior [-Waggressive-loop-optimizations]
    6 |       printf("%i\n", (j * 0x20000001));
      |       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.c:5:21: note: within this loop
    5 |   for (int j = 0; j < 9; ++j){
      |                   ~~^~~
$ ./a.out 
0
536870913
1073741826
1610612739
-2147483644
-1610612731
-1073741818
-536870905
8
$ 
COKPOWEHEU
()
Ответ на: комментарий от COKPOWEHEU

Кстати всё ещё интереснее: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=30201

Баг был открыт в 2006 году, а в 2024 (!) кто-то чекнул, что в gcc всё работает, и закрыл :)

static_lab ★★★★★
()
Последнее исправление: static_lab (всего исправлений: 1)
Ответ на: комментарий от firkax

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

Как я и написал, ты не шаришь.

Доказательствах чего?

Доказательствах корректности программы, например. Откуда ты знаешь, что твой код делает ровно то, что ты заявляешь? Слова пацана иногда недостаточно, сорян.

hateyoufeel ★★★★★
() автор топика
Ответ на: комментарий от hateyoufeel

Я эти фантазии про доказательства корректности регулярно слышу, но нигде не было реальных примеров. Сомневаюсь, что ты сможешь вот это «то что ты заявляешь» засунуть в какое бы то ни было доказательство вообще, т.к. для этого придётся начать с 100% строгой формулировки парсера и интерпретатора бытовой речи. Остаются только проверки каких-то заданных формулами условий, по сути теоретический аналог тестов, которые разумеется не гарантируют самого нужного.

Да и вообще, слово «корректность» и «делать то что ты заявлешь» это совершенно разные вещи. То, что ты их засунул в свой коммент как синонимы, свидетельствует только о том, что ты сам не в теме и только пересказываешь чьи-то понты (чьи-то - разумеется теоретика, либо теоретизирующего за идею, либо пытающегося таким способом удовлетворить бюрократические требования какого-то государства).

firkax ★★★★★
()
Последнее исправление: firkax (всего исправлений: 4)
Ответ на: комментарий от static_lab

А вот это пример того, как у нормальных программистов половина оптимизаций не нужна. Т.к. нормальный программист эти циклы по жалким трём итерациям развернёт сам, так даже код станет красивее смотреться. А некоторые - да, будут лепить каскадные горы кода и желать чтобы компилятор сам решил что там можно выкинуть.

firkax ★★★★★
()
Ответ на: комментарий от firkax

Я эти фантазии про доказательства корректности регулярно слышу, но нигде не было реальных примеров.

Потому что мы множество базовых полезных алгоритмов уже воспринимаем как данность. А так-то для любого quicksort есть доказательства корректности. Иначе любой алгоритм это просто набор действий, который имеет такую-то временную сложность и не сожрёт весь стек, честно-честно.

opcode
()
Ответ на: комментарий от opcode

Не надо сравнивать математический алгоритм с прикладными. У сортировки есть вполне конкретные математические требования и метрики, которые исчерпывающе её определяют. У прикладного софта ТЗ обычно, хоть и стараются делать построже, но записано бытовым языком. Если бы оно умещалось в формулы, то и кодить скорее всего ничего бы не пришлось почти.

То что стек не переполняется проверить конечно можно, но это всего лишь маленькая техническая подробность, а вовсе и близко не проверка на соответствие требованиям.

firkax ★★★★★
()
Последнее исправление: firkax (всего исправлений: 1)
Ответ на: комментарий от hateyoufeel

Потому что очень многие проблемы в CS часто можно легко свести к проблеме останова. Соответственно, если программа, их описывающая, завершается, то у проблемы есть решение. Но для этого, конечно же, используются языки без Тьюринговой полноты.

Слишком много намешано и получилась каша.

Компьютеры могут практически использоваться для поиска контрпримеров к математическим гипотезам (например, поиск нулей дзета-функции для опровержения гипотезы Римана). Если остановился (то есть нашёл контрпример) - то гипотеза неверна.

Для проблем из CS обычно известно что решение есть (то есть программа поиска решения когда-то остановится и значит это не проблема останова), но из-за комбинаторного взрыва искать его тупым перебором слишком долго.

Для тех проблем из CS для которых известно что общего решения нет (то есть, проблема сводится к проблеме останова, которая не может быть решена в общем случае. Например, парсинг исходников C++), применяют эвристики. Ограничивают глубину рекурсии или время работы программы и вываливаются по ошибке по достижении этого предела.

Языки без Тьюринговой полноты применяются в тех случаях, когда по какой-то причине требуется гарантия останова.

Ну и слова «проблема останова» можно понять двумя способами:

  1. Проблема остановки конкретной программы. Решаемость этой проблемы зависит от конкретной программы. (Опровержение математических гипотез находится здесь)

  2. Проблема останова в теории алгоритмов: создать алгоритм для определения остановит-ли работу алгоритм поданный на вход. Эта проблема неразрешима на машине Тьюринга. (Парсинг С++ находится здесь)

red75prim ★★★
()
Последнее исправление: red75prim (всего исправлений: 4)
Ответ на: комментарий от red75prim

Слишком много намешано и получилась каша.

Сам попробуй @firkax это всё объяснить на пальцах, чтобы он понял. А то он не очень понимает.

Проблема остановки конкретной программы. Решаемость этой проблемы зависит от конкретной программы. (Опровержение математических гипотез находится здесь)

Ага, я про это писал.

hateyoufeel ★★★★★
() автор топика