Между тем...

По ходу дела вспомнил об одной теме в форуме Wasm.RU, где уже с полгода как возник (с моей подачи, каюсь) вопрос о минимальном наборе команд какого-либо процессора. Ответы неожиданно порадовали, поскольку участники форума вспомнили о стрелке Пирса, штрихе Шеффера и о "загадочных" для меня машинах Шенфилда. Слово "загадочные" я взял в кавычки не случайно: о машине Тьюринга не знает только ленивый, чуть меньше знакома машина Поста (последней, кстати, посвящена увлекательная книга В.А.Успенского, которая так и называется; вот тут свободно лежит ее электронная копия, рекомендую); существует и ряд других подходов. Но что есть "машина Шенфилда", для меня остается загадкой.
Разумеется, я сначала подумал, что эта машина каким-либо образом связана с известной книгой Джозефа Шенфилда (или, вероятнее, правильнее - Шёнфилда) "Математическая логика", изданной еще в 1975 г. в серии "Математическая логика и основания математики". Книга весьма интересная, хотя и сложная для первоначального знакомства с предметом. Но ничего о каких-бы то ни было машинах я в этой книге не нашел. Более того, ни в одной из известных книг по математической логике, побывавших в моих руках (а список этот, поверьте, весьма обширный) о машинах Шенфилда не сказано ни слова.
Один из участников вышеупомянутого обсуждения прислал мне свой университетский конспект лекций по математической логике и теории алгоритмов. Там, действительно, речь идет о машинах Шенфилда. Оказалось, что "машины Шенфилда" - не что иное, как давным давно известные регистровые машины: см., например, М.Минский "Вычисления и автоматы" и Дж.Булос и Р.Джеффри "Вычислимость и логика". Правда, ни в первой, ни во второй книге о машинах Шенфилда - ни слова.
Таким образом, я никак не могу победить "лингвистическую" загадку: причем тут Шенфилд. Понимаю, что это пустяк, не более чем безделица, но интересно все-таки.