Skip to content

A small program reversing the Gödel numbering function for turing machines taught in my theoretical computer science class

License

Notifications You must be signed in to change notification settings

nils-matthaei/ungoedel

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

16 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

ungoedel

It happens all the time, you leave your Turing machine lying around unattended for only a couple of minutes and immediately a free roamig theoretical computer scientist comes by and gödelises your Turing machine, rendering it completely unuseable.

Luckily, now there is a solution to this extremely common problem: ungoedel (or in the correct german spelling ungödel) is a program, written entirely in Rust, to ungödelise any* Turing machine and returns it in the form of a Turing table. Check out the wiki to see how it works!

*as long as it's tape alphabet is {0, 1, □}.

How does it work?

It's really quite simple:

Just run the code with a binary coded Gödel number as the argument. And just like that the associated turing table will be printed out.

$ ungödel 100111011011010000101101011101101000010100001010000101000010

   |     0      |     1      |     □      |
---|------------|------------|------------|
Z0 | (Z0, 1, R) | (Z1, 0, N) | (   --   ) |
Z1 | (Z1, 0, L) | (Z2, 0, N) | (   --   ) |
Z2 | (   --   ) | (   --   ) | (   --   ) |

About

A small program reversing the Gödel numbering function for turing machines taught in my theoretical computer science class

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages