flat assembler
Message board for the users of flat assembler.

Index > Main > Busy Beaver

Author
Thread Post new topic Reply to topic
bitRAKE



Joined: 21 Jul 2003
Posts: 4060
Location: vpcmpistri
bitRAKE 07 Mar 2008, 06:17
Code:
TAPE_BYTES     = 1024*1024
MAX_POSITION   = TAPE_BYTES*8
START_POSITION = MAX_POSITION/2
START_STATE    = 0

BusyBeaver:
        pushad
        mov edi,TAPE
        mov eax,START_POSITION
        mov edx,START_STATE
        jmp .go

    align 16 ;+8

.clip:  and eax,MAX_POSITION-1
.next:  mov edx,[.t+edx+ecx*8+8]  ; load next state
.go:    bt [edi],eax              ; read tape
        sbb ecx,ecx               ;
        jmp [.t+edx+ecx*8+12]     ; select action

.LEFT:  dec eax
        jmp .clip

.RIGHT: inc eax
        jmp .clip

.SET:   bts [edi],eax
        jmp .next

.CLEAR: btr [edi],eax
        jmp .next


.HALT:  ; examine tape

        popad
        retn


; -1 state is the halting state - allowing
; varied actions prior to halt.

;---------------------------------------------;
;       tape 1         |         tape 0       ;
;  new state, action   |   new state, action  ;
;---------------------------------------------;
    dd -1*16,.HALT,            -1*16,.HALT    ;
.t  dd -1*16,.SET,              4*16,.SET     ;
    dd  6*16,.RIGHT,            3*16,.CLEAR   ;
    dd  5*16,.LEFT,             3*16,.SET     ;
    dd  3*16,.RIGHT,            2*16,.SET     ;
    dd  2*16,.LEFT,             1*16,.RIGHT   ;
    dd  6*16,.LEFT,             0*16,.CLEAR   ;
    dd  4*16,.CLEAR,            0*16,.RIGHT   ;
;---------------------------------------------;


TAPE rb TAPE_BYTES    
Some rather convienient code for the Busy Beaver function. Although I choose constants, the arguments could easily be pushed on the stack. MAX_POSITION needs to be a power of two - just to simplify wrapping of the tape index.

Some related threads:

http://board.flatassembler.net/topic.php?t=5735 Finite State Machines
http://board.flatassembler.net/topic.php?t=8289 L-Systems

(no, I'm not going to code a GUI)

_________________
¯\(°_o)/¯ “languages are not safe - uses can be” Bjarne Stroustrup
Post 07 Mar 2008, 06:17
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 20415
Location: In your JS exploiting you and your system
revolution 07 Mar 2008, 06:29
bitRAKE wrote:
MAX_POSITION needs to be a power of two - just to simplify wrapping of the tape index.
I thought that tape was meant to be infinite length?

You can add this:
Code:
if MAX_POSITION and (MAX_POSITION-1)
  rb -1 ; MAX_POSITION must be a power of 2
end if    


bitRAKE wrote:
(no, I'm not going to code a GUI)
How about coding a GUI? Twisted Evil
Post 07 Mar 2008, 06:29
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 4060
Location: vpcmpistri
bitRAKE 07 Mar 2008, 06:48
unfortunately, we have a finite bit index and limited memory - so I choose to wrap the tape around. of course, I contemplated the idea of halting when the tape is exceeded, but the choice seemed too restrictive. some machines might overflow, others might underflow, and even some that do both.

much of the documentation uses machines that move and/or print every step (5-tuple variant) - this is the easier 4-tuple version. also, it only supports two symbol machines, but others could be converted to a two symbol version with more states from either the 5-tuple and/or multi-symbol description.

revolution wrote:
bitRAKE wrote:
(no, I'm not going to code a GUI)
How about coding a GUI? Twisted Evil
FASMW is working fine here.

_________________
¯\(°_o)/¯ “languages are not safe - uses can be” Bjarne Stroustrup
Post 07 Mar 2008, 06:48
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.