A Turing machine in WEIDU

[DavidW]

A somewhat tongue-in-cheek response to the discussion of WEIDU on this thread:

A WEIDU implementation of a Turing machine, using the conventions here:

Spoiler

DEFINE_ACTION_FUNCTION turing_machine
    INT_VAR display_steps=0
    STR_VAR initial_tape=""
            machine=""
BEGIN
    // initialise array, just in case
    ACTION_PHP_EACH turing_tape AS k=>v BEGIN
        OUTER_SET $turing_tape("%k%")=0
    END
    // read the initial_tape into the turing_tape array
    OUTER_PATCH "%initial_tape%" BEGIN
        FOR (ind=0;ind<BUFFER_LENGTH;++ind) BEGIN
            READ_ASCII ind val (1)
            SET $turing_tape("%ind%")=val
        END
    END
    // put the pointer at zero
    OUTER_SET pointer=0
    // initialise the machine
    OUTER_SPRINT state "A"
    // start the counter
    OUTER_SET counter=0
    OUTER_WHILE !("%state%" STRING_EQUAL "HALT") BEGIN
        // increment the counter
        OUTER_SET counter+=1
        // get the current state of the tape (0=blank)
        ACTION_IF VARIABLE_IS_SET $turing_tape("%pointer%") BEGIN
            OUTER_SET tape=$turing_tape("%pointer%")
        END ELSE BEGIN
            OUTER_SET tape=0
        END
        // run the machine
        LAF "%machine%" INT_VAR tape STR_VAR state RET state mark_tape move END
        // mark the tape
        OUTER_SET $turing_tape("%pointer%")=mark_tape 
        // move the pointer
        ACTION_MATCH "%move%" WITH
        L BEGIN
            OUTER_SET pointer +=1
        END
        R BEGIN
            OUTER_SET pointer -=1
        END
        DEFAULT
            FAIL "%move% is an illegal move output from Turing machine %machine%"
        END
        // display the tape and machine 
        ACTION_IF display_steps BEGIN
            OUTER_SPRINT display ""
            ACTION_SORT_ARRAY_INDICES turing_tape NUMERICALLY
            ACTION_PHP_EACH turing_tape AS ind=>data BEGIN
                OUTER_SPRINT display "%display%%data%"
            END
            PRINT "Step %counter%: Machine state: %state%; Tape state: %display%"
        END
    END
    PRINT "Turing machine %machine%, with input %initial_tape%, halted after %counter% steps"
END

You use it like this:

LAF turing_machine INT_VAR display_steps=1 STR_VAR machine=my_machine END

'my_machine' is an action function encoding the machine's lookup table. Here's an example:

Spoiler

DEFINE_ACTION_FUNCTION busy_beaver
    INT_VAR tape=0
    STR_VAR state=""  
    RET state
        mark_tape
        move
BEGIN
        ACTION_MATCH "%state%" WITH
        A BEGIN
            OUTER_SET mark_tape=1
            ACTION_IF tape=0 BEGIN
                OUTER_SPRINT state B
                OUTER_SPRINT move R
            END ELSE BEGIN
                OUTER_SPRINT state C
                OUTER_SPRINT move L            
            END
        END
        B BEGIN
            OUTER_SET mark_tape=1
            ACTION_IF tape=0 BEGIN
                OUTER_SPRINT state A
                OUTER_SPRINT move L
            END ELSE BEGIN
                OUTER_SPRINT state B
                OUTER_SPRINT move R    
            END        
        END
        C BEGIN
            OUTER_SET mark_tape=1
            ACTION_IF tape=0 BEGIN
                OUTER_SPRINT state B
                OUTER_SPRINT move L
            END ELSE BEGIN
                OUTER_SPRINT state HALT
                OUTER_SPRINT move R
            END                
        END
        DEFAULT
            FAIL "%state% is an illegal internal state for busy_beaver"
        END
END

 

[CamDawg]

Excellent, now we can start coding GemRB in WeiDU, and the circle is complete.

[Sam.]

I was wondering if it could be used to decipher encrypted 2DAs.

[DavidW]

Anyone is welcome to use this code in their mods, of course.

[Luke]

Neat indeed!

It's quite curious that your scientific background is not "Computer Science and Engineering" (contrary to what I originally though...)

Just to clarify: you depicted the so-called Single-Tape Turing Machine, right? In other words, there's a single tape for memory, input and output (namely the array  "turing_tape")...? If so, shouldn't "Tape state: %display%" be renamed to "Output tape: %display%"...? Is the word "state" associated to Output kinda misleading...?

[DavidW]

No, I don't think so, precisely because the tape isn't just an output: it's also input and working memory.

(Not that I put more than 5 seconds thought into what it should be called!)

[Luke]

3 hours ago, DavidW said:

No, I don't think so, precisely because the tape isn't just an output: it's also input and working memory.

Yeah, me dumb (I answered myself without noticing it, sigh...).

Better to leave the name as is...

[Luke]

@DavidW

So, to sum up: what did you mean by [WeiDU] is not just nominally Turing-complete...?

[DavidW]

Well, just being Turing-complete, by itself, isn't enough to make a programming language fit for a given purpose. Turing machines are Turing-complete, but I'm not planning to mod with them! My point was that WEIDU actually is a fairly powerful programming language, in which you can do most of the things you need for high-level programming.

The actual Turing machine implementation was a joke, mostly. (Obviously WEIDU is Turing complete - all you need for that is variables and basic control flow, and it obviously has those.) But the fact that I can do a fast smooth implementation of a Turing machine in a few dozen lines of WEIDU code and in twenty minutes of my time does provide a reasonable demonstration that WEIDU can easily be used for abstract programming and not just as a low-level interface into IE files.

[Luke]

20 hours ago, DavidW said:

Turing machines are Turing-complete, but I'm not planning to mod with them!

Yes, that is certainly true (even simple tasks like computing the successor of an integer coded in base 10 is cumbersome...)

20 hours ago, DavidW said:

But the fact that I can do a fast smooth implementation of a Turing machine in a few dozen lines of WEIDU code and in twenty minutes of my time does provide a reasonable demonstration that WEIDU can easily be used for abstract programming and not just as a low-level interface into IE files.

Are you talking about something like your SFO vs. COPY files pre-made with NearInfinity (or similar), right?

[DavidW]

Yes. (And various intermediates; e.g. my recode of Ascension is nothing like as abstracted as SCS but still does things at a fairly high level.)

[Axatax]

On a similar note, I think the WEIDU package for SCS calculates fluid dynamics during the installation.

[Sam.]

7 hours ago, Axatax said:

On a similar note, I think the WEIDU package for SCS calculates fluid dynamics during the installation.

If it's calculating true analytic (not numerical) solutions to the full no-assumptions Navier–Stokes equations, I'm very interested in that.  Moreover, if DavidW has solved the Navier–Stokes existence and smoothness problem, that would be pretty cool.

[Endarire]

I just noticed this on the recent forum posts and felt list.

1: How serious is this notion of making Turing Machines in Weidu?

2: How useful is it?

3: What else should someone generally unfamiliar with Turing Machines know about the situation?

Thankee!

[DavidW]

1. Not at all serious. It's a joke, really (I should probably have posted it in Noobermeet) with a 10% admixture of making a point about WEIDU's expressive capabilities.

2. Useless. (The comment about 'you can use this in your mods' is 100% a joke.)

3. It depends what you mean by 'should'. If you mean 'what should they know for modding purposes': nothing. But in case you're interested more broadly:

(i) One of the central principles of computer science is that computation is universal, which means that any reasonable model of computation can achieve anything that any other reasonable model of computation can achieve. Alan Turing was one of the pioneers of all this; the 'Turing machine' is his concrete model of computation. A standard way, at least in theory, to demonstrate that a computing device or computing language is 'universal' - that is, that it can do anything that any other model of computation can do - is to show that it can simulate a Turing machine. (The Wikipedia link I put upthread has more.)

(ii) The other thread I linked to was a good-natured discussion of the limitations or otherwise of WEIDU. Taylan was complaining about how limited WEIDU is as a computation language and mentioned in passing that it was only 'probably Turing-complete'. I don't think they were very serious - the requirements for Turing completeness are very minimal, WEIDU obviously satisfies them - but nominally my post is a demonstration of Turing completeness. Insofar as it had a more serious purpose, it was to demonstrate that you can use WEIDU to do complex abstract programming tasks very far removed from concrete mod applications like WRITE_ASCII 0x248 ~wtasight~, and so that it's a much more powerful tool than most people treat it as.

(iii)...But, like I say, it was mostly a joke. The code took me 20 minutes, it's not a labor of love or anything.