Попадаются постоянно на глаза фразы «этот язык тюринг-полон поэтому бла-бла-бла». Вот например, есть такая шняга как комбинаторная логика и родственное ему ski-исчисление. Я читал лично его отца Шойфенкеля, который утверждал, что сама по себе ski избыточна, достаточно одной функции, чтобы выразить все. В то же время, комбинаторная логика эквивалентна LC, которое, в свою очередь, тьюринг-полное. Так что же тогда получается, что для тьюринг-полноты достаточно одной функции?
Как вообще понять, «визуально», является ли язык тьюринг-полным или нет? Какими необходимыми свойствами он должен обладать, для того чтобы называться так?
