Bonjour,
Ah super l'exemple du jeu de la vie en APL2 donné dans le lien de pm42. Ça m'a rappelé qu'il y'a quelques années je m'étais amusé à coder la fourmi de Langton en Brainf**k.
Concernant le sujet du fil, la question de la frontière entre mathématique et informatique théorique me semble difficile à cerner et n'est sans doutes qu'affaire de point de vue.
Il y a la correspondance preuves-programmes qui a été évoquée plus haut. A un niveau tout aussi théorique il y'a même des connexions entre l'informatique théorique et la théorie des ensembles, ce que je trouve vraiment fascinant.
Par exemple le concept des machines de Turing ordinale:
https://arxiv.org/abs/math/9808093
https://arxiv.org/abs/math/0502264
Ce sont des machines de Turing dont les cellules du ruban et/ou le temps de calcul sont indexés par les ordinaux au lieu des entiers, avec des règles appropriées permettant de définir l'état de la machine aux ordinaux limites. Bref, le concept de calcul et d'algorithme transposé au transfini. (dans le premier papier, le ruban reste classique et le temps étendu aux ordinaux, dans le deuxième les deux sont étendus aux ordinaux.)
Ce qui m'avais beaucoup fasciné c'est la correspondance entre les ensembles calculables par ces machines (celle du deuxième papier) et l'univers constructible de Gödel.
-----