MU puzzle (opens in new tab)

For example, https://arxiv.org/abs/1104.2804

But if you're at work and your boss says "I have a puzzle I need you to solve: Given these constraints, find an answer" You need to be able to say "Here is my solution" or "No solution is possible, and here is why."

Or take something simpler: a 500 piece "Puzzle" only there's a manufacturing defect in all copies: one piece is miss shaped. The puzzle can't be completed; there is no "solution". It's still a puzzle.

So no, you don't get to "unfair!" your way out of the MU Puzzle through narrow semantic definitions, especially given the, well, grammatical nature of language, because then you have gone and missed the entire point.

It should be noted that if the teacher had had the foresight (often a big ask) to simply tell you they suspected there was no solution, which is often the case with such problems presented as they are, and that you should attempt a proof alone, you would likely not feel so bad about not spotting it immediately.

But that was precisely the point. That given a system with a set of rules, the space of all possible problems may be larger than the space of all solutions, i.e., not all problems have a solution.

To say it's useful to be able to determine if a problem is solvable is a vast understatement.

    #!/usr/bin/perl -w
    use strict; 


    my %tried = (); 

    main(); 

    sub main { 

        my @rules = (
                     \&rule_one, 
                     \&rule_two,
                     \&rule_three, 
                     \&rule_four,
                    ); 

        my $axiom = 'MI';
    
        my @path; 
        my @tries; 

         solve($axiom, \@rules); 
    }


    sub solve { 

        my @app; 


        my ($axiom, $rules) = @_; 
        my $i = 0; 

        foreach(@$rules){ 
            my $tmp =  $_->($axiom);
            push(@app, $tmp) if $tmp;
        }

        foreach(@app){ 

            next if $tried{$_};
            next unless (length($_) < 1000); 
    
            print $_ . "\n";
    
            $tried{$_} = 1; 
    
            if($_ eq 'MU'){ 
                print "YES!\n\n\n"; 
                exit;
            }
            solve($_, $rules); 
        }

    }



    sub rule_one { 
        # If any string ends in I, you can append U

        my $str = shift; 

        if ($str =~ m/I$/){ 
            return $str . 'U';     
        }else{ 
            return undef; 
        }
    }




    sub rule_two { 
        # If any string begins with M, 
        # you can duplicate the string after M,    

        my $str = shift; 

        if($str =~ /^M/){ 
            return 'M' . substr($str, 1) . substr($str, 1); 
        }else{ 
            return undef;
        }
    }




    sub rule_three { 
        # If any string contains III, 
        # you can replace the III with U

        my $str = shift; 
        if($str =~ /III/){ 
            $str =~ s/III/U/g;
            return $str; 
        }else{ 
            return undef;     
        }
    }




    sub rule_four { 
        #If any string contains UU, 
        # you can delete the UU

        my $str = shift; 

        if($str =~ /UU/){ 
            $str =~ s/UU//g; 
            return $str;
        }else{ 
            return undef; 
        }
    }

The GEB book doesn't have all the details, but it uses the ASCII representations (actually base 20 but whatever). With the ASCII representation the theorem feels obvious.

https://en.m.wikipedia.org/wiki/Squaring_the_circle