What are Formal Systems?

Introduced here: the MIU puzzle as an example of a formal system. A formal system is composed of axioms, to which rules of inference are applied to produce theorems to which the rules can be applied again. Confused? Try to MIU puzzle yourself - [...]

An episode of the TOKTalk.net podcast, hosted by ok, titled "What are Formal Systems?" was published on January 9, 2008.

January 9, 2008 · TOKTalk.net

Summary

http://www.toktalk.net/wordpress/wp-content/uploads/MP3/010-toktalk-formal-systems.mp3 Introduced here: the MIU puzzle as an example of a formal system. A formal system is composed of axioms, to which rules of inference are applied to produce theorems to which the rules can be applied again. Confused? Try to MIU puzzle yourself – it’s fun! The MU Puzzle is an example of a formal system. The objective of the MU Puzzle is to try to reach the string MU starting from MI, using only these four rules: Rule 1: xI ? xIU. If there is an I at the end of the string of letters, then you can add a U. For example if your string is MI then you can change it into MIU. You can only add a U if the last letter is an I. Rule 2: Mx ? Mxx. You can double any string that follows the M. So if your string is MIU then you can double the IU after the M. You will then get MIUIU. We have doubled the IU. Rule 3: xIIIy ? xUy. You can replace three I in a row with one U. MUIII can be changed in to MUU. It is also possible to replace the three III if they occur in the middle somewhere. MUIIIU can also be changed to MUUU. Rule 4: xUUy ? xy. You can cancel and remove any two U that occur in a row. MUUU can be changed to MU. Is it possible to reach the string MU with these four rules? If yes, then what are the steps involved? A formal system needs axioms and rules of inference. These rules are applied to the axioms and theorems are derived. It is possible to make new theorems by applying the rules to existing theorems. The first steps in solving the the MU puzzle could be: Axiom: MI Theorem 1, using rule 2: MII Theorem 2, using rule 2: MIIII Theorem 3, using rule 3: MUI Theorem 4, using rule 1: MUIU Theorem 5, using rule 2: MUIUUIU Theorem 6, suing rule 4: MUIIU etc. until you reach MU, if possible at all. Transcript: For this edition of TOK talk, you need something to write with, a pen and paper. Why? Because I’m going to show you a little puzzle for you to try out. Actually we are going through the puzzle together, but it’s difficult for you to follow by just listening to it – you need to be able to see it as well. It’s called the MU puzzle. I want to use this puzzle as an example of a formal system. I think we’re gonna do the puzzle first and I’ll explain the theory behind formal systems later. The puzzle starts out like this: Write the letters MI at the top left of the page. This is our starting string of letters. And at the bottom left of the page I want you to write the letters MU. The goal of the puzzle is to change the string MI into MU. Of course you can not just cross out the I and replace it with a U. This is not allowed. There are four rules that you can use and I am going to tell you these four rules now. I think it is a good idea to write these rules down as well. Otherwise it’s really getting kind of difficult to remember them. So, we could use the right side of the paper for writing down these rules. Here are the four rules: Rule 1: If there is an I at the end of the string of letters, then you can add a U. For example if your string is MI then you can change it into MIU. You can only add a U if the last letter is an I. Rule 2: You can double any string that follows the M. So if your string is MIU then you can double the IU after the M. You will then get MIUIU. We have doubled the IU. Rule 3: You can replace three I in a row with one U. MUIII can be changed in to MUU. It is also possible to replace the three III if they occur in the middle somewhere. MUIIIU can also be changed to MUUU. Rule 4: You can cancel and remove any two U that occur in a row. MUUU can be changed to MU. These are the only four rules that you can use. You do not have to use all of these rules. You can use the rules in any order that you want and of course you can use one rule as often as you want. In summary the four rules are: You can add a U if there is an I at the end. You can double anything after the M You can replace III with [...]

Episode Description