Как пишет И. В. Поттосин, "в АЛЬФА-языке впервые введено понятие многомерных значений и определены операции над ними, в том числе операции конструирования. Все это вошло в структуру таких языков, как PL/1, ALGOL 68, ADA. Впервые в языке были введены и такие естественные для современных языков концепции, как разнообразие циклов, задание начальных значений выражениями. Интересными, но не повторенными по существу свойствами языка были перечисления и верхние (временные) индексы. В своих метасредствах язык впервые выходил за пределы контекстно- свободных грамматик.

Система АЛЬФА была первой в мировой практике оптимизирующей системой программирования для языков, сложнее, чем FORTRAN. Существовавший в это же время английский проект (Хоукинс и Хакстейбл) для ALGOL 60, аналогичный АЛЬФА по функциональным возможностям, так и не был доведен до конца. Об этом важно сказать потому, что сама возможность существования трансляторов для языков, сложнее FORTRAN, с приемлемой эффективностью объектных программ в то время многими оспаривалась. Система АЛЬФА стала конструктивным доказательством такой возможности, и это существенно, ибо открывало границы созданию новых, семантически более богатых языков. Проект системы был опубликован Ершовым в 1961 году. Монография по системе вышла в свет в 1967 году".

Дальнейшие работы А. П. Ершова по оптимизирующей трансляции привели к появлению широко известной системы АЛЬФА-6. Повторяя во многом систему АЛЬФА, система АЛЬФА-6 обладала более компактной схемой трансляции, более четко был выделен в схеме трансляции внутренний язык представления программы как основа для алгоритмов оптимизирующих преобразований.

В 1969 году А. П. Ершов становится профессором Новосибирского университета (кандидатскую диссертацию он подготовил еще в 1958 году, но в связи с настороженным отношением математиков к новой науке — программированию, защитил ее только в 1962 году. Докторскую диссертацию по методам построения трансляторов он защитил в 1968 году).

В 1971 году А. П. Ершовым была опубликована статья "Универсальный программирующий процессор", которая положила начало работе по проекту БЕТА. Исследования по проекту БЕТА представляли собой многолетнюю (окончательная публикация появилась в 1982 году) методологическую и экспериментальную работу, связанную с осознанием фундаментальных основ трансляции и языков программирования.

"Одной из центральных концепций схемы трансляции БЕТА, — как пишет И. В. Поттосин, — является концепция внутреннего языка. Исследования по внутреннему языку в проекте БЕТА составили заметную часть общемировых исследований, которые ввели понятие внутреннего языка, внутреннего представления программы как фундаментальное для методологии построения большого числа различных языковых процессоров — трансляторов, анализаторов свойств, систем преобразований программ и др. В системе БЕТА внутренний язык выступает в трех качествах — как семантический базис входных языков, как основа для оптимизирующих преобразований на его уровне, как исходное представление для генерации объектного кода на различных ЭВМ".

В 60—70-е годы А. П. Ершов, наряду с решением проблем автоматизации программирования, много внимания уделяет в своих работах вопросам теоретического программирования (первая статья об операторных алгоритмах была опубликована еще в 1958 году). Его работы 1967–1973 годов оказали большое влияние на развитие теоретического программирования. В них был сформулирован ряд проблем теории схем программ, сопоставлены различные направления и модели этой теории, выработана общая система понятий и связаны воедино разнообразные результаты и их применения, иначе говоря, создан фундамент теории схем программ как цельного направления теоретического программирования.

Если теория схем программ имела дело с таким исследуемым и моделируемым объектом, как программа, то в дальнейшей деятельности по теории программирования А. П. Ершов делает следующий шаг, заключающийся в том, что предметом исследований служит процесс работы над программой. Начало этому новому направлению было положено А. П. Ершовым в опубликованной в 1977 году статье "О сущности трансляции". В этой и последующих статьях он сформулировал понятие смешанного вычисления — как фундаментальный принцип системного программирования, определяющий в тех или иных аспектах функционирование процессоров обработки программ.

В 80-х годах А. П. Ершов публикует ряд работ, посвященных проблемам вычислимости, которые также примыкают к теоретическому программированию. В фундаментальной работе 1982 года "Вычислимость в произвольных областях и базисах" проводится глубокий анализ большого числа определений вычислимости, сложившихся в указанных областях, их сопоставление и оценка вклада в общую теорию.

Одной из важных заслуг Ершова перед отечественной и мировой компьютерной наукой является то, что он умел оценить текущее состояние этой науки и наметить те реальные точки роста и перспективы исследований, которые будут определять ее развитие. Так, во второй половине 60-х годов он одним из первых в стране осознал те новые возможности общения с ЭВМ, которые создают системы разделения времени. В 1966 году он организует работы по автоматическим информационным станциям (проект АИСТ). Проект АИСТ, создателем и руководителем которого был А. П. Ершов, объединял широкий круг исследований по архитектуре вычислительных систем. В рамках этого проекта была создана первая в стране развитая система разделения времени АИСТ-0. Реализованная как многомашинный комплекс из отечественных ЭВМ, эта система была во многом пионерской и внесла большой вклад в развитие отечественных работ по архитектуре ЭВМ и операционным системам, которые, к сожалению, были в дальнейшем свернуты из-за ориентации на копирование зарубежных разработок.

С конца 70-х годов и до конца своей жизни А. П. Ершов большое внимание уделял проблемам обучения программированию. Так, в статье 1976 года под названием "Откуда берутся люди, способные создавать надежное программное обеспечение" он изложил план подготовки системных программистов в вузах. Этот план был результатом его многолетней преподавательской деятельности на механико-математическом факультете Новосибирского университета, где он читал общие курсы по программированию и руководил организацией обучения специалистов по системному и теоретическому программированию.