Grammar and Enumerator for Decision and Halting Problem

in theoretical computer science I learned for every recursive enumerable language there would be an enumerator and a grammar. So since decision problem and halting problem are recursively enumerable, I was wondering what kind of grammar and enumerator could this be.

Ok since there exists a sequence of M_i I would start with M_1 and find all words for this TM and give them out. So if I have any TM is there a possibility to give all words out which are accepted by this TM? I probably would have to give all w_i to it and compute the first i words for i steps, then i+1 words for i+1 steps and so on. Or maybe something like DFS on all configurations. This really sounds like that only for one TM this could go on forever. So I would need to start the second TM for the same period of time after a while… Seems as if something similiar could work for Halting Problem. Do you have any more refined thoughts on this one?

But the Problem with the Grammar seems to be more challenging. How could I possibly come up with a Grammar for these problems? You would have to generate code(M_i) in such a way that its always in the language. So you would have to simulate the TM through grammmar on different words. It somewhat comes down to the question whether a TM accepts anything or holds on any entry. Or is it more "okay we proofed, so there must be some kind of grammar even though I can´t comeup with an idea for it".



How would I add up enumerator values such that any combination provides a unique number?

Backstory (You can skip)

I am writing a pronunciation library for irregular words. Take something like the following:

T1E1s    // tee one E one es | tee one E ones 1994-1995// 1994 (minus|dash|to|) 1995  19-mm    // 19 dash mmmmmmmmmmmmmm | 19 dash millimeter | 19 dash em em 4x4      // 4 ex 4 | 4 times 4 | 4 by 4 

What you see for every word, are the different possible interpretations. Tackling the issue is pretty taxing, but is honestly pretty straight forward. Basically, I parse the word into various types denoted by this enumerator, as such:

    enum StringType     { // Heirarchical         Acronymn                  , // "mm","мм"         Measurement               , // pound          Number                    , // 0-9          Character_Times           , // x × X         Character_Dash            , // -         Character_ForwardSlash    , // /         Character_Latin_Lower     , // a         Character_Latin_Upper     , // A         Character_Latin_Plural    , // s          Consanants_Latin_Proper   , // Fff         Consanants_Latin_Lower    , // fff         Consanants_Latin_Mixed    , // fFF         Consanants_Latin_Upper    , // FFF          Word_Latin_Proper         , // Foo         Word_Latin_Lower          , // foo         Word_Latin_Mixed          , // fOO         Word_Latin_Upper          , // FOO          Consanants_Cyrillic_Proper, // Fff         Consanants_Cyrillic_Lower , // fff         Consanants_Cyrillic_Mixed , // fFF         Consanants_Cyrillic_Upper , // FFF          Word_Cyrillic_Proper      , // Фоо         Word_Cyrillic_Lower       , // фоо         Word_Cyrillic_Mixed       , // фОО         Word_Cyrillic_Upper       , // ФОО     };  

thus, a word like 19-mm is parsed like so:

Halt: void mapper(QString) /home/akiva/Programming/Blanket/main.cpp:206 [QStringList] sp.parsedStrings() QStringList:: QStringList 0   : 19 1   : - 2   : mm QList<QCD::StringType>:: QList<QCD::StringType> 0   : Number 1   : Character_Dash 2   : Acronymn QString:: "19-mm" 

The taxing part is where I have to tackle each case with its own implementation, and by the end of this, I imagine I will have something like 500 different combinations I will need to program functions for. This is where things get messy, because I do not want this:

     if (string.types() == QList<StringType> t() << StringType::Number << StringType::Dash << StringType::Acronymn) { Number_Dash_Acronymn(); } else if (string.types() == QList<StringType> t() << StringType::Number << StringType::Dash << StringType::Number) { Number_Dash_Number(); } else if (string.types() == QList<StringType> t() << StringType::Number << StringType::Times << StringType::Number) { Number_Times_Number(); } // + 500 additional if else statements 

500 if else statements is not acceptable. An enumerator with 500 different values is also disgusting for all the reasons that you can imagine. I had floated the idea of using bitflags, but that ended up being far too limited (32 bits = only 32 parameters). Thus I think I have the best possible approach detailed below:

Actual Issue:

I want something like this:

switch (stringTypes)     case Number + Dash + Word_Latin_Lower: {         /* code */         break; } case Word_Latin_Lower + Dash + Number: {          /* code */         break; } default:         ct_Error("Failed to account for the combination: ", stringTypes);         break; } 

The obvious issue being that the first two cases have the same value, despite being in a different order. Regardless, if the code was functional, it would be foldable, readable, efficient, and easy to sort. Not to mention, I won’t have to touch my header file to add new enumerators or functions, thus drastically helping my compile times.

Thus, how should I give combined enumerators guaranteed unique values, so much so that the order it is given also guarantee a unique value, while still maintaining readability?