Re: Solution to QOTW #23 in language of QOTW #24

Daniel Martin <martin-+m399P62/[email protected]>:
> As a demonstration that turing machines can indeed do all the things
> more convenient computer systems can, I attach a solution to the
> "parens" problem of a few weeks ago in the turing machine language
> of QOTW #24.

I was kind of hoping someone would post an interpreter.  But maybe
that's too insane.

> Unfortunately, the restriction on the output format means that it
> can't quite output like QOTW #23 specified.  However, doing this
> should get you the right output (assuming that your turing machine
> interpreter is called tm.pl, and that you have a "tr" program that
> understands backslashed escapes):

I changed the definition of my interpreter so that (, ), [, and ] are
valid tape symbols, and also that a r/w head motion of the form "x!"
means that the interpreter should print the tape contents just before
moving the head.  If you don't like that, it should be easy to alter
the TM instructions so that section D copies the new parenthesis
string while scanning it.

This is a fairly straightforward translation of my
parenthesis-generating program.  It is substantially simpler than
Daniel Martin's, although not so featureful; I think it has fewer
states and fewer total instructions, even if you don't count the
argument-processing and copying parts of Martin's code.

The input should be a string of the form '()()()()()'.  If you don't
like that, it should be easy to paste in the chunk of Martin's code
that transforms a decimal numeral into a string of that form.

The execution of 

        perl tm.pl parens.pl '()()()()'

generates:

        ()()()()
        ()()(())
        ()(())()
        ()(()())
        ()((()))
        (())()()
        (())(())
        (()())()
        (()()())
        (()(()))
        ((()))()
        ((())())
        ((()()))
        (((())))

which I believe is correct, and also in lexicographic order.


# Initialization: Scan to the right-hand end
init ( init ( R
init ) init ) R
init _ A_scan_1 _ L!            # Print the tape contents at this point

# Section A
# Locate innermost changeable pair )( and replace with []
# If there isn't one, then we have ((((())))), so halt.

A_scan_1 ) A_scan_1 ) L
A_scan_1 ( A_scan_2 ( L

A_scan_2 ( A_scan_2 ( L
A_scan_2 ) A_change [ R
A_scan_2 _ HALT     _ R         # HALT instruction

A_change ( B_scan_L ] L

# Section B
# Mark outer pairs that surround inner pair

B_scan_L [ B_scan_L [ L
B_scan_L ] B_scan_L ] L
B_scan_L ) B_scan_L ) L
B_scan_L ( B_scan_R [ R
B_scan_L _ C_scan_R _ R

B_scan_R [ B_scan_R [ R
B_scan_R ] B_scan_R ] R
B_scan_R ) B_scan_L ] L
B_scan_R ( B_scan_L ] L  # Note that this changes ( to ]

# Section C
# Reset rightmost marks
# In the 'counting' analogy, this is like resetting the 999 part of
# 345999 to 000.

C_scan_R [ C_scan_R [ R
C_scan_R ] C_scan_R ] R
C_scan_R ( C_close [ R
C_scan_R ) C_close [ R
C_scan_R _ D_fix _ L

C_close ( C_open ] R
C_close ) C_open ] R

C_open ( C_close [ R
C_open ) C_close [ R
C_open _ D_fix _ L

# Section D
# Replace [] with () and start over

D_fix ( D_fix ( L
D_fix ) D_fix ) L
D_fix [ D_fix ( L
D_fix ] D_fix ) L
D_fix _ init _ R