Busy Beaver

Index > Main > Busy Beaver

Author

Thread

bitRAKE

Joined: 21 Jul 2003
Posts: 4061
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

07 Mar 2008, 06:17

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20430
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

07 Mar 2008, 06:29

bitRAKE

Joined: 21 Jul 2003
Posts: 4061
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?

FASMW is working fine here.

_________________
¯\(°_o)/¯ “languages are not safe - uses can be” Bjarne Stroustrup

07 Mar 2008, 06:48

< 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