C'est un peu la preuve-golf -comme flics et voleurs défi. Ceci est le fil des flics; le fil des voleurs est ici.
Flics
Votre tâche consiste à définir un système de réécriture abstrait dans lequel l'accessibilité d'un mot à l'autre est difficile à déterminer. Vous préparerez les choses suivantes:
Un ensemble de symboles, appelé l'alphabet. (Vous pouvez utiliser des caractères Unicode pour ceux-ci, mais veuillez ne pas utiliser d'espaces ou de symboles difficiles à distinguer les uns des autres.)
Une chaîne source composée de symboles de votre alphabet.
Une chaîne cible composée de symboles de votre alphabet.
Un ensemble de règles de réécriture utilisant des caractères de votre alphabet. (Voir ci-dessous pour la définition d'une règle de réécriture.)
Une preuve montrant si votre chaîne source peut être convertie en votre chaîne cible par application successive de vos règles de réécriture. Cette preuve peut consister en une séquence réelle d'étapes de réécriture, ou une preuve mathématique qu'une telle séquence doit exister, ou une preuve mathématique qu'une telle séquence n'existe pas.
Vous publierez les quatre premiers de ceux-ci, en gardant la preuve secrète; les voleurs essaieront de déchiffrer votre réponse en fournissant leur propre preuve que votre chaîne cible peut ou ne peut pas être atteinte à partir de votre chaîne source. Si votre soumission n'est pas piratée dans les deux semaines , vous pouvez la marquer comme sûre et la modifier dans votre épreuve.
Les soumissions seront notées en fonction du nombre de caractères dans leurs règles de réécriture et de leurs chaînes source et cible, comme détaillé ci-dessous. Le gagnant sera la soumission non fissurée avec le score le plus bas.
Qu'est-ce qu'une règle de réécriture?
Une règle de réécriture est simplement une paire de chaînes dans votre alphabet. (L'une ou l'autre de ces chaînes peut être vide.) Une application d'une règle de réécriture consiste à rechercher une sous-chaîne égale à la première chaîne de la paire et à la remplacer par la seconde.
Un exemple devrait clarifier ceci:
Supposons que l'alphabet soit A, Bet C; la chaîne source est " A"; la chaîne cible est " C" et les règles de réécriture sont
A:B
B:BB
B:A
AA:C
alors la chaîne cible est accessible de la manière suivante:
A
B (using rule 1)
BB (using rule 2)
AB (using rule 3)
AA (using rule 3)
C (using rule 4)
Notation
Votre score sera
- la longueur de votre chaîne source,
- plus la longueur de votre chaîne cible,
- plus la longueur de toutes les chaînes incluses dans vos règles de réécriture,
- plus un point supplémentaire pour chaque règle de réécriture.
Si vous écrivez vos règles de réécriture avec un séparateur deux-points comme ci-dessus, il s'agit simplement de la longueur totale de toutes les règles de réécriture (y compris le séparateur), plus les longueurs des chaînes source et cible. Un score inférieur est préférable. Le nombre de caractères distincts de votre alphabet sera utilisé pour rompre les liens, moins étant mieux.
Prime
J'aimerais voir des réponses qui vont vraiment pour des scores faibles. Je vais attribuer 200 répétitions à la première réponse qui marque moins de 100 points dans ce défi et qui ne se fissure pas.
Mx -> Mxxrègle, donc cela finirait beaucoup plus compliqué que celui de Hofstadter original.Réponses:
326 points - fissurés par jimmy23013
Le niveau est Picokosmos # 13 par Aymeric du Peloux (avec une modification triviale). J'ai essayé de trouver un niveau de bon goût qui pourrait être mis en œuvre avec des «boîtes» et des «murs» ayant le même caractère. Pour ce niveau, il était possible de faire en sorte que le starter central ait deux colonnes de large plutôt qu'une.
Les règles / chaînes initiales / cibles pourraient être jouées un peu plus, mais c'est juste pour le plaisir.
Chaîne initiale:
Chaîne cible:
Règles:
la source
171 points, cracké par HyperNeutrino
La source:
YAAATCible:
VW626206555675126212043640270477001760465526277571600601Règles:
Juste quelque chose d'évident à faire. La séquence réelle des étapes de réécriture ne rentrera probablement pas dans une réponse SE.
la source
VWxendroit oùxest formé à partir de n'importe quelle chaîne binaire de_(0) et+(1) qui évaluent à10*n+6(y compris l'interligne_;n= entier non négatif) mais lexdonné (626...601) est formé à partir du binaire qui évalue à10*n+3(pour un grandn).33 points, craqué par user71546
Un simple pour commencer.
Source:
xnorcible:
xorrègles de réécriture:
La dernière règle prend 11 o à la chaîne vide.
la source
139 points (sécurité)
Je voulais que cette réponse soit fissurée, et user202729 l'a résolue dans les commentaires, mais personne n'a posté de réponse dans le fil des voleurs, donc je la marque "en toute sécurité" et j'inclus ma preuve ci-dessous.
(Ces choses sont évidemment beaucoup plus faciles à faire qu'à casser. Personne n'a encore essayé d'obtenir un score vraiment bas, et il pourrait y avoir plus de plaisir à avoir à cette fin, si ce défi décolle un jour. )
Voici une réponse personnelle. C'est potentiellement très difficile, mais devrait être facile si vous déterminez d'où il vient.
alphabet:
ABCDEⒶⒷⒸⒹⒺⒻ⬛⚪️️🎂←→la source:
←A→cible:
←🎂→Règles: (l'espace blanc n'est pas significatif)
Voici une version ASCII , au cas où l'unicode ne s'afficherait pas bien pour tout le monde.
Preuve
C'est l'équivalent du meilleur concurrent actuel pour un castor occupé à six états . Un castor occupé est une machine de Turing qui s'arrête après une très longue période. Pour cette raison, la chaîne source
←A→peut en effet être transformée en chaîne cible←🎂→, mais seulement après plus de7*10^36534étapes, ce qui prendrait beaucoup plus de temps que l'âge de l'univers pour toute implémentation physique.La bande de la machine de Turing est représentée par les symboles
⬛(0) et⚪(1). Les règlessignifie que les extrémités de la bande peuvent toujours être étendues avec plus de zéros. Si jamais la tête de la machine Turing se rapproche d'une extrémité de la bande, nous pouvons simplement appliquer l'une de ces règles, ce qui nous permet de prétendre que la bande est infinie et commence remplie de tous les zéros. (Les symboles
→et←ne sont jamais créés ou détruits, ils sont donc toujours à la fin de la bande.)La tête de la machine de Turing est représentée par les symboles
ABCDEⒶⒷⒸⒹⒺⒻet🎂.Asignifie que la tête est en étatAet que le symbole sous la tête est un⬛(0), tandis que Ⓐ signifie qu'elle est en étatAet que le symbole en dessous est un⚪(1). Cela se poursuit pour les autres États, avec la lettre encerclée représentant un 1 sous la tête et la version non cerclée représentant un 0. (Il n'y a pas de symboleFcar il arrive que la tête ne se retrouve jamais en étatFavec un 1 en dessous.)L'État
🎂est l'état d'arrêt. Il a les règles spécialesSi l'état d'arrêt est atteint, nous pouvons appliquer à plusieurs reprises ces règles pour «aspirer» toute la bande (y compris les zéros supplémentaires résultant de l'extension de la bande plus que nécessaire), nous laissant ainsi dans l'état
←🎂→. Par conséquent, le problème d'accessibilité se résume à savoir si l'état🎂sera jamais atteint.Les règles restantes sont les règles de transition pour la machine de Turing. Par exemple, les règles
peut être lu comme "si la machine est dans l'état A et qu'il y a un zéro sous la tête, puis écrivez un 1, passez à l'état B et déplacez-vous vers la droite." Le déplacement vers la droite nécessite deux règles, car la cellule de bande vers la droite peut contenir un
⬛, auquel cas la machine doit passer en étatB, ou la cellule peut contenir un⚪, auquel cas elle doit entrer en étatⒷ, car il y a un en⚪dessous.De même,
signifie "si la machine est dans l'état D et qu'il y a un 1 sous la tête, alors écrivez un 0, passez à l'état C et déplacez-vous vers la gauche."
La machine Turing utilisée a été découverte par Pavel Kropitz en 2010. Bien qu'elle soit souvent mentionnée dans le contexte des castors occupés, sa véritable table de transition est un peu difficile à retrouver, mais elle peut être trouvée par exemple ici . Il peut être écrit comme
qui peut être lu comme "si la machine est dans l'état A et qu'il y a un zéro sous la tête, puis écrivez un 1, passez à l'état B et déplacez-vous vers la droite", et ainsi de suite. Il doit être simple, si laborieux, de vérifier que chaque entrée de ce tableau correspond à une paire de règles comme décrit ci-dessus.
La seule exception est la règle
1RHqui se produit lorsque la machine est dans l'état F sur un 0, car il semblait assez inutile de faire écrire la machine un 1 et de se déplacer vers la droite alors qu'elle pourrait s'arrêter immédiatement dès qu'elle entre dans l'état F sur un 0. J'ai donc changé la règle qui aurait étédans
C'est pourquoi il n'y a pas de symbole
Fdans l'alphabet. (Il y a d'autres golfs que j'aurais pu faire, mais je ne voulais pas trop les obscurcir.)C'est essentiellement ça. La chaîne cible est accessible à partir de la chaîne source, mais seulement après un nombre ridicule d'étapes.
Encore un fait amusant: si j'avais utilisé
←A⚪⚪→comme point de départ à la place, alors il ne faudrait pas des
7*10^36534étapes pour arrêter, mais des10^10^10^10^18705352étapes, ce qui est un très grand nombre en effet.la source
48 points, craqué par bb94
Alphabet:
abcSource:
cbaabaabcCible:
cbacbcabcRègles de réécriture:
la source
287 points, sûr
La source:
YAATCible:
Règles:
J'ai trouvé que openssl est beaucoup plus facile à utiliser que gpg à cet effet.
Voir le crack d' HyperNeutrino à la version la plus faible. Dans ce cas, le nombre de
Cs est:Et les facteurs premiers sont:
Le premier nombre mod 5 = 2, il est donc possible d'obtenir la chaîne finale.
la source
402 points
Alphabet:
abcdefghijklmnopqrstuSource:
abcdoiCible:
ioabcdnnnnnnnnnnnnnnnnnnRègles de réécriture:
La dernière règle vous permet de créer autant de
ns que vous le souhaitez.Aussi laid que cela puisse paraître, c'est en fait plutôt sympa, d'une manière ou d'une autre ...
la source
aoi:eogesteogcensé êtreeag?1337 Points
Certainement pas compétitif, et a pris beaucoup trop de temps à créer (j'espère que je ne me suis pas trompé).
Allusion:
Alphabet:
ABEILRSTabcdefijlrLa source:
SIbbbbbbbdbffacebbfadbdbeecddfaeebddcefaddbdbeeecddaaaaadfaeeebdddcefbbfadbdbdbeeecdddfaeeebdddcefaddbdbeeecddaaaadfaeeebdddcefbfadbdbdbeeecdddfaeeebdddcbdbffacebfadbdbeecddfaeebddceeefadddbdbeeeecddddfaeeeebddddceefaddbdbeeecdddfaeeebdddceefadadbefadfacdbeecddfaeebddcefaeeefaddbdbeeecdddfaeeebdddcceecdfaeeaddceecefaeadcbefadfacecdfaebdceeeeefadddddbdbeeeeeecddddddfaeeeeeebddddddceeefaddaeecdddbdbffacebfadbdbeecddfaeebddceeefadddbdbeeeecddddfaeeeebddddceefaddbdbeeecdddfaeeebdddceefadadbefadfacdbeecddfaeebddcefaeeefaddbdbeeecdddfaeeebdddcceecdfaeeaddceecefaeadcbefadfacecdfaebdcefaefaeeebdddcdcefaceeaaaceefacdffacebdceeeeefadddddbdbeeeeeecddddddfaeeeeeebddddddceeefaddaeecdddbdbffacebfadbdbeecddfaeebddceeefadddbdbeeeecddddfaeeeebddddceefaddbdbeeecdddfaeeebdddceefadadbefadfacdbeecddfaeebddcefaeeefaddbdbeeecdddfaeeebdddcceecdfaeeaddceecefaeadcbefadfacecdfaebdcefaefaeeebdddcdcefaceeaaaaceefacdffacebdcecefacECible:
SERéécrire les règles:
la source
154 Points
Alphabet:
P.!xABC[{mD<Source:
[x!P.P...P..P.P....P..P.P.....P.P....P......P.P..P...P.P...Pm(61 caractères)Cible:
{CCCCC<(il y a 5Cs, donc 7 caractères)Règles:
Il y a 19 règles, nombre total de caractères = 67.
la source
106 points - craqué par HyperNeutrino
Alphabet:
ABCDEFGHIJLa source:
FIABCJAGJDEHHIDCible:
FRéécrire les règles:
D'accord, HyperNeutrino a prouvé que cela est insoluble. Cependant, il existe une autre solution à cela.
Prendre:
La valeur de la source est égale. La valeur de la cible est impaire. Si nous prenons chaque côté, totalisons la valeur et prenons la valeur au mod 2, les valeurs restent les mêmes. Par conséquent, cela ne peut pas être réalisé.
la source