При всём уважении к опыту предыдущих ораторов и при всей моей любви к ФП, да и к железу тоже, остаюсь при своём мнении.
Моё мнение таково: основой всего и любого программирования является так называемое "алгоритмическое мышление", иначе известное как "моделирование" и "абстрагирование". Именно ему и следует обучать, поскольку именно с этим пунктом возникают самые серьёзные проблемы, при этом не только у начинающих программистов, но и у многих продолжающих.
А для того чтобы промоделировать вычислительные процессы, и, соответственно, построить алгоритмы решения каких-то "прикладных" задач, необходима модель вычислений. И именно ей необходимо обучать начинающих. Не так уж важно, что именно это за модель. Я лично считаю, что лямбда-исчисление наиболее доступно именно для непосвящённых в программирование благодаря ссылочной прозрачности и семантике переписывания, которую реально можно проводить руками на бумажке. Но машина Тьюринга тоже подойдёт, как и её вариации в виде разных упрощённых учебных процессоров. А вот реальные процессоры "замусорены" слишком большим количеством усложнений связанных с соображениями производительности и историческими причинами.
Опять же, при наличии чётко определённой вычислительной модели можно предметно говорить о корректности алгоритмов и программ. А при желании и возможности — преподавать средства доказательства корректности.
С машиной Тьюринга и переписыванием термов есть проблема, как мне кажется: всегда возникает вопрос, а как оно работает-то в компьютере? Если сказать, что вот именно так и работает, то у человека закрепляется надолго неверное представление. Если сказать это во время формирования первоначальных моделей в мозге, потом переучиться может быть очень и очень тяжело, очень тяжело будет решать львиную долю необходимых прикладных задач. Зачем человеку сразу усложнять путь в драйверописатели какие-нибудь (что актуально)?
Есть, конечно, опасность, что освоив Си и Ассемблер человек возмнить себя кульхацкером и забьёт на дальнейшее образование (и таких примеров много). Поэтому, возможно, разумно сразу говорить и об ассемблере, и о lambda-исчислении, связывая их через какие-нибудь естественные абстрактные машины или же через строгое математическое описание ассемблера.
Эх... Может, и стоит написать такой курс.