Renaming CTL and CPS?

I would like to discuss renaming “Closed Tape Language” (CTL) and “Closed Position Set” (CPS) deciders. In the last month or so CTL and CPS have been super-hot in bbchallenge, I’m very excited to see all the new innovation and results, but find myself wishing we had better names.

Why don’t I like the existing names:

  1. “Closed Tape Language” and “Closed Position Set” are literally synonyms. Tape & Position are both used to mean TM Configuration (tape + TM head state and pos). Language & Set both mean collections of such configurations. The main difference between these two is not present in the name at all (Regular Language vs. Markov/ngram Language).
  2. Because they are long, they are often shortened to CTL and CPS, but these are very opaque and I imagine scare off people who don’t know what they are.
  3. There is actually a huge variation in so-called CTL deciders. From the simple hard-coded Regex w/ macro machine search I first posted about to @UncombedCoconut’s DFA and Push-Down Automata based miracle! Likewise there is a bit of variation in CPS as well especially with @Nathan-Fenner’s floating ngram version.

For all of these reasons, I think it would be helpful to do a rename. My hope is that if we can get all stakeholders here bought in, it will be a smooth transition (instead of if I just unilaterally decided to change my names and then everyone gets confused and annoyed, heh :P). My criteria for a good name are:

  1. Literal reading of the name tells us more about how the decider works.
  2. Name is short enough that it is commonly written out fully instead of made into an acronym.
  3. Perhaps the name could somehow help to tie together the variety of approaches or allows for specifying more detail about different approaches.

Off the top of my head, here are some names I like:

  • CTL → Regex Closure, Regular Closure, Regex Closed Set
  • CPS → Markov Closure, Graph Closure, N-gram Closure, Markov Closed Set

My feeling here is that these are all Closure/Closed Set based approaches, but by putting that part of the name at the end, it allows people to shorten it to Regex or Markov deciders which are the real notable differences.

I like Regex vs. Regular b/c … well Regular sounds super-generic to anyone who doesn’t know the jargon. I like Markov and Graph about equally the same, these come from the idea that instead of using Regex / Regular Language to model Tape, CPS uses a Graph-based continuation language that also seems like a Markov Chain. I like Markov slightly more because it feels very unique and unlikely to collide with a future decider(?)

What do y’all think? I’d love to hear from as many people involved in these filters as possible. Maybe we can start with 2 questions:

  1. Are you for or against renaming?
  2. If we rename, what names do you propose?

Then, if we get enough support for renaming, we can vote on the specific names.

Sorry for teasing, but I might already be updating my pet decider’s name (to a horrible pun plus detailed 1-2 page writeup of the what and why, if the next experiment goes well, otherwise something straightforward).

Generally speaking, it feels like the “real” problem is a terminology overload, between abstract concepts / proof techniques and decider implementations.
“Closed tape langauge” is a pretty good term for a formal language closed under TM steps! It’s a questionable name for a decider. When the decider is under active development, though, it’s a helpful placeholder.

Anyway, I’ll come back once I’m surer of exactly what I’m doing.
In the meantime, if brainstorming synonyms for CTL, maybe “covering” and/or “grammar” in the name.

There was a bit of discussion on Discord: Discord in which @savask described their disapproval of renaming. I will attempt to summarize their complaints as:

  1. We shouldn’t renaming things. That’s confusing. bbchallenge has already renamed too many things (bouncers, translated cyclers, etc.) which is just confusing to anyone not familiar with our specific project.
  2. We should respect the original names from the creators (skelet & Marxen) who coined these names.

One thing this makes me think of is that we could keep CTL/CPS as general names for this entire class of decider (ones that involve defining a superset of TM configs, closed under TM step, containing start config, but not containing halt config).

Then individual deciders could have more specific names. Like Regex CTL or some fancy pun name that @UncombedCoconut comes up with (I’m sure it will be unique!).

I’m proposing the name “reducible to finite state machine” for the family of deciders that I, djmati1111, and mateon1 have been posting to the closed-tape-language Discord channel.
This is a long name, but I think it’s the thing to write after “Decided (Non-Halt)” on the machine pages.

1 Like