Two alphabets One substitution Slashes programs Halting problem

Submit

Language is selected by the extension of the file. See the list of supported languages to know the extension of your language.

Problem

This description is written as markdown.

For several ///[1] (slashes) programs, decide whether it halts or not.

Each program shall

- have only a line, and
- be in the format of `^/[ab]*/[ab]*/[ab]*$` in POSIX BRE[2].

# What is ///[1]
- An esolang.
- Output only.
- Has two functions: quine and self-modification.
- Proven to be Turing-complete.

# Input specification
- Each program is separated with a LF.
- Has a trailing LF.
- Always follow the following syntax.
- Every line shall have 50 or less characters excluding the trailing LF.

## Input syntax
```
input = line | input line
line = program <0x0a>
program = <0x2f> ab_s <0x2f> ab_s <0x2f> ab_s
ab_s = *EMPTY* | ab_s ab
ab = <0x61> | <0x62>
```

# Output specification
- Separate each with LFs.
- Has a trailing LF.
- Each line shall be either 'Yes' or 'No'.
- For \$n\$th line of the input,\$n\$th line of the output must be
- 'Yes' if the program halts, or
- 'No' otherwise.

## Output syntax
```
output = line | output line
line = yes <0x0a> | no <0x0a>
yes = <0x59> <0x65> <0x73>
no = <0x4e> <0x6f>
```

# How to emulate the program
1. Let a given program be `/`\$p\$`/`\$q\$`/`\$r\$.
2. If \$p\$ is a substring of \$r\$(note 1), go to step 6.
3. Otherwise eliminate `/`\$p\$`/`\$\q$`/` from your program.
4. Output \$r\$ and eliminate the string from your program.
5. Now the program is empty, the program terminates.
6. Replace the leftmost \$p\$ of the string \$r\$ with \$q\$.
7. Let the result of step 6 be the new \$r\$.
8. Go to step 2.

(note 1) An empty string is always a substring of any strings.

# References
[1] https://esolangs.org/wiki////
[2] https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap09.html#tag_09_03

# Poster of this problem
tail spark rabbit ear

Options

exec is denied

rejudge feature is enabled

now post-mortem time, all source codes will be revealed

Sample input:_

/ab/ba/bba
/bab/aab/babab
///
/bb//bbbbbbbbbbb
/ab/ba/ab
/ab/bba/ab
/ab/bba/abb
/babaaaab/a/aababb
/ab/baa/abbbaaaaa
/bbb/aaaabbaa/
//babaa/b
/a/bb/bbbbbbb
/babbb/b/abbaa
/bba/bbaabbabb/abbabbaa
/ba/ba/abaaab
/a/bbbaa/a
/b/baabbb/bbbabba
/bbbbaaa/aabaababa/aababbbb
/bbbaab/bb/bbabbaaba
//a/babbaba
/bbbbbaabb/baaaaa/aa
/ababa/abbba/bbaababbb
/babbb/bbbab/abb
/babbaa/abbbbbb/
/ba/bbb/bbaaa
/aaaab/bbbb/aababb
/ababbb/babababba/b
/bab/bb/baabbaaa
/aabbba/abbaaab/aaabbabbb
/baabbba//baabbaabb
/bbabbb/bbbbba/abbaaaaab
/baabbaaa/abaabab/abbbaa
/abbabbbb/ba/ba
/aaababbb//aaab
//abaabb/aababaaa
/bbaab/bab/
/baabba/abbbaaaab/ba
/bbbbba/a/aaaaaaa
//aba/aabbaa
/bba/bbbabab/babbab
/ba/b/bbbb
/bbaabab/baabababa/
//baaab/baaaab
/aab/bbbbba/bab
/ababbbbaa/bbabaa/babba
/bbb/babaaabab/
/b/abbab/baaa
//abbaab/aaaaaaa
/aababa/ab/aaa
/aa/ababbb/bbba
/ba//baabaaa
//abaaaba/abbb
/abaa/b/ab
/bbb/bab/abbaab
//aabbaaba/b
/baabbabbb/a/aab
/bbabaab//babb
/babbabbaa/bbaa/abbbaaabbbbaaa
/bb/baa/aaabaab
/bbabaababa/bb/abbb
/a/bbaaabbbb/abaaaab
/bbbabaabbabaa/babba/
/babbbaab/ababaaaaaa/abba
/bbbab/bbabababbaaba/aababbbab
/baaaab/babaaaabbba/bbabb
/aaa/babbbbbabaaab/baabbbaab
/b/baaaabbbbaab/aababbababba
/bba/bbbbbabbba/baabbaabbbbab
/bb/bbbbbbbbab/bbbbaaaabbbaab
/bbaabbab/aaabbb/
/abbabbbaaa/baaba/b
/abbaab/abbbb/bab
/bbaababaabaab/ba/aaaabbb
/bb/abbabbbaaaaabb/abaabbbbaaaa
/babababbbab/aaaaabbabab/
/ba/abaabb/aaaabba
/baababb/ababaabbbbaaa/abababababbaaa
/baabbaa/abbbba/aaaabbbabaa
/abbaabbbbabaaa/bbbabaaabaabab/baaabbbbb
/abbbbbbbab/bb/bbbabaaabba
/aabab/bbabba/bab
/a/aaababaabbbaaa/abba
/ababaababbbaab/abab/ab
/aabaaababab/aabbbabbaaba/abbbabbb
/bbbbaaaaabbaa//bbb
/bbbabbaa/abbbbabbbbbaaa/ab
/baaabbbaa/aabbabbba/
/bbb/aba/bbaaaaabba
/bbbaba/ab/aaababab
/babb/baaababbaabaa/babbbbbbab
/bbbbbababaaab/bbbaba/abbbab
/bbbb/a/bababababaab
/abbabaaa/bababbabababab/bbba
/abaaa/aaaa/aa
/baabababb/abbb/bababbbaa
/bbbba/bbabaaaa/babbaba
/abbbaababb/bab/babbbaaabb
/bbabaaaabbab/abb/ababbbaabaa
/ababb/aaabbbaa/bbbb
/aaabbaababb/aabaaabbbababa/babaaabaababa
/bbbaa/aaaabaabbbaab/a
/abaaaabb/bbabaaabba/babbaaa
/abbb/bbabbabaaa/abba
/aabbaababbb/bbbaa/abbaaaa
/bbaabab/bbababbb/babababaaaaba
/aaa//babbabbba
/bbaaaab/bab/ababa

Sample output:

Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
No
No
No
No
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
No
No
Yes
Yes
No
Yes
Yes
Yes
No
No
Yes
Yes
Yes
No
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
No
No
No
Yes
Yes
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

Sample input:_

/babbb/ab/baaabbaabbb
/aabaaaa/aabbaaababbbb/bb
/bbba/aaabba/bababbbaa
/abba/abbbbbaab/baababbbbaaab
/babbaaaabaabb/abbbbaa/babbaba
/aabbbbbabbb//ababaaabaaa
/baaabb/baabaabbbbbaa/bbbbbaaa
/babba//babaaa
/a/b/b
/aabbab/bbaaaaa/aaababa
/baaabbaaab/aabbbbbb/bbbbabbaaab
/aaaabbabbabaa/bbaaaa/bbb
/baabababbaba/bbabaabaaababa/bbabbabbaaaa
/baaaabbab/baaaba/bbbaaaabb
/bbbaabaaabaab/bb/baaaabaaababa
/a/bbbbbba/bbbbab
/baabbbba/aaabaaabbb/ba
/abbaaabab//aabb
/abaaababaab/abbb/bbb
/aaab//
/bbbbbaaa/aabababbb/baaaaaaabb
/aaababbabbbaa/a/bab
/baabbbbaab/bbbabaaa/baabba
//bbab/ababbbbba
/bbaaa/ababbbabb/babbabbbabaa
/aaabab/aabb/
/bbab/ababaabaabb/aaaba
/abbabbabb/b/abababa
/bbb/bbabbababba/a
/aabbaba/baaaabbaabaaa/
/a/aababaaa/babaaabb
/aaaabb/baabaaabab/bbabaabaaba
/baaabbbbbbbbab/a/babbaabaaabbba
/aaabbaaaababab/abaabbb/bbaa
/babbabbaa/babaaabaa/ababbbabbbaba
/aabbbbba/baa/aba
/aa/abbabbaaaaaaa/aaabaabaaaaba
/aa/baabbbbb/bbaaabbba
/abababbabaa/abbbaababaaaab/abbaababaabaa
/baaabbaaa/babaaa/abbbaaba
/abbaa/bba/aaa
/abaabaaabbabaa/aaabbbba/abbabbabb
/bbbba/aaaabba/bababbbaaa
/aab/bbbaabaa/baaabbbb
/abbbababaabba/baaabaa/a
/b/ba/abbbaaaababba
//aaaababbbbaa/abaabbaaaabab
/b/aaab/abababaaba
/aabbbbbaaabab/babbbaaabb/aaababbbbbbb
/a/abbbbbaabb/baaaaaaabb
/bbbba/baaa/ab
/abbababaabbbba/baabbbbbaaba/aaabbabaabab
/aaaaabaaab/aaabbabbabbba/bbbbbaaababa
/b/abbbbaabba/
/babababbba/abbbb/aaaaaababbbbb
/bbabbabaa/bababab/ab
/ba/aaaaab/baabab
/babb/abbbaaa/baabbaabbaabaa
/baaabaaaabb/ababa/ababaabaaaba
/abbabbaaabbb/ab/baaabbaaaba
/abaabbbabab/babaab/bbaabbabbbaabb
/babaabbba//abbbababba
/bb/bababbbaabb/aabaaab
//baaba/baaabbabaabaab
/abaaba/abababbbabaa/b
/baaaaaabbaaaa/aa/
//babbbba/bbabbba
/abbbba/bbaaaaabbababa/ba
/abaab/aaabbbabaabbaa/bbbabaaabba
/aaabaaa/abbaabbaaaaaa/aabbbbbbbaabb
/abaaab/aaabaabba/aaaa
/bbbabaaab/aa/aaabbbabbba
/baaabaaaabaaa/bbbbaabba/bbabb
/abaaabbbbaaabb/bab/
/abaaa/babbbbbbbaabb/bababbaaab
/bbbaabbaab//
/babaabaabaabba/bbaabbb/abbbaab
/babbaababab/aaababa/bbbbaa
/ba/aab/aaaaabaaba
/abaaabbaba/bab/bbaaa
/aa/bab/ababbbbabb
/abaa/babbbababbbbba/b
/baabaabababbb/babaaabababbaa/bbbbabbbbabbab
/a/abaabbb/abbbbbbbbbbaab
/baab/ab/aaabaaa
/abaaababbabbab/aabbaba/bbabbbaaaab
/babb/aaabbb/a
/abaaa/b/baba
/abab//aaababaaaabab
/baabbaabbbaaab/aabbbaaabaaa/b
/abbab/aabababa/aaabaaaababaab
/bbbabaabbaa/babaa/bbaabbaabb
/abb/aab/a
/bbbb/bbbbaabab/abbaa
/ababaababab/baaabbbabbaaba/baabaa
/bba/bbaab/aababba
/aabaaaba/bbaaa/bbbba
/b//abbaaaababb
/aaaba/a/bbaaa
/bbbabbbaaabbb/bbbabbbbbbab/babbaaba

Sample output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
No
No
Yes
Yes
Yes
Yes
Yes
No
Yes
No
No
No
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes

Ranking

Ruby _

Ruby2 _

Perl _

Python3 _

SNOBOL _

J _

C _

Java _

AWK _

sed _

Bash (builtins) _

make _

gs2 _

Lazy-K _

Scala _

Language Ranking_

return to the top page