Родился в Петербурге в семье знаменитого русского математика Андрея Андреевича Маркова (старшего). Окончил Ленинградский университет (1924 г.), аспирантуру Астрономического института. Доктор физико-математических наук (1935 г.), профессор (1936 г.), член-корреспондент АН СССР (1953 г.).
Работал в Ленинградском университете и Ленинградском отделении Математического института АН СССР, с 1959 г. заведует кафедрой математической логики Московского университета, сотрудничает в Математическом институте АН СССР и с 1972 г.—также в ВЦ АН СССР, где руководит лабораторией логики и структуры машин.
Основные труды относятся к топологии, топологической алгебре, теории динамических систем, теорий алгоритмов и конструктивной математике. Наиболее важные работы посвятил так называемой конструктивной математике и организовал научную школу. На протяжении ряда лет уделяет большое внимание практическим вопросам математической логики, в частности ее применению в теории ЭВМ. Создал терминологию для описания процессов, выполняемых ЭВМ. Опубликовал более 100 работ.
Член КПСС с 1953 г., член бюро Отделения математики АН СССР. Удостоен премии им. П. Л. Чебышева АН СССР, награжден орденом Ленина, тремя другими орденами, а также медалями.