Список проголосовавших за комментарий "Есть, кстати, по-этому поводу любопытный, хоть и малоизвестный спор в области математики и CS.<br/> <br/> Есть тезис черча-тьюринга, который говорит о том, что МТ и лямбда-исчисление эквивалентны, и при этом являются универсальными вычислителями, которые способны вычислить любую функцию, которая в принципе вычислима.<br/> Есть доказательство ложности этого тезиса, в рамках недетерминистской модели Акторов Карла Хьюитта, который доказал, что тезис не верен, и существуют функции, невычислимые на машине Тьринга, именно потому, что машина тьюринга является либо детерминистской, либо ограниченно-недетерминисткой моделью. Доказательство абсолютно ясное, но математический мейнстрим о нем не знает, широко это не известно.<br/> Поэтому, тезис Черча-Тьюринга до сих пор считается верным<br/> <br/> Вот тут, на странице 40 приведено это доказательство<br/> <a href="/r.php?u=https%3A%2F%2Fpdfs.semanticscholar.org%2F7626%2F93415b205b075639fad6670b16e9f72d14cb.pdf&s=977173368">pdfs.semanticscholar.org/7626/93415b205b075639fad6670b16e9f72d14cb.pdf</a>"