Il s'agit d'un défi de flics et de voleurs basé sur la définition des langages et la preuve qu'ils sont Turing complets.

Ceci est le fil des flics. Le fil des voleurs est ici .

Flics

En tant que flic, vous préparerez deux choses:

• Spécification formelle d'un langage de programmation ou d'un autre système informatique. (Les systèmes informatiques sont définis ci-dessous.)

• Une preuve que votre système est Turing complet, selon la définition un peu stricte ci-dessous.

Vous publierez votre spécification de votre langue, et les voleurs essaieront de la "casser" en prouvant son intégralité Turing. Si votre soumission n'est pas fissurée dans une semaine, vous pouvez la marquer comme sûre et poster votre preuve. (Votre réponse peut être invalidée si quelqu'un trouve une faille dans votre preuve, à moins que vous ne puissiez la corriger.)

Il s'agit d'un concours de popularité , donc le gagnant sera la réponse qui aura le plus de votes, et qui n'est ni fêlée ni invalidée. Le défi est illimité - je n'accepterai pas de réponse.

Pour relever ce défi, un système informatique sera défini comme quatre éléments:

• Un "ensemble de programmes" P. Ce sera un ensemble infiniment dénombrable, par exemple des chaînes, des entiers, des arbres binaires, des configurations de pixels sur une grille, etc. (Mais voir la restriction technique ci-dessous.)

• Un "ensemble d'entrée" I, qui sera également un ensemble infiniment comptable, et n'a pas besoin d'être le même ensemble que P(bien qu'il puisse l'être).

• Un "ensemble de sortie" O, qui de la même façon sera un ensemble infiniment dénombrable, et peut être ou ne pas être identique à PouI

• Une procédure déterministe, mécaniste pour produire une sortie ode programme pet d' entrée i, où p, iet osont membres P, Iet Orespectivement. Cette procédure devrait être telle qu'elle pourrait, en principe, être mise en œuvre sur une machine de Turing ou tout autre modèle abstrait de calcul. La procédure peut, bien sûr, ne pas s'arrêter, selon le programme et son entrée.

Les ensembles P, Iet Odoivent être tels que vous pouvez les exprimer sous forme de chaînes d'une manière calculable. (Pour la plupart des choix judicieux, cela n'aura pas d'importance; cette règle existe pour vous empêcher de choisir des ensembles étranges, tels que l'ensemble des machines de Turing qui ne s'arrêtent pas.)

L'exhaustivité de Turing sera définie comme suit:

• Pour toute fonction partielle calculable à fpartir Ide O, il existe un programme pde Ptelle sorte que donné pet l' entrée i, la sortie est f(i)si f(i)une valeur. (Sinon, le programme ne s'arrête pas.)

Le mot "calculable" dans la définition ci-dessus signifie "peut être calculé à l'aide d'une machine de Turing".

Notez que ni la règle 110 ni la balise cyclique au niveau du bit ne sont Turing-complete selon cette définition, car elles n'ont pas la structure d'entrée-sortie requise. Le calcul lambda est Turing complet, tant que nous définissons Iet que nous sommes Oles chiffres de l' Église . (Ce n'est pas Turing-complete si nous prenons Iet Opour être des expressions lambda en général.)

Notez que vous n'êtes pas obligé de fournir une implémentation de votre langue, mais vous pouvez en inclure une dans votre réponse si vous le souhaitez. Cependant, vous ne devez pas vous fier à l'implémentation pour définir le langage de quelque façon que ce soit - la spécification doit être complète en elle-même, et s'il y a une contradiction entre la spécification et l'implémentation, cela doit être traité comme un bogue dans l'implémentation.

Arithmétique avec les yeux bandés

Peut-être une langue assez facile pour commencer, relativement parlant. (Il y a des limites à la difficulté d'un langage que je peux rendre parce que je dois le prouver Turing-complet moi-même!)

Pour ce langage, l'ensemble de programmes est l'ensemble des programmes d'arithmétique avec les yeux bandés comme indiqué dans la section "programme" ci-dessous, l'ensemble d'entrée est l'ensemble d'entiers positifs et l'ensemble de sortie est l'ensemble d'entiers (l'ensemble entier, pas seulement les entiers positifs).

Ce langage est assez intéressant - peut-être même pratiquement utile - car il a un manque de contrôle plus ou moins total, étant entièrement basé sur des calculs sur des nombres que vous ne pouvez pas voir. Cela le rend potentiellement utile comme langage pour implémenter des programmes à l'intérieur de systèmes de cryptage homomorphes .

spécification

L'arithmétique avec les yeux bandés est un langage de programmation ésotérique avec les spécifications suivantes:

Stockage de données

L'état d'un programme arithmétique avec les yeux bandés en cours d'exécution se compose de six variables, chacune pouvant stocker un entier. (Il n'y a aucune limite sur la taille ou petite taille , ces entiers peuvent obtenir,. En particulier, ils peuvent devenir négatifs) sont appelées les variables a, b, c, d, eet i.

Au début du programme, aà einclusif sont chacun initialisés à 0, et iest initialisé à un entier positif extrait de l'entrée utilisateur. (Si aucune entrée n'est disponible, iest initialisé à 1.)

Si le programme cesse son exécution (cela ne peut se produire qu'en raison d'une division par zéro), la valeur de iimmédiatement avant la tentative de division est utilisée comme sortie du programme.

Programme

Un programme d'arithmétique avec les yeux bandés est une liste de commandes, chacune ayant l'une des formes suivantes (où v peut être remplacé par n'importe quel nom de variable, potentiellement un nom différent chaque fois qu'il est utilisé):

• v = v + v
• v = v - v
• v = v * v
• v = v / v

Notez que chaque opérande des commandes doit être une variable; ce langage ne permet pas l'utilisation d'entiers littéraux.

L'exécution du programme est effectuée en exécutant chacune des commandes en séquence, puis en rebouclant vers le début et en continuant d'exécuter les commandes en séquence à nouveau, à l'infini (ou jusqu'à ce qu'il y ait une tentative de division par zéro, ce qui termine le programme) .

Chaque commande a la même sémantique que celle que vous attendez de la notation, qui n'est pas différente de celle utilisée par la plupart des langages de programmation pratiques: les valeurs des deuxième et troisième variables mentionnées dans la commande sont prises, une opération arithmétique (ajouter / soustraire / multiplier / diviser respectivement pour les quatre formes de commande) leur est appliqué et la valeur résultante stockée dans la première variable. La division est ici une division entière, arrondie à 0.

Il n'y a aucun flux de contrôle d'aucune sorte, autre que la sortie du programme; les commandes se déroulent toujours en séquence, jusqu'à ce qu'une division par zéro (le cas échéant) se produise et termine le programme. En particulier, il n'y a aucun moyen de lire directement les variables, seulement de les utiliser comme source de calculs dont les résultats ont un impact sur les valeurs affectées aux autres variables.