Yo creo que sí sería posible. Tendría que ser una especie de programa que fuera capaz de cambiar su código en tiempo de ejecución. A medida que fuera recibiendo nueva información, compararla con el razonamiento ya existente y si el nuevo fuese más exitoso entonces cambiarlo.
Antes de aventurarnos a decir como seria ya en la practica, primero hay que responder preguntas tan basicas como: ¿Que es aprender?, ¿agregar nuevos estados en la Maquina de Turing o simplemente apartir de estados ya existentes contruir operaciones mas complejas?
Respecto a "cambiar su codigo en tiempo de ejecucion", simplemente en la maquina de turing es leer una especie de configuracion en alguna parte de la cinta, tan sencillo como eso.