El "Entscheidungsproblem" propuesto por Hilbert en la lógica, derivó en una Informática Teórica previa a la construcción de los primeros ordenadores, y que no fue en absoluto ajena al panorama interdisciplinar anteriormente descrito. La preocupación fundamental fue, desde 1910 hasta 1936 fue el determinar qué clase de problemas pueden resolverse mediante formulaciones constructivas por procedimientos algorítmicos, y cuáles eran los límites. Se buscaba una teoría de lo calculable mediante un procedimiento, un algoritmo, y por eso se formalizaban las reglas del cálculo aritmético. El verdadero padre de la informática teórica fue Kurt Godel: demostró la validez del cálculo lógico de primer orden, y este es el teorema que se conoce como el de "completitud" de la lógica. Pero el resultado más importante de Godel es el de "incompletitud" de la aritmética, 1931, por el que establece que la formalización de la aritmética en la lógica de primer orden hace que existan sentencias ciertas que no son demostrables. Estas sentencias se corresponden con paradojas del tipo "esta frase es falsa": si admitimos que es falsa, entonces se cumple lo opuesto de lo que dice la frase y por lo tanto es verdad; si admitimos que es cierta, la frase dice de sí misma que es falsa: es una paradoja. Si toda fórmula cierta fuera demostrable, ocurriría que se puede expresar una fórmula que dice de sí misma "yo no soy demostrable en la aritmética" con la que surge una paradoja como la anterior.
Ocurre entonces que cualquier demostrador automático de teoremas sobre los números naturales que construyamos se encontrará con la posibilidad de demostraciones de longitud infinita, sin tener ningún criterio para poder parar. Por lo tanto, se conocía ya el límite de lo computable antes de que se construyeran los primeros ordenadores. Posteriormente, se comprobó que cualquier formalización de la aritmética distinta de la lógica tenía el mismo límite: la paradoja. Se investigaron formalizaciones distintas de los procesos constructivos de resolución de problemas, para ver si tenían los mismos límites que la lógica, buscando la noción más general posible de "procedimiento efectivo de cómputo".
En 1935 se llegó a la misma conclusión desde una aproximación basada en funciones: Alonzo Church formalizó la aritmética en el A.-cálculo (posteriormente el lenguaje LISP), y Kleene mediante funciones p,-recursivas. Ambas aproximaciones mostraron los mismos límites que la lógica. Pero la noción más aceptada de procedimiento efectivo de cómputo fue la propuesta por el inglés Alan Turing en 1936. La máquina de Turing, un dispositivo dotado de una memoria en forma de cinta infinita sobre la cual una cabeza lectora puede leer o escribir, y desplazarse a izquierda o derecha de acuerdo con un estado interno y el símbolo leído en la cinta. También mostró la misma limitación que el resto de los modelos. Se establece así la Teroría de la Computabilidad, que es la base de la Informática Teórica. Inmediatamente después, en 1939, se abordó, en el contexto de la Il G.M. la construcción de los primeros ordenadores.
La construcción de las primeras computadoras abrió un sinfín de posibilidades para la formalización a todas las ciencias, pero sobre todo a las ciencias humanas. La lingüística encontró en el ordenador un medio adecuado para estudiar las propiedades formales de la lengua, entendida como la estructura común subyacente a las expresiones individuales del habla de una masa hablante, para estudiar los sonidos, la gramática y los significados de la lengua como sistemas abstractos con entidad propia, separados del mundo físico en el que sólo hay expresiones del habla producidas individualmente.
La psicología también tuvo en los ordenadores un medio distinto al del complicado cerebro humano en el que reproducir los fenómenos de la inteligencia humana, las capacidades del lenguaje y de realizar operaciones 16gico-matemáticas, y este es el embrión de la Inteligencia Artificial hacia 1940, gestado por Alan Turing. Los ordenadores derrumbaron el veto impuesto por el conductismo a la psicología "mentalista". El llamado "Test de Turing" acerca de la posibilidad de modelar las capacidades de razonamiento y lenguaje en un medio computacional, viene a decir que si en la interacción entre una máquina y una persona no se puede distinguir a una y a otra, entonces habrá que admitir la inteligencia de la máquina. Se abre así un intenso debate acerca la posibilidad de modelar la mente, la inteligencia, y de probar empíricamente la bondad del modelo. El área interdisciplinar de las Ciencias Cognitivas se va conformando de esta manera en estos años 40.
