Talk:DigFill

Turing-completeness

I have a hunch it should be easy to compile the :()^! subset of Underload to this, so I think it is Turing-complete. --Ørjan 00:30, 14 July 2011 (UTC)

I think it is Turing-complete, but I'm not so sure Underload would be very easy. DigFill doesn't really have any string-handling facilities, and I don't think it would be very good at converting data to code, either. —Maharba 03:10, 14 July 2011 (UTC)

Underload has no string-handling facilities, either; it merely has composition (*), const (a), and apply (^). It does have the ability to print the code of a quotation in a certain way (S), but the subset Ørjan mentioned does not. —ehird 04:26, 14 July 2011 (UTC)

If we restrict the argument of () to valid programs, (and use only the :()^! subset) this seems fairly doable except for the : command. Any ideas on how to translate it? —Maharba 05:12, 14 July 2011 (UTC)

Yes. The thing about that subset is that it cannot move things around on the stack, so the copies created by : will always be consecutive. I just worked it out in some detail. My idea is representing an Underload stack somewhat like this:

(a)(a)(a)(b)(c)(c)  (with c at top)

becomes

inscriptions:        <c>   <b>   <a>   <underflow>
counting "grooves":   1  1  1  1  1  1  1  <cleanup of empty column>
                      1  0  1  0  1  0  1  <underflow>
                      1  0  0     1  0  1  <underflow>
                      0           1  0  0
                                  0

Then the commands become:

<:>         ~e@s$s
<(...)>     %n@w$w@w$w(%s%e~e<...>)n@s$s
<^>         $n#s%n~n
<!>         $n#s%e~e
<cleanup>   %w@n#n$e#w$e#w%s
<underflow> *

Also you can still add printing commands for specific strings.

--Ørjan 13:28, 14 July 2011 (UTC)

That seems to work. The program would have to begin with

(*)n(%w@n#n$e#w$e#w%s)e

of course. I don't see any error checking with ! and : though, which makes me a bit worried. On an empty stack, ! won't do anything, which is okay, but : will dig out below the underflow, which could lead to a hard-to-debug error later. That doesn't affect TCness, though, so this is great! Thanks! —Maharba 18:30, 14 July 2011 (UTC)

Um the rightmost column and its neighboring inscriptions are all initial state, including the three <underflow> spots, which are supposed to handle error detection for ^, !, and :, respectively. On an empty stack the miner should be on the bottom of those 1's. So the initial setup should be

(*)n(%w@n#n$e#w$e#w%s)e@s$s(*)e@s$s(*)e

For ^ and ! the <underflow>s (which may of course be embellished if you wish some more verbose error reporting) are placed such that they are hit during the natural progress of the commands, but for : I did not see how to avoid an explicit ~e test. --Ørjan 20:01, 14 July 2011 (UTC)

Oh, I see! That does work. I'll add this proof to the main article. —Maharba 22:08, 14 July 2011 (UTC)