Est-ce que la programmation fonctionnelle et les chaînes de Markov sont liées?

Question

David Silver décrit une propriété de Markov Chains comme:

L'avenir est indépendant du passé étant donné les présents

https://www.youtube.com/watch?v=lfHX2hHRMVQ (4 minutes en vidéo)

Cette frappe un accord avec moi parce que j'apprends actuellement sur la programmation fonctionnelle (FP). Dans FP, vous pouvez également ignorer le passé car vos fonctions n'ont besoin que de l'état actuel pour effectuer certaines actions et générer un nouvel état. Cela n'est pas nécessairement vrai avec Object Oriented car votre sortie peut dépendre de plusieurs états dans des endroits différents.

Y a-t-il une connexion plus profonde entre FP et les chaînes de Markov que je ne connais pas?

Est-il exact de dire, par exemple, que les fonctions écrites dans FP sont des chaînes de Markov déterministes?

Answer 1

Il existe en effet une connexion entre une chaîne de Markov et une programmation fonctionnelle. Une chaîne de Markov est un type de Finite-State Machine non-déterministe (FSM), tandis que le chaînage pur fonctions produirait un FSM déterministe. La mise en garde ici est que dans le monde réel (par exemple, les applications Web), vous avez souvent besoin également de fonctions qui ne sont pas pures (par exemple, modifier ou interroger une base de données externe).

J'ai trouvé très utile de modéliser un état de programme en tant que machine à états finis (FSM), à la fois comme une métaphore et comme une façon concrète de modéliser des états et des transitions. Par exemple, un FSM représente bien which actions are allowed at which state lors de l'implémentation des interfaces utilisateur (Web).