Questions marquées «turing-completeness»

Quel est le jeu minimal de fonctionnalités / structures de langage qui rend

Je me demande si le langage de notation musicale est le langage Turing-Complete ? Ma première pensée est qu'il y a des boucles dans la notation musicale, mais il n'y a aucun moyen d'écrire des branches conditionnelles, non? Je ne suis pas musicien, alors peut-être que quelqu'un peut aider à combler...

Là où il est accepté qu'un langage doit être complet pour être réussi, est-il réellement possible d'avoir un langage de programmation «utile» qui n'est pas complet? Je devrais préciser qu'il s'agit tout particulièrement de la "programmation" des langages au sens traditionnel, et non des langages de...

J'ai une idée générale de la façon dont le processeur gère les instructions, mais je passe mon temps à travailler dans des langues principalement de haut niveau. Peut-être que quelqu'un qui travaille plus près du fer peut fournir des informations précieuses. En supposant que les langages de...

J'ai d'abord essayé de poser cette question sur StackOverflow, mais c'était trop subjectif :-(. Je m'intéresse aux méthodes de définition de la puissance des langages de programmation. La complétude de Turing en est une, mais elle est presque universellement satisfaite. Ce qui serait bien, c'est de...

C'est une question théorique, mais après de nombreuses années de programmation dans ce que je réalise maintenant comme une technique impérative "normale", utilisant principalement le C ++, j'ai découvert cet autre monde de programmation fonctionnelle, sur lequel je suis tombé par hasard tout en...

Les langages complets non Turing offrent un grand avantage par rapport aux langages complets Turing car ils sont beaucoup plus analysables et offrent ainsi des possibilités d'optimisation beaucoup plus larges. Pourtant, ils sont à peine utilisés et l'exhaustivité de Turing est en fait vendue comme...

J'ai essayé de rechercher des explications sur Google, mais la plupart des liens ne disent que des choses comme "FRACTRAN est complet. À titre d'exemple, regardons la multiplication." Je me souviens avoir vu un article du forum xkcd dire que FRACTRAN avait aidé l'affiche à comprendre l'intégralité...