16
\$\begingroup\$

I'd like to introduce a new? programming language I call Shue (Simplified Thue). It has very simple syntax.

Here is a program that checks if an input is divisible by three:

yes
no
3=0
4=1
5=2
6=0
7=1
8=2
9=0
00=0
01=1
02=2
10=1
11=2
12=0
20=2
21=0
22=1
0=yes
1=no
2=no

Try it online!

At the top we can see two lines. These are the output strings, "yes" and "no".

Next are the replacement rules. Let's look at 3=0. This means that whenever we see a 3 we can replace it by 0 (but not the other way round). 12=0 means that the string 12 can be replaced with the string 0.

Then these replacements are performed non-deterministically on the input string until we reach an output state.

For example, if we have the input 14253, it can be reduced to an output state like so:

14253
11253 - 4=1
11223 - 5=2
2223  - 11=2
2220  - 3=0
210   - 22=1
00    - 21=0
0     - 00=0
yes   - 0=yes

Here the answer is yes, and it's pretty easy to prove that yes is the only output state reachable using these rules and this input. This means that the program is well-defined. A program is well-defined if there is at most one output state reachable for every input.

That's it! There are basically no other rules or syntax. There is no way to restrict where or when a substring is replaced (as long as it's possible it will happen). There are no special characters or patterns that match the start or end of the string. Shue is Turing-complete, but only capable of having a finite output set. If the syntax or execution of a Shue program is not completely clear, there are more formal and more precise rules later.

Here are some possibly useful example programs:

Recognize the string "a"*x+"b"*x

yes
no
=|
a|b=|
|=yes
=L
=R
a|R=|R
L|b=L|
a|R=no
L|b=no
ba=#
#a=#
#b=#
a#=#
b#=#
#=no

Try it online!

Semi-recognize the string "a"*x+"b"*y+"c"*(x+y)

yes
=|
=!
a|=|b
b!c=!
|!=yes

Try it online!

Recognize the string "a"*x+"b"*y+"c"*(x+y)

yes
no
=|
=!
a|=|b
b!c=!
|!=yes
b!=!B
BB=B
|!c=C|!
CC=C
C|!=no
|!B=no
ba=#
ca=#
cb=#
#a=#
#b=#
#c=#
a#=#
b#=#
c#=#
#=no

Try it online!

Semi-recognize the string "a"*x+"b"*x+"c"*x

yes
=|
=!
a|b=|>
>b=b>
>!c=!
|!=yes

Try it online!

Exact definition of Shue

The source code is interpreted as a list of bytes. The only characters with special meaning are the newline, the equals sign and the backslash. \n corresponds to a literal newline, \= to a literal equals sign and \\ to a literal backslash. Any other use of \ is an error. Every line must contain 0 or 1 unescaped equals signs.

Or in other words, to be syntactically valid, the program has to match the following regex: /([^\n=\\]|\\=|\\n|\\\\)*(=([^\n=\\]|\\=|\\n|\\\\)*)?(\n([^\n=\\]|\\=|\\n|\\\\)*(=([^\n=\\]|\\=|\\n|\\\\)*)?)*/

Here is the mathematical definition of a Shue program:

A Shue program is a set of terminator strings \$T_e\$, and a set of transformation rules \$T_r\$, which are pairs of strings.

The execution of a Shue program on a input string \$i\$ is defined as follows. Let \$U\$ be the minimal set, so that \$i\in U\$ and \$\forall a,x,y,b: axb \in U \land (x,y) \in T_r \rightarrow ayb \in U\$. Let \$S=U\cap T_e\$.

If \$S=\{x\}\$, then the program will terminate, and \$x\$ will be printed to stdout.

If \$S=\emptyset\$ and \$|U|=\aleph_0\$, then the program will enter an infinite loop.

In all other cases, the behavior is undefined (yes, Shue isn't memory safe).

A compiler

Speaking of not being memory safe, here is the Optimizing Shue Transpiler (osht) version 0.0.2. This is a python program that transpiles a Shue program to C. I wouldn't recommend reading the source code (it even contains some debug prints). But the binaries produced are faster than the interpreter, and seem to work just fine with most inputs.

The actual challenge

Your task is to make a program that checks if a unary input (string matching regex /1*/) is prime in this programming language. That is, is the length of the input string a prime. You must have two output states, one for yes and the other one for no. Shortest code wins.

Test cases (You can use other strings for yes and no)

"" -> "no"
"1" -> "no"
"11" -> "yes"
"111" -> "yes"
"1111" -> "no"
"11111" -> "yes"
\$\endgroup\$
8
  • \$\begingroup\$ Shortest in line or byte? \$\endgroup\$
    – l4m2
    Feb 18, 2022 at 10:14
  • \$\begingroup\$ @l4m2 Shortest in bytes \$\endgroup\$
    – AnttiP
    Feb 18, 2022 at 10:17
  • 1
    \$\begingroup\$ then why atomic-code-golf? \$\endgroup\$
    – l4m2
    Feb 18, 2022 at 10:22
  • \$\begingroup\$ @l4m2 because it's restricted to only one language \$\endgroup\$
    – AnttiP
    Feb 18, 2022 at 10:59
  • \$\begingroup\$ Have you solved this yourself? Is it even possible? \$\endgroup\$
    – Seggan
    Feb 18, 2022 at 16:36

2 Answers 2

13
\$\begingroup\$

Shue, 533 218 208 204 bytes

My original solution was very Turing machine-esque, so here is an improved solution. Unfortunately this solution is difficult to simulate as it's very highly nondeterministic, so there is no TIO link available.

The semi-Thue outputs and productions appear with comments below. Byte count is exclusive of comments.

// [x] is the count of character x.
// Output states: (> prime, (} not prime.
(>
(}
// Start.
=[
=)
// Special cases: 0, 1 not prime.
[)=(}
[1)=(}
// 1. L->R: [a] := [1] - 1.
[1=(1B
B1=a1B
// Move as right of 1s.
a1=1a
// 2. Start of a loop where [a] decreases,
//    and we have checked all divisors between [1] - 1
//    and [a] + 1.
// Prime exit: succeed if [a] == 1.
aB)=>
1>=>
// 3. Begin to check [a].
//     R->L: [b] := x, 0 <= x < [a]; change ) to ] at right if x = 0.
aB)=Cab)
aB)=Da]
aC=Cab
aC=Da
aD=Da
// Move as right of bs.
ab=ba
// 4. R->L: We add [1] ds and y cs, where 0 <= y <= [1] - 1.
// The cs are allowed to move freely to the right, and add one b
// when they pass right of an a; they may vanish at the right end.
// Also, ds move right of 1s, and ds and bs may annihilate each other.
// Overall, the effect is that there is an invariant
// I := [b] - [d] + sum_{each c present} [a to the right of the c]
//    = x + y [a] - [1].
1D=Ed1
1E=Ecd1
1E=Ed1
cd=dc
c1=1c
ca=abc
cb=bc
c]=]
c)=)
d1=1d
db=
// 5. L->R: Move right without passing bs, cs and ds.
// We can only reach the right end if I = 0, i.e., [1] = x + y [a].
(E=(F
F1=1F
Fa=aF
// 6. Composite exit: If ] is at the right, then x = 0, so [1] = y [a] is composite.
F]=}
a}=}
1}=}
// 7. If there is ) at the right, then [1] = x + y [a] with 0 < x < [a],
//    so [1] is not divisible by [a].  Decrement [a] and return to step 2.
Fa)=B)
\$\endgroup\$
4
  • \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$ Feb 22, 2022 at 18:08
  • \$\begingroup\$ Woo! I had such a hard time with this one. Glad you solved it. \$\endgroup\$
    – Seggan
    Feb 22, 2022 at 18:56
  • \$\begingroup\$ Welcome to Code Golf! Is this the BigNum Bakeoff David Moews? \$\endgroup\$
    – apollyon
    Feb 24, 2022 at 15:53
  • 1
    \$\begingroup\$ Yes, that's me. \$\endgroup\$ Feb 24, 2022 at 16:01
3
\$\begingroup\$

136 bytes

P!
C!
=C!
1=C!
=P
11=nq!
qn=nq
rn=nr
r1=1r
1n=r
n1=r
P=P;
;1=1;
;n=.
.n=n.
.r=1.
.q=q.
.!=q!
;r=n,
,q=nq,
,r=r,
,!=!
Pq=P
P1=C
Cq=C
C1=C

Explanation

It implements this primality-testing algorithm (for \$x\ge 2\$):

def isprime(x):
    # r+s+1 is the current divisor (starts at x-1 and counts down)
    # q and r are the quotient and remainder of the division
    # n is the unprocessed part of x
    n, q, r, s = 1, 1, 0, x-2
    while True:
        assert (r + s + 1) * q + r + n == x
        if n and s:  # (1) decrement n, increment remainder
            n, r, s = n-1, r+1, s-1
        elif n:      # (2) clear remainder, increment quotient
            n, q, r, s = n-1, q+1, 0, r
        elif r:      # (3) decrement divisor
            n, r = q+1, r-1
        else:        # prime iff the first divisor was 1
            return s == 0

The values of \$n\$, \$q\$, \$r\$, \$s\$ are stored as the number of n, q, r, 1 [sic] characters in the string.

=C!, 1=C!, =P, 11=nq! are scary angelic nondeterminism rules that handle the 0 and 1 special cases, and convert a longer string like 11111 to P111nq!. See below for a proof that they do nothing else.

qn=nq, rn=nr, r1=1r bubble sort the variables into the order [1n]rq.

1n=r, n1=r implement transition (1).

P=P;, ;1=1; start a left-to-right update pass that will implement transition (2) or (3).

;n=., .n=n., .r=1., .q=q., .!=q! implement transition (2).

;r=n,, ,q=nq,, ,r=r,, ,!=! implement transition (3).

Pq=P, P1=C, Cq=C, C1=C run when \$n=r=0\$, and turn the string into C! if it contains any 1s and P! otherwise.

"Proof" that it works

There is a clear path from any input to the correct final state. I've verified that it works in a simulator if you always apply the earliest applicable rule at the leftmost position, except that the first four rules are handled specially and P=P; is moved to just above Pq=P and chosen only if there is a n or r in the string.

Proving that there is no path to the incorrect final state is harder, but I'll attempt it and handwave some parts.

The first four rules: All other rules conserve the number of PC and ! characters, so unless the first or second rule is used exactly once, or the third and fourth rules once each, the string will never evolve to either of the two terminal states. There are no rules that can delete all the characters left of P or C or right of !, so if C! is added here, it must be the whole string, and if P and ! are added they must be at the ends.

The final four rules: All other rules keep all qs to the right of all rs and 1s, so if Pq=P matches, there must be only q and n and punctuation to the right of it. If there are any ns, it will get stuck, so Pq=P can only lead to a final state if \$n=r=s=0\$ after any ongoing updates complete, i.e., if the number is prime. The other three teardown rules delete the only P, which halts updates. So they can't violate the invariants of the main algorithm while it's still running; they can stop it early, but they'll just get stuck unless \$n=r=0\$.

The middle rules: It's tricky to define invariants that are preserved by each individual rule while there are arbitrarily many rolling updates in progress, but the updates as a whole preserve the invariants of the primality-testing algorithm. These rules seem safe and well behaved to me compared to the first and last four which violate the invariants, so I'm going to handwave it and say they're fine.


An interesting no-go result that I found while writing this

Theorem: A Shue program that solves this challenge can't be a POSIX-compliant text file.

Proof: POSIX requires nonempty text files to end with a newline. Per the Shue spec, that means that ϵ is a valid output state. It is also a valid input state which must be judged composite, so ϵ must mean composite. 1 must also be judged composite, so there must be a path by which 1 evolves into ϵ. Therefore, there is a path by which any unary input evolves into ϵ.

So my program contains no final newline not merely to save bytes, but because it would be incorrect otherwise.

\$\endgroup\$
3
  • \$\begingroup\$ Amazing answer! Mightn't you golf a couple of characters by changing multi-char strings to single-char? I am inexperienced in Shue golfing, so I may well be wrong. \$\endgroup\$
    – Qaziquza
    Apr 29, 2022 at 19:15
  • 1
    \$\begingroup\$ @Pyautogui Maybe, but I'm not seeing how. C! and nq appear 3 times each, but saving 3 bytes there would require adding a 5-byte rule. Let me know if you spot something. I'm not experienced in Shue/Thue either; this is basically a port from FRACTRAN. \$\endgroup\$
    – benrg
    Apr 29, 2022 at 20:16
  • \$\begingroup\$ Yeah, I do not see how either now. Sorry for the wrong statement! Again, amazing answer! \$\endgroup\$
    – Qaziquza
    Apr 29, 2022 at 22:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.