Abstract Rewriting Challenge (Cops)

27

Dies ist ein etwas -ähnlichen Herausforderung. Dies ist der Faden der Polizei; Der Räuberfaden ist da.

Bullen

Ihre Aufgabe ist es, ein abstraktes Umschreibungssystem zu definieren , bei dem die Erreichbarkeit eines Wortes von einem anderen schwer zu bestimmen ist. Sie bereiten folgende Dinge vor:

  1. Eine Reihe von Symbolen, die als Alphabet bezeichnet werden. (Sie können für diese Zeichen beliebige Unicode-Zeichen verwenden. Verwenden Sie jedoch keine Leerzeichen oder Symbole, die nur schwer voneinander zu unterscheiden sind.)

  2. Eine Quellzeichenfolge, die aus Symbolen aus Ihrem Alphabet besteht.

  3. Eine Zielzeichenfolge, die aus Symbolen aus Ihrem Alphabet besteht.

  4. Eine Reihe von Umschreiberegeln, die Zeichen aus Ihrem Alphabet verwenden. (Siehe unten für die Definition einer Umschreiberegel.)

  5. Ein Beweis, der zeigt, ob Ihre Quellzeichenfolge durch sukzessive Anwendung Ihrer Umschreiberegeln in Ihre Zielzeichenfolge konvertiert werden kann. Dieser Beweis kann aus einer tatsächlichen Folge von Umschreibschritten bestehen oder aus einem mathematischen Beweis, dass eine solche Folge existieren muss, oder aus einem mathematischen Beweis, dass eine solche Folge nicht existiert.

Sie werden die ersten vier davon veröffentlichen und den Beweis geheim halten. Die Räuber versuchen, Ihre Antwort zu knacken, indem sie selbst nachweisen, dass Ihre Zielzeichenfolge von Ihrer Quellzeichenfolge aus erreichbar ist oder nicht. Wenn Ihr Beitrag nicht innerhalb von zwei Wochen geknackt wird , können Sie ihn als sicher markieren und in Ihrem Proof bearbeiten.

Die Einreichungen werden gemäß der Anzahl der Zeichen in ihren Umschreiberegeln und ihren Quell- und Zielzeichenfolgen gewertet, wie nachstehend beschrieben. Der Gewinner ist die ungerissene Einsendung mit der niedrigsten Punktzahl.

Was ist eine Umschreiberegel?

Eine Umschreiberegel besteht einfach aus zwei Zeichenfolgen in Ihrem Alphabet. (Eine dieser Zeichenfolgen kann leer sein.) Eine Anwendung einer Umschreiberegel besteht darin, eine Teilzeichenfolge zu finden, die der ersten Zeichenfolge im Paar entspricht, und diese durch die zweite zu ersetzen.

Ein Beispiel soll dies verdeutlichen:

Angenommen Alphabet ist A, Bund C; die Quellzeichenfolge ist " A"; Die Zielzeichenfolge lautet " C" und die Umschreiberegeln lauten

A:B
B:BB
B:A
AA:C

dann ist die Zielzeichenfolge auf folgende Weise erreichbar:

A
B   (using rule 1)
BB  (using rule 2)
AB  (using rule 3)
AA  (using rule 3)
C   (using rule 4)

Wertung

Ihre Punktzahl wird sein

  • die Länge Ihrer Quellzeichenfolge,
  • plus die Länge Ihrer Zielzeichenfolge,
  • zuzüglich der Länge aller Zeichenfolgen, die in Ihren Umschreiberegeln enthalten sind,
  • zuzüglich eines zusätzlichen Punktes für jede Umschreiberegel.

Wenn Sie Ihre Umschreiberegeln wie oben beschrieben mit einem Doppelpunkt als Trennzeichen schreiben, entspricht dies lediglich der Gesamtlänge aller Umschreiberegeln (einschließlich des Trennzeichens) zuzüglich der Länge der Quell- und Zielzeichenfolgen. Eine niedrigere Punktzahl ist besser. Die Anzahl der unterschiedlichen Zeichen in Ihrem Alphabet wird zum Unterbrechen von Bindungen verwendet, wobei weniger besser ist.

Kopfgeld

Ich würde gerne Antworten sehen, die wirklich niedrige Punktzahlen anstreben. Ich werde 200 Wiederholungen für die erste Antwort vergeben, die bei dieser Herausforderung weniger als 100 Punkte erzielt und nicht geknackt wird.

Nathaniel
quelle
3
Bah, nicht ausdrucksstark genug für das MU-Puzzle .
Neil
1
@Neil technisch gesehen sind sie so ausdrucksstark wie Turing-Maschinen - Sie könnten eine Version des MU-Puzzles erstellen, aber Sie würden eine Reihe zusätzlicher Symbole und Übergangsregeln benötigen, um die Mx -> MxxRegel zu implementieren , sodass sie viel komplizierter als die von Hofstadter wird Original.
Nathaniel

Antworten:

9

326 Punkte - Gebrochen von Jimmy23013

Das Level ist Picokosmos # 13 von Aymeric du Peloux (mit einer unbedeutenden Modifikation). Ich habe versucht, eine geschmackvolle Ebene zu finden, bei der "Boxen" und "Wände" den gleichen Charakter haben. Für dieses Niveau war es möglich, den zentralen Drosselpunkt zwei statt nur einer Spalte breit zu machen.

Die Regeln / Initialen / Ziel-Saiten könnten ein bisschen mehr golfen werden, aber das ist nur zum Spaß.

Anfangszeichenfolge:

___##___####_____##_#_#_##_#_!####______##_#####__####_#_######__###__

Zielzeichenfolge:

___##___####_____##_#_#_##_#_#####____!__#_#####__####_#_######__###__

Regeln:

_wW:!
_<:<_
Vv_:!
V_:_V
R:>>>>>>>>>>>>>
V#:#V
#w<:w#
>v_:_v
_wX:#
_!:!_
!:wLW_
L:<<<<<<<<<<<<<
#W:W#
!#_:_!#
_w<:w_
#<:<#
!:_VRv
>v#:#v
Uv_:#
_W:W_
_X:X_
>#:#>
#X:X#
U_:_U
Vv#:!URv
#wW:wLX!
>_:_>
!_:_!
_#!:#!_
U#:#U
Feersum
quelle
Geknackt
Jimmy23013
8

171 Punkte, geknackt von HyperNeutrino

Quelle: YAAAT

Ziel: VW626206555675126212043640270477001760465526277571600601

Regeln:

T:AAAAAT
T:BBU
U:BU
U:ZW
AB:BCA
CB:BC
AZ:Z
CZ:ZC
YB:Y
YZ:V
V:VD
DCC:CD
DCW:W+
DW:W_
___:0
__+:1
_+_:2
_++:3
+__:4
+_+:5
++_:6
+++:7

Nur etwas Offensichtliches. Die tatsächliche Reihenfolge der Umschreibeschritte passt wahrscheinlich nicht in eine SE-Antwort.

jimmy23013
quelle
Ich muss geschwankt irgendwo haben , weil ich nur zu bekommen , VWxwo xaus gebildet ist , jede binäre Zeichenkette von _(0) und +(1) , die zur Bewertung 10*n+6(einschließlich der führenden _; n= nicht-negative ganze Zahl ist ) noch die xgegebene ( 626...601) aus binären welche auswertet gebildet zu 10*n+3(für ein großes n).
Jonathan Allan
Solche Dinge sind durch reine Logik lösbar?
VortexYT
@HyperNeutrino Drat, ich hatte gehofft, dein Riss hätte die Stelle freigelegt, an der ich gestolpert bin.
Jonathan Allan
6

33 Punkte, geknackt von user71546

Ein einfacher Einstieg.

Quelle: xnor
Ziel: xor
Regeln umschreiben:

x:xn
no:oon
nr:r
ooooooooooo:

Die letzte Regel benötigt 11 0 für die leere Zeichenfolge.

xnor
quelle
Gebrochen
Shieru Asakoto
4

139 Punkte (sicher)

Ich wollte, dass diese Antwort geknackt wird, und user202729 hat sie im Grunde genommen in den Kommentaren gelöst, aber niemand hat eine Antwort im Räuber-Thread gepostet, also markiere ich sie als "sicher" und füge meinen Beweis darunter ein.

(Diese Dinge sind offensichtlich viel einfacher zu machen als sie zu knacken. Noch hat niemand versucht, eine wirklich niedrige Punktzahl zu erzielen, und es könnte mehr Spaß machen, wenn diese Herausforderung jemals auftaucht. )


Hier ist eine Selbstantwort. Es ist möglicherweise sehr schwer, sollte aber einfach sein, wenn Sie herausfinden, woher es kommt.

Alphabet: ABCDEⒶⒷⒸⒹⒺⒻ⬛⚪️️🎂←→

Quelle: ←A→

Ziel: ←🎂→

Regeln: (Leerzeichen sind nicht signifikant)

← : ←⬛
→ : ⬛→
A⬛ : ⚪B
A⚪ : ⚪Ⓑ
⬛Ⓐ : E⚪
⚪Ⓐ : Ⓔ⚪
B⬛ : ⚪C
B⚪ : ⚪Ⓒ
Ⓑ⬛ : 🎂
Ⓑ⚪ : ⚪Ⓕ
⬛C : D⚪
⚪C : Ⓓ⚪
Ⓒ⬛ : ⬛B
Ⓒ⚪ : ⬛Ⓑ
D⬛ : ⚪E
D⚪ : ⚪Ⓔ
⬛Ⓓ : C⬛
⚪Ⓓ : Ⓒ⬛
⬛E : A⚪
⚪E : Ⓐ⚪
Ⓔ⬛ : ⬛D
Ⓔ⚪ : ⬛Ⓓ
Ⓕ⬛ : ⚪C
Ⓕ⚪ : ⚪Ⓒ
⬛🎂 : 🎂
⚪🎂 : 🎂
🎂⬛ : 🎂
🎂⚪ : 🎂

Hier ist eine ASCII-Version für den Fall, dass der Unicode nicht für alle gut angezeigt wird.


Beweis

Dies entspricht dem derzeit besten Anwärter für einen Biber mit sechs beschäftigten Bundesstaaten . Ein vielbeschäftigter Biber ist eine Turingmaschine, die nach sehr langer Zeit anhält. Aus diesem Grund ←A→kann die Quellzeichenfolge in der Tat in die Zielzeichenfolge umgewandelt werden ←🎂→, jedoch erst nach mehr als 7*10^36534Schritten, die für eine physische Implementierung erheblich länger als das Alter des Universums dauern würden.

Das Band der Turingmaschine wird durch die Symbole (0) und (1) dargestellt. Die Regeln

← : ←⬛
→ : ⬛→

bedeutet, dass die Enden des Bands immer mit mehr Nullen verlängert werden können. Sollte sich der Kopf der Turingmaschine jemals einem Ende des Bandes nähern, können wir nur eine dieser Regeln anwenden, die uns vorgeben lassen, dass das Band unendlich ist und mit allen Nullen gefüllt beginnen. (Die Symbole und werden niemals erstellt oder zerstört, sie befinden sich also immer am Ende des Bandes.)

Der Kopf der Turingmaschine ist mit den Symbolen ABCDEⒶⒷⒸⒹⒺⒻund dargestellt 🎂. Abedeutet, dass sich der Kopf im Status befindet Aund das Symbol unter dem Kopf eine (0) ist, wohingegen Ⓐ bedeutet, dass er sich im Status befindet Aund das Symbol unter ihm eine (1) ist. Dies wird für die anderen Zustände fortgesetzt, wobei der eingekreiste Buchstabe eine 1 unter dem Kopf und die nicht eingekreiste Version eine 0 darstellt. (Es gibt kein Symbol, Fda der Kopf niemals in einem Zustand Fmit einer 1 darunter endet .)

Der Staat 🎂ist der Stillstand. Es hat die besonderen Regeln

⬛🎂 : 🎂
⚪🎂 : 🎂
🎂⬛ : 🎂
🎂⚪ : 🎂

Wenn der Stopp-Zustand jemals erreicht wird, können wir diese Regeln wiederholt anwenden, um das gesamte Band "einzusaugen" (einschließlich aller zusätzlichen Nullen, die durch mehr als notwendiges Erweitern des Bandes entstanden sind), wodurch wir in dem Zustand zurückbleiben ←🎂→. Daher läuft das Problem der Erreichbarkeit darauf hinaus, ob der Staat 🎂jemals erreicht wird.

Die übrigen Regeln sind die Übergangsregeln für die Turingmaschine. Zum Beispiel die Regeln

A⬛ : ⚪B
A⚪ : ⚪Ⓑ

kann wie folgt gelesen werden: "Befindet sich die Maschine im Zustand A und befindet sich eine Null unter dem Kopf, schreiben Sie eine 1, wechseln Sie in den Zustand B und bewegen Sie sich nach rechts." Das Verschieben nach rechts erfordert zwei Regeln, da die Bandzelle rechts u. U. ein enthält . In diesem Fall sollte die Maschine in den Status wechseln B, oder die Zelle könnte ein enthalten . In diesem Fall sollte sie in den Status wechseln , da sich darunter ein befindet.

Ähnlich,

⬛Ⓓ : C⬛
⚪Ⓓ : Ⓒ⬛

bedeutet "Wenn sich die Maschine im Zustand D befindet und sich eine 1 unter dem Kopf befindet, schreiben Sie eine 0, wechseln Sie in den Zustand C und bewegen Sie sich nach links."

Die verwendete Turing-Maschine wurde 2010 von Pavel Kropitz entdeckt. Obwohl sie häufig im Zusammenhang mit vielbeschäftigten Bibern erwähnt wird, ist ihre tatsächliche Übergangstabelle etwas schwierig zu finden, aber sie kann zum Beispiel hier gefunden werden . Es kann geschrieben werden als

    0   1

A   1RB 1LE
B   1RC 1RF
C   1LD 0RB
D   1RE 0LC
E   1LA 0RD
F   1RH 1RC

Dies kann wie folgt gelesen werden: "Befindet sich die Maschine im Zustand A und befindet sich eine Null unter dem Kopf, schreiben Sie eine 1, wechseln Sie in den Zustand B und bewegen Sie sich nach rechts." Wenn mühsam, sollte es einfach sein, zu überprüfen, ob jeder Eintrag dieser Tabelle einem Paar von Regeln entspricht, wie oben beschrieben.

Die einzige Ausnahme ist die Regel 1RH, die auftritt, wenn sich die Maschine im Zustand F über einer 0 befindet, da es ziemlich sinnlos erschien, die Maschine eine 1 schreiben zu lassen und nach rechts zu gehen, wenn sie sofort anhalten könnte, sobald sie jemals in den Zustand F übergeht über eine 0. Also habe ich die Regel geändert, die gewesen wäre

Ⓑ⬛ : ⚪F

in

Ⓑ⬛ : 🎂

Aus diesem Grund enthält Fdas Alphabet kein Symbol . (Es gibt noch ein paar andere Golfplätze, die ich hätte machen können, aber ich wollte sie nicht zu sehr verschleiern.)

Das war's im Grunde. Die Zielzeichenfolge ist von der Quellzeichenfolge aus erreichbar, aber nur nach einer lächerlichen Anzahl von Schritten.

Eine weitere lustige Tatsache: wenn ich verwendet hätte

←A⚪⚪→

als ausgangspunkt müsste man dann nicht 7*10^36534schritte machen, um anzuhalten, sondern 10^10^10^10^18705352schritte, was in der tat eine sehr große zahl ist.

Nathaniel
quelle
1
Dies sieht aus wie eine Implementierung einer Turing-Maschine
NieDzejkob
1
Ich denke, dies ist die "aktuelle Turing-Maschine mit 6 Bundesstaaten und 2 Symbolen als bester Anwärter", die hier aufgelistet ist . Jetzt muss nur noch jemand beweisen, dass er gleichwertig ist.
user202729
1
Ineffizienter Dolmetscher .
user202729
1
@ user202729 Warum nicht als Antwort posten?
Jimmy23013
3

48 Punkte, geknackt von BB94

Alphabet: abc
Quelle: cbaabaabc
Ziel: cbacbcabc
Regeln umschreiben:

ab: ba
bc: cb
ca: ac
ab: cc
bc: aa
ca: bb
Boboquack
quelle
Gebrochen
BB94
3

287 Punkte, sicher

Quelle: YAAT

Ziel:

VW644507203420630255035757474755142053542246325217734264734527745236024300376212053464720055350477167345032015327021403167165534313137253235506613164473217702550435776242713

Regeln:

T:AAAAAT
T:BBU
U:BU
U:ZW
AB:BCA
CB:BC
AZ:Z
CZ:ZC
YB:Y
YZ:V
V:VD
DCC:CD
DCW:W+
DW:W_
___:0
__+:1
_+_:2
_++:3
+__:4
+_+:5
++_:6
+++:7

Ich fand, dass openssl für diesen Zweck viel einfacher zu benutzen ist als gpg.


Siehe HyperNeutrinos Sprung zur schwächeren Version. In diesem Fall ist die Anzahl von Cs:

22030661124527021657244569669713986649562044939414344827127551659400215941242670121250289039666163853124410625741840610262419007778597078437731811349579211

Und die Hauptfaktoren sind:

220040395270643587721928041668579651570457474080109642875632513424514300377757
100120985046540745657156603717368093083538096517411033964934953688222272684423

Die erste Zahl mod 5 = 2, so dass es möglich ist, die letzte Zeichenfolge zu erhalten.

jimmy23013
quelle
Vorausgesetzt, es handelt sich um eine zufällige 512-Bit-Halbwertszeit, werden die aktuellen PCs Wochen bis Monate
brauchen, um
Es ist jetzt sicher.
user202729
2

402 Punkte

Alphabet: abcdefghijklmnopqrstu
Quelle: abcdoi
Ziel: ioabcdnnnnnnnnnnnnnnnnnn
Regeln umschreiben:

ab: ba
ba: ab
ac: ca
ca: ac
füge hinzu ein
da: ad
bc: cb
cb: bc
bd: db
db: bd
cd: dc
dc: cd
Naan
nb: bn
nc: cn
nd: dn
nm: mn
nj: jn
aoi: eag
boi: ebg
coi: ecg
doi: edg
ae: ha
sei: hb
ce: hc
de: hd
Ioa: Kam
iob: kbm
ioc: kcm
Jod: kdm
ma: aj
mb: bj
mc: cj
md: dj
dg: rdnnnnnnnnnn
cg: qcnnnnn
bg: pbnn
ag: fan
cr: fc
br: fb
ar: fa
bq: fb
aq: fa
ap: fa
äh: io
eq: io
ep: io
ef: io
hf: io
kd: dunnnnnnnnnn
kc: ctnnnnn
kb: bsnn
ka: aln
uc: cl
ub: bl
ua: al
tb: bl
ta: al
sa: al
um: oi
tm: oi
sm: oi
lm: oi
lj: oi
: n

Mit der letzten Regel können Sie so viele ns erstellen, wie Sie benötigen.

Hässlich wie es scheint, ist es eigentlich ganz nett, so oder so ...

Boboquack
quelle
* In aoi:eogwird eogsein soll eag?
Kritixi Lithos
@Cowsquack ja, danke, dass
du das
2

1337 Punkte

Auf jeden Fall nicht wettbewerbsfähig und es hat viel zu lange gedauert, um es zu schaffen (ich hoffe, ich habe keinen Fehler gemacht).

Hinweis:

Versuchen Sie, die Quellzeichenfolge zu verstehen, bevor Sie sich die Regeln ansehen

Alphabet: ABEILRSTabcdefijlr

Quelle: SIbbbbbbbdbffacebbfadbdbeecddfaeebddcefaddbdbeeecddaaaaadfaeeebdddcefbbfadbdbdbeeecdddfaeeebdddcefaddbdbeeecddaaaadfaeeebdddcefbfadbdbdbeeecdddfaeeebdddcbdbffacebfadbdbeecddfaeebddceeefadddbdbeeeecddddfaeeeebddddceefaddbdbeeecdddfaeeebdddceefadadbefadfacdbeecddfaeebddcefaeeefaddbdbeeecdddfaeeebdddcceecdfaeeaddceecefaeadcbefadfacecdfaebdceeeeefadddddbdbeeeeeecddddddfaeeeeeebddddddceeefaddaeecdddbdbffacebfadbdbeecddfaeebddceeefadddbdbeeeecddddfaeeeebddddceefaddbdbeeecdddfaeeebdddceefadadbefadfacdbeecddfaeebddcefaeeefaddbdbeeecdddfaeeebdddcceecdfaeeaddceecefaeadcbefadfacecdfaebdcefaefaeeebdddcdcefaceeaaaceefacdffacebdceeeeefadddddbdbeeeeeecddddddfaeeeeeebddddddceeefaddaeecdddbdbffacebfadbdbeecddfaeebddceeefadddbdbeeeecddddfaeeeebddddceefaddbdbeeecdddfaeeebdddceefadadbefadfacdbeecddfaeebddcefaeeefaddbdbeeecdddfaeeebdddcceecdfaeeaddceecefaeadcbefadfacecdfaebdcefaefaeeebdddcdcefaceeaaaaceefacdffacebdcecefacE

Ziel: SE

Regeln umschreiben:

Ab: bA
bA: Ab
Aa: aA
aA: Aa
Füge hinzu ein
dA: Ad
Ae: eA
eA: Ae
Af: fA
fA: Af
Ac: cA
cA: Ac
IA: AI
AI: IA
Bb: bB
bB: Bb
Ba: aB
aB: Ba
Bd: dB
eB: Be
Be: eB
dB: Bd
Bf: fB
fB: Bf
Bc: cB
cB: Bc
E: BE
S: SB
Ib: AbI
AIa: aI
IdB: dBI
BIe: eIB
AIf: AfI
BIfB: BfiLB
Lb: bL
La: aL
Le: eL
Ld: dL
Lf: fL
Lc: cL
ib: bi
ia: ai
dh: ei
id: di
wenn: fil
lb: bl
la: al
le: el
ld: dl
lf: fl
lc: cl
icl: ci
icL: cI
Ic: jRc
bj: jb
aj: ja
dj: jd
ej: je
br: rb
ar: ra
dr: rd
äh: re
fr: rf
cr: rc
bR: Rb
aR: Ra
dR: Rd
eR: Re
fR: Rf
cR: Rc
cj: jrc
fjr: jf
fjR: Wenn
ES
TB: T
BT: T
bT: T
aT: T
dT: T
eT: T
fT: T
cT: T
T:
ManfP
quelle
2

Beachten Sie, dass ich anfangs einige Fehler gemacht habe, sodass die Punktzahl geändert wurde. Trotzdem ist die Idee dieselbe. Ich hoffe, dass es jetzt keine Fehler mehr gibt.


154 Punkte

Alphabet: P.!xABC[{mD<
Quelle: [x!P.P...P..P.P....P..P.P.....P.P....P......P.P..P...P.P...Pm(61 Zeichen)
Ziel: {CCCCC<(es gibt 5 Cs, also 7 Zeichen)

Regeln:

P.  →  .PP
!.  →  !
x   →  AxB
x   →  
AB  →  BAC
CB  →  BC
CA  →  AC
[B  →  [
[A  →  {
{A  →  {
!   →  !m
mP  →  PmD
Dm  →  mD
DP  →  PD
!P  →  ?
?P  →  ?
!m  →  <
<m  →  <
C<D →  <

Es gibt 19 Regeln, Gesamtanzahl der Zeichen = 67.

user202729
quelle
1

106 Punkte - von HyperNeutrino geknackt

Alphabet: ABCDEFGHIJ

Quelle: FIABCJAGJDEHHID

Ziel: F

Rewrite-Regeln:

B:DCIE
A:IFBA
D:EEFJ
C:GFIC
E:HBJG
F:FEBG
G:HFCJ
H:DIGB
I:FCAH
J:BHEA

EJGI:FF
FFF:J
FF:E
EE:D
DDEA:FI
I:F

Okay, HyperNeutrino hat bewiesen, dass dies nicht lösbar ist. Hierfür gibt es jedoch eine andere Lösung.


Nehmen:

I E C D H G J A F B
1 2 3 4 5 6 7 8 9 10

Der Wert der Quelle ist gerade. Der Wert des Ziels ist ungerade. Wenn wir jede Seite nehmen, den Wert aufsummieren und den Wert auf Mod 2 setzen, bleiben die Werte gleich. Daher kann dies nicht erreicht werden.

VortexYT
quelle
geknackt
HyperNeutrino
Gerne können Sie Ihre geplante Lösung bearbeiten, wenn Sie möchten.
Nathaniel
@ Nathaniel, okay, sicher
VortexYT