Skip to content

Instantly share code, notes, and snippets.

@slavapestov
slavapestov / hard.md
Last active October 1, 2026 13:35
The First Annual International Monoid Word Problem Competition

The First Annual International Monoid Word Problem Competition

Can you find a finite complete rewriting system for any of the 19 monoids with unknown FCRS status, or solve the word problem by some other means in the 2 with unknown word problem?

See https://monoids.net for more information.

Prizes: There is no prize.

Key

The FCRS? column is one of the following:

noby# diff -c3 keyboard.ps.orig keyboard.ps
*** keyboard.ps.orig Mon Jul 27 08:55:38 1992
--- keyboard.ps Mon Jul 27 09:17:11 1992
***************
*** 45,50 ****
--- 45,51 ----
/KB_SUN4_US101A 23 def
/KB_SUN4_JAPAN 36 def
/KB_SUN5_US 37 def
+ /KB_SUN5_US_COMPACT 84 def
#include <stdio.h>
#include <termios.h>
#include <errno.h>
#include <fcntl.h>
#include <sys/termios.h>
#include <sys/types.h>
int main() {
int fd;
protocol P
where A.C == C.A,
A.D == D.A,
B.C == C.B,
B.D == D.B,
C.E == E.C.A,
D.E == E.D.B,
C.C.A == C.C.A.E {
associatedtype A : P
associatedtype B : P
Equivalence classes:
* Equivalence class represented by τ_0_0:
Members: τ_0_0
Conformances:Collection, Sequence
Same-type constraints:
---Rewrite tree---
`--(cont'd)
`--Collection.SubSequence
`--Collection.Index --> [Collection.Indices -> Sequence.Element]
struct AnyEncodable : Encodable {
var wrapped: Encodable
func encode(to encoder: Encoder) throws {
try wrapped.encode(to: encoder)
}
}
struct S {
let x: Int
init(x: Int) { self.x = x }
// This is allowed
init(x2: Int) {
self.init(x: x2)
}
// Example 1
protocol P {
func f() -> Self
}
extension P {
func f() -> Self {
return self
}
}

Keybase proof

I hereby claim:

  • I am slavapestov on github.
  • I am spestov (https://keybase.io/spestov) on keybase.
  • I have a public key ASDtaF_IPmUGQ8saUB0otbOZbh8Y57SqiiSuq23Vlugttwo

To claim this, I am signing this object:

func foo<T>(_: T) {
print("Self = \(T.self)")
}
protocol P {
func requirement()
}
extension P {