S'échapper du tarpit (flics)

9

Il s'agit d'un défi de 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 , 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.

Nathaniel
la source
9
Désolé les gars, mais le concours de popularité est un critère de gain objectif. Être un pop-con ne fait pas un défi hors sujet, et ne l'a jamais fait. La dernière méta-discussion a un consensus de +27 en faveur de cela, donc bien que vous préfériez tous les cinq que ce soit différent, vous n'avez vraiment aucune jambe sur laquelle vous tenir. Étant donné que cette question a été close par rapport à la politique convenue, je demande qu'elle soit rouverte.
Nathaniel
2
(notez que WhatWizard l'a fermé pour une raison différente.)
user202729
2
Veuillez ne pas utiliser de votes serrés comme bouton "Je ne suis pas d'accord" ou "Je n'aime pas ça". Les votes serrés doivent être utilisés pour appliquer la politique du site. Si vous n'êtes pas d'accord avec une politique, prenez-la en méta - ne fermez pas les défis qui sont sur le sujet par consensus de la communauté.
Mego
1
@Mego, j'ai voté pour que cela soit trop large, mais je pense également que cela est hors sujet par nos règles existantes pour les contre-pop. Nous nous attendons à ce que les concours de popularité aient une «spécification claire de l'objectif à atteindre», cette question est un do X de la manière la plus créative. Il est clair pour moi qu'il n'y a pas d'autre objectif que d'être une réponse valide et que la balise pop-con est attachée juste pour la garder ouverte.
Ad Hoc Garf Hunter
2
@WhatWizard l'objectif qui doit être atteint est d'être non évidemment Turing complet, la non-évidence étant évaluée en ne se fissurant pas dans la semaine. N'est-ce pas clair?
Nathaniel

Réponses:

10

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.

ais523
la source
Pouvez-vous vérifier si ma réponse manque quelque chose?
user202729
@ user202729: (commentant ici car je n'ai pas le représentant pour commenter) après avoir déménagé. Vous aurez donc besoin d'une autre façon de gérer cela (par exemple, une façon d'inverser les tests, cela ne devrait pas être difficile). Plus particulièrement, cependant, c'est une preuve d'exhaustivité de Turing en termes de comportement d'arrêt, mais la définition de la question exige que vous puissiez également effectuer des E / S, vous devez donc prouver que vous pouvez le faire.
ais523
J'espère que la partie E / S (maintenant) va bien. Quant à l'autre problème, je me rends compte que les états intérieurs ne sont même pas nécessaires, les états intermédiaires résolvent tous les problèmes (bien que je ne sois pas sûr de la façon de le dire)
user202729
@ user202729: ce n'est toujours pas tout à fait correct (par exemple, la question vous oblige à pouvoir sortir des nombres négatifs, et vous devrez également changer le but de isorte que le numéro d'état - qui sera toujours "stop" - ne faire partie de la sortie), mais il est suffisamment proche pour que je ne marque pas cela comme sûr, car vous obtiendrez clairement une fissure complète avec suffisamment de temps et avec une clarification suffisante des règles. Je ne veux pas gagner ce challenge sur les détails techniques.
ais523
Ceci est très proche des restrictions que de.ioccc.org/years-spoiler.html#1992_buzzard.1 utilise. Cette implémentation utilise des entiers de taille fixe et n'est donc pas complète de Turing, et celle-ci est sérieusement limitée dans le nombre de variables dont vous disposez, mais je pense que la preuve est néanmoins similaire.
b_jonas