Click here to Skip to main content
13,251,556 members (89,173 online)
Click here to Skip to main content
Add your own
alternative version

Tagged as


4 bookmarked
Posted 6 Aug 2010

Implementing state machine transitions with Gödel encoded switch statements

, 6 Aug 2010
Rate this:
Please Sign up or sign in to vote.
Uses Gödel numbering constants from program state for use with C++ switch statements
Title:       Implementing state machine transitions with Gödel encoded switch statements
Author:      William Bourke
Member ID:   5803131
Language:    C, C++
Platform:    Platforms Independent
Technology:  C++, State machines
Level:       Intermediate
Description: C++ technique for implementing fast, maintainable state machines with Gödel numbering and switch statements
Section      General Programming
SubSection   Algorithms and Recipes
License:     Public domain


A common problem with implementing state machines is how to represent a table of branches in a form that can be executed efficiently at run time, but that is clear enough to be maintainable later. Non-trivial state machines can have dozens of states, with several state variables representing each state, and many branches from each state.

    enum { Large, Small } Size;
    enum { Red, Green, Blue } Color;
    if (Size == Large)
        if (Color == Green)
            LargeGreen ();
            LargeRedOrBlue ();
        if (Color != Blue)
            SmallRedOrGreen ();
            SmallBlue ();

The example shows a typical implementation, using nested "if" statements. Even with only a few possible values for the two state variables, the transition logic is becoming hard to parse.

A technique that satisfies the two objectives of human clarity and machine efficiency is to use Gödel numbering to represent state transitions in switch statements.

Gödel Numbering

Kurt Gödel was a mathematician who lived in the 20th century. One of his contributions to the field was a method of mapping strings of tokens to a unique natural number.

Gödel's original prime factorization model assigned a number to each symbol in the string, and a prime number to every position in the string. The Gödel number is then calculated as:

p0So * p1S1 * ... * pnSn

where pi is the positional prime and Si is number assigned to the symbol at that position.

For example, the string BCA could be encoded by assigning each letter a number, A = 1, B = 2, C = 3. Assign the primes 2, 3 and 5 to the 3 possible positions in the string - more primes are needed for a longer string. The Gödel number is then:

22 * 33 * 51 = 4 * 9 * 5 = 180

The original string of symbols can be recovered by factoring the Gödel number into primes and counting the number of each prime.

More generally, Gödel numbering refers to any mapping of strings of symbols to natural numbers, so the natural numbers can be processed in place of the strings of symbols.

C++ Application

The technique discussed here uses a macro to Gödel encode a string of state variables to a constant, then using the constant in the "case" section of a switch statement. Instead of exponentiation and multiplication to encode strings, as in Gödel's original model, this technique uses multiplication and addition. First define a macro that computes the following function

((s0 * p0 + s1) * p1 + .. + Sn-1) * Pn + Sn

where pi is the position multiplier. The position multiplier Pi is selected to be larger than the largest symbol Si-1. Note, there is no last position multiplier. Recoding the size/color example above.

    enum { Large, Small } Size;
    enum { Red, Green, Blue } Color;
    #define SizeColor(size, color) (size * 3 + color)
    switch (SizeColor (Size, Color)) {
        case SizeColor (Large, Green):   LargeGreen (); break;
        case SizeColor (Large, Red):
        case SizeColor (Large, Blue):    LargeRedOrBlue (); break;
        case SizeColor (Small, Green):  
        case SizeColor (Small, Red):     SmallRedOrGreen (); break;
        case SizeColor (Small, Blue):    SmallBlue (); break;
    #undef SizeColor

The "#undef" on the last line helps reduce name-space clutter.


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

William Bourke
Software Developer (Senior)
United States United States
Bill works at, a managed file transfer start-up in Campbell, California.
In his spare time, Bill enjoys mountain biking and designing algorithms.

You may also be interested in...

Comments and Discussions

GeneralReason for my vote of 5 Nice and practical idea Pin
Grof6-Sep-10 2:12
memberGrof6-Sep-10 2:12 
GeneralReason for my vote of 5 Very interesting and useful tip! Pin
Nuri Ismail17-Aug-10 4:25
memberNuri Ismail17-Aug-10 4:25 
GeneralNice tip Pin
ThatsAlok9-Aug-10 20:55
memberThatsAlok9-Aug-10 20:55 
GeneralReason for my vote of 5 A simple but useful tip. Pin
José Vitor8-Aug-10 4:40
memberJosé Vitor8-Aug-10 4:40 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.171114.1 | Last Updated 6 Aug 2010
Article Copyright 2010 by William Bourke
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid