flat assembler
Message board for the users of flat assembler.

Index > Macroinstructions > [fasmg] graphing state machines

Author
Thread Post new topic Reply to topic
bitRAKE



Joined: 21 Jul 2003
Posts: 3970
Location: vpcmipstrm
bitRAKE 10 May 2023, 14:26
Code:
; state machine to DOT graph file format

; REFERENCES:
;       https://oeis.org/A060843
;       https://bbchallenge.org
;       https://turingmachine.io

match =PARAMS,PARAMS
        display 10,'expected usage examples:',10,\
                9,      'fasmg sm_dot.g -i "PARAMS equ 1RB0LD_1RC0RF_1LC1LA_0LE1RH_1LF0RB_0RC0RE"',10,\
                9,      'dot -Tpng sm_dot.dot -o "BB(6,2).png"',10
        err 'PARAMS missing'
else match Q=,S=,I,PARAMS
        file_gather <'states = ',`Q,' symbols = ',`S,' index = ',`I>,\
                <IndexForm Q,S,I>
else match any,PARAMS
        file_gather <`any>, <CompactLinearForm `any>
end match

macro file_gather note*, body*
        format binary as 'dot'
        db '###',10
        db '### generated file',10
        db '### ',note,10
        db '###',10
        db 'digraph statemachine {',10
        db '    rankdir=LR;',10
        db '    node [shape = circle fixedsize=true fillcolor=lightgray style=filled];',10
        body
        db '    Halt [shape = doublecircle];',10
        db '}',10
end macro

macro IndexForm states*,symbols*,index*
        local reduce,state,value,target,write,direction,attributes
        reduce = index

        struc StateName I*
                local result,chars,i
                i = I mod (states+1)
                if i = states
                        . = 'Halt'
                else
                        if I eqtype 0
                        else
                                I = I / states
                        end if
                        result = 0
                        chars = 0
                        while 1
                                result = (result shl 8)+'A'+(i mod 26)
                                chars = chars + 1
                                i = i/26
                                if i = 0
                                        break
                                end if
                        end while
                        . = string (result bswap chars)
                end if
        end struc

        struc SymbolName I*
                repeat 1, n:I mod symbols
                        . = `n
                end repeat
                if I eqtype 0
                else
                        I = I / symbols
                end if
        end struc

        repeat states
                state StateName %-1
                ; NOTE: this ordering creates a unique decode of index:
                repeat symbols
                        value SymbolName %-1

                        target StateName reduce
                        write SymbolName reduce
                        if reduce and 1
                                direction = 'L'
                                attributes reequ ''
                        else
                                direction = 'R'
                                attributes reequ ' color = "red"'
                        end if
                        reduce = reduce shr 1
                        if symbols = 2 ; decorate edges based on binary tape writing
                                if write = '0'
                                        attributes reequ attributes,' arrowhead = onormal'
                                end if
                        end if

                        db '    ',state,' -> ',target,\
                                ' [ label = "',value,'; ',write,', ',direction,'"',\
                                attributes,' ];',10
                end repeat ; symbols
        end repeat ; states
end macro

; WARNING: assume valid input: compact linearized transition matrix
; see: https://www.sligocki.com/2022/10/09/standard-tm-format.html

macro CompactLinearForm matrix*
        local reduce,symbols,symbol,states
        states = 1
        symbol = 0
        reduce = 0+matrix
        ; precompute so halt state is known
        while reduce > 0
                if reduce and 0xFF = '_'
                        reduce = reduce shr 8
                        ; next row of transition table
                        if ~ definite symbols
                                symbols := symbol
                        else if symbols <> symbol
                                err 'invalid compact linearized form'
                        end if
                        states = states + 1
                        symbol = 0
                else
                        transitions =: reduce and 0xFF_FF_FF
                        reduce = reduce shr 24
                        symbol = symbol + 1
                end if
        end while
        state = 'A'
        symbol = 0
        irpv transition, transitions
                if transition = '---' ; undefined transition
                else
                        target = transition shr 16
                        value = symbol + '0'
                        write = 0xFF and transition
                        direction = 0xFF and (transition shr 8)
                        if target > states + 'A' - 1
                                target = 'Halt'
                        end if
                        if direction = 'R'
                                attributes reequ ' color = "red"'
                        else
                                attributes reequ ''
                        end if
                        if write = '0'
                                attributes reequ attributes,' arrowhead = onormal'
                        end if
                        db '    ',state,' -> ',target,\
                                ' [ label = "',value,'; ',write,', ',direction,'"',\
                                attributes,' ];',10
                end if
                symbol = symbol + 1
                if symbol = symbols
                        state = state + 1
                        symbol = 0
                end if
        end irpv
end macro    
Some interesting machines ...

2022 May 30, Pavel Kropitz, BB(6,2) t15,
1RB0LD_1RC0RF_1LC1LA_0LE1RH_1LF0RB_0RC0RE

2023 Apr 29, Pavel Kropitz, BB(2,6) ~t90,
1RB3LA4LB0RB1RA3LA_2LA2RA4LA1RA5RB1RZ

15-state 2-symbol Turing machine M(15,2) that halts if and only if Erdős’ conjecture is false.
0RB1RC_1RD0RA_0RA1LI_0RE0RF_0RD0LG_1RA1RA_1RE1RM_0LI1LJ_0LK1LH_0LH1LN_0LL1LM_0LK1LK_0LK1RF_1LO0RM_0RZ0RG

Use https://graphviz.org/ to create pretty pictures ...


Description:
Filesize: 39.82 KB
Viewed: 1049 Time(s)

BB(6,2).png



_________________
¯\(°_o)/¯ “languages are not safe - uses can be” Bjarne Stroustrup
Post 10 May 2023, 14:26
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 3970
Location: vpcmipstrm
bitRAKE 12 May 2023, 05:43
It's easy to see from the diagram that the B-F-E loop can consume 1's going right and replace them with zeros. This loop also has an internal branch that allows single zero's to be consumed in a string of 1's. Oddly, state C consumes 0's going left, replacing them with 1's - this is kept from being problematic on a empty tape.

The halt condition requires three 1's on the tape going left from state C.
Post 12 May 2023, 05:43
View user's profile Send private message Visit poster's website Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2024, Tomasz Grysztar. Also on GitHub, YouTube.

Website powered by rwasa.