В кибернетике Колмогоров проанализировал роль дискретного (в противопоставлении непрерывному) и отстаивал принципиальную возможность возникновения у машин мышления, эмоций, целенаправленной деятельности и способности конструировать ещё более сложные машины. В информатике Колмогоров в 1950-х гг. предложил общее определение понятия алгоритма, а в 1960-х гг., опираясь на алгоритмические представления, создал теорию сложности конструктивных объектов. Эта теория, в свою очередь, была им применена для построения нового обоснования теории информации.

Выдающуюся роль в логике играют две статьи Колмогорова: «О принципе tertium non datur» (Математический сборник. 1925. Т. 32. № 4. С. 668–677) и «Zur Deutung der intuitionistischen Logik» (Mathematische Zeitschrift. 1932. Bd. 35. S. 58–65); обе перепечатаны в книге его избранных трудов «Математика и механика»[177] (вторая в русском переводе – «К толкованию интуиционистской логики»). Обе объединены общей идеей – навести мост между интуиционистской логикой и традиционной, или классической, логикой, причём сделать это средствами, свободными как от идеологии интуиционизма, так и от крайностей теоретико-множественного догматизма. Именно, в статье 1925 г. предлагается такая интерпретация «классической» логики, которая приемлема с точки зрения интуиционизма; напротив, в статье 1932 г. предлагается такая интерпретация интуиционистской логики, которая приемлема с классических позиций.

В статье «О принципе…» Колмогоров принимает предпринятую главой интуиционизма Брауэром критику традиционной логики; при этом Колмогоров обнаруживает в последней ещё один уязвимый, но обойдённый критикой Брауэра логический принцип, а именно принцип, выражаемый аксиомой А → (¬ А → В). Как указывает Колмогоров, эта аксиома «не имеет и не может иметь интуитивных оснований как утверждающая нечто о последствиях невозможного». Колмогоров выдвигает два вопроса: 1) почему незаконное с интуиционистской точки зрения применение принципа исключённого третьего часто остаётся незамеченным; 2) почему оно не привело до сих пор к противоречию? На оба вопроса в статье даются ответы. На 1-й вопрос – потому что применения закона исключённого третьего оправданы, коль скоро возникающее в результате таких применений суждение носит финитный характер; действительно, в этом случае оно может быть доказано и без использования указанного закона (это открытие Колмогорова опровергло точку зрения Брауэра о том, что при получении финитных результатов должны быть запрещены нефинитные умозаключения). На 2-й вопрос – потому что если бы противоречие было получено при использовании закона исключённого третьего, то оно могло бы быть получено и без него; здесь впервые в истории логики произошло предвосхитившее последующие работы Гёделя 1930-х гг. доказательство относительной непротиворечивости формальной аксиоматической системы, т. е. такое доказательство непротиворечивости, которое использует презумпцию о непротиворечивости другой системы. Колмогоров точно очертил круг тех суждений, для которых составленные из них тавтологии классической логики высказываний являются интуиционистски обоснованными: это суть те, и только те, суждения, для которых выполняется закон двойного отрицания. В своей статье Колмогоров впервые предложил позитивный анализ обоснованности с точки зрения интуиционизма традиционной, или «классической», математики. Одновременно Колмогоров впервые сделал интуиционистскую логику объектом строгого математического анализа. В статье была предложена первая система аксиом для этой логики, предвосхитившая формализацию Гейтинга и ныне известная как минимальное исчисление для отрицания и импликации.