flat assembler
Message board for the users of flat assembler.

flat assembler > Heap > Shortest Universal Turing Implementation Contest!

Goto page 1, 2, 3  Next
Author
Thread Post new topic Reply to topic
bitRAKE



Joined: 21 Jul 2003
Posts: 2796
Location: dank orb
http://www.mathrix.org/experimentalAIT/TuringMachine.html

Quote:
implementations written in languages other than ANSI/ISO C++98 language with GNU extensions might be taken into consideration for aside publication in a separate section (no other than ANSI/ISO C++ implementations can hold the winner record). If several implementations in a single language are submitted they will be grouped by size in the same fashion than for the ANSI/ISO C++ and rules for subcontests in those languages may be set up later.
...it's easy to get the program small, but the source code grows too fast in assembly. Could use a bunch of EQU's to shrink the code.

_________________
¯\(°_o)/¯ unlicense.org
Post 26 Dec 2008, 00:35
View user's profile Send private message Visit poster's website Reply with quote
Borsuc



Joined: 29 Dec 2005
Posts: 2468
Location: Bucharest, Romania
I don't get it, what's so hard to write an infinite amounts of 1s on the tape with a simple loop? (for the "busy beaver")

I know I'm missing something though.
Post 26 Dec 2008, 15:02
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 16792
Location: In your JS exploiting you and your system
Borsuc: I think you misunderstand "Universal Turing".

edit: Also "busy beaver" has a defined stop point. It doesn't just go on forever, that would be too easy.
Post 26 Dec 2008, 15:06
View user's profile Send private message Visit poster's website Reply with quote
Borsuc



Joined: 29 Dec 2005
Posts: 2468
Location: Bucharest, Romania
No matter how many times I read from wiki the definition I still don't get it.
I know what turing machine is, with states reading memory bits (from the tape) like a CPU does... I don't get what the contest or "busy beaver" is about.
Post 26 Dec 2008, 15:09
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 16792
Location: In your JS exploiting you and your system
Well, any idiot can write a program to write infinite 1's to a tape, I'm sure you'll agree here. But it is considerably more challenging to have a program that stops when a certain set of conditions are met. If the machine has only a few limited states, then making it stop after a very long time is a very hard challenge.
Post 26 Dec 2008, 15:16
View user's profile Send private message Visit poster's website Reply with quote
sleepsleep



Joined: 05 Oct 2006
Posts: 8419
Location: ˛                             ⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣Posts: 334455
if anyone could explain it in layman term, probably i can understand what is this all about....
Post 26 Dec 2008, 15:17
View user's profile Send private message Reply with quote
Borsuc



Joined: 29 Dec 2005
Posts: 2468
Location: Bucharest, Romania
Yes I know but you are not allowed to use counters (registers) or something else memory-related?

_________________
Previously known as The_Grey_Beast
Post 26 Dec 2008, 15:22
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 16792
Location: In your JS exploiting you and your system
The tape is your memory. You can set up any counters and registers you want onto it.
Post 26 Dec 2008, 15:27
View user's profile Send private message Visit poster's website Reply with quote
Borsuc



Joined: 29 Dec 2005
Posts: 2468
Location: Bucharest, Romania
Hmm I thought the tape was more of a hard disk, and the memory would be RAM, but the tape isn't random-access, so yeah I agree it could be hard.

_________________
Previously known as The_Grey_Beast
Post 26 Dec 2008, 16:01
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 16792
Location: In your JS exploiting you and your system
Hard discs and RAM are both memory, they store data for you to retrieve later. The type of access (random or sequential) does not affect that definition.
Post 27 Dec 2008, 00:05
View user's profile Send private message Visit poster's website Reply with quote
Borsuc



Joined: 29 Dec 2005
Posts: 2468
Location: Bucharest, Romania
What I mean is that it's really easy to write a certain number of 1s on a tape if you have a simple register counter you can access anytime (random), but I think you can't because the tape is sequential. Right?

_________________
Previously known as The_Grey_Beast
Post 27 Dec 2008, 00:51
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 16792
Location: In your JS exploiting you and your system
So now you are starting to understand why BB is a hard problem.
Post 27 Dec 2008, 01:08
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2796
Location: dank orb
Anyone else planning on submitting FASM entries for the competition?

I'm doing one for Win64, but DOS COM should be very small.
Post 27 Dec 2008, 01:49
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: 16792
Location: In your JS exploiting you and your system
I'm not. But good luck bitRAKE. Let us know how you get on. I couldn't find any closing date, is it open dated?
Post 27 Dec 2008, 04:33
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2796
Location: dank orb
Only C++ entries can be a winner.

There doesn't appear to be an end date, yet. They are waiting for submissions to gage interest it seems (only announced a couple days ago). I'm doing it for fun - just thought it might be cool for the contest to add an FASM section to the results, and show how easy the assembly language implementation is in comparison to C++.

I wonder if there is any value to a massively parallel UTM? Are they used for any real work, or just an academic curiosity? Technically, they are "universal", but that doesn't imply practical utility.
Post 27 Dec 2008, 05:54
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: 16792
Location: In your JS exploiting you and your system
AFAIK, no one uses them for anything except academic pleasure/torture.

Besides, where are you going to find an infinitely long tape? Maybe at the hotel infinity.
Post 27 Dec 2008, 05:59
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2796
Location: dank orb
Quote:
At the moment the record 6-state busy beaver produces over 10^1439 1s, using over 10^2879 steps (found by Terry and Shawn Ligocki in 2007). As noted above, these busy beavers are 2-symbol Turing machines.
Wow, only 6-states seem fairly powerful. An eight state machine can be implemented in only a couple instructions. Very Happy (my secret)

Ooo...I love torture/pleasure - perfect.

[edit] guess it's fairly easy to do something like:
Code:
     virtual at esi+eax
          .next rb $10000
             .sym  rb $10000
             .head rb $10000
     end virtual
 mov ah,[edi]            ; read tape
 movzx edx,byte[.sym]    ; update symbol
     movsx ebx,byte[.head]   ; update head position
      movzx eax,byte[.next]   ; next state
        mov [edi],dl
        add edi,ebx    
Post 27 Dec 2008, 06:27
View user's profile Send private message Visit poster's website Reply with quote
Borsuc



Joined: 29 Dec 2005
Posts: 2468
Location: Bucharest, Romania
Can you please explain what each of the registers represents?
Thanks Smile

_________________
Previously known as The_Grey_Beast
Post 28 Dec 2008, 14:24
View user's profile Send private message Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2796
Location: dank orb
I just posted the inner loop code.

AL is the current state - this is an internal register of the UTM. AH is the current tape value (symbol). Together the state and symbol index into tables to advance the UTM: write new value to tape, move tape head (EDI), select next state (AL).

In the BB problems only the symbols 0 and 1 are used, typically.
The bytes of .head would only be -1,0,1. The states in .next should also include an exit condition (zero is easy to use for this). Note when they talk about a four state BB they don't include the halting state.

Of course, the tables are overkill as they support 255 states and 256 symbols, but if you read some of Heiner Marxen's work he talks about how to compress/accelerate a BB -- which will make use of the additional options.
Post 28 Dec 2008, 18:04
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2796
Location: dank orb
Here is my first entry for Win64, EXE is 973 bytes:
Code:
format PE64 Console 5.0

include 'Win64W.inc'

section '' code readable writeable executable

entry $
; Instead of creating a state transition table, itterate through the command
; line parameters and respond based on current state and tape value. This is
; slower, but less code.
    push rsp rsp rsp
    pop rcx rdx r8
      enter 8*20,0
        xor r9,r9               ; globbing = FALSE
  lea rax,[rbp-8*15]
  mov [rbp-8*16],rax      ; STARTUPINFO
       call [MSVCRT.__getmainargs]
 mov esi,[rbp]
       lodsq   ; skip program name
 lodsq
       xchg ecx,eax
        call [MSVCRT.atol]
  xchg edi,eax    ; starting bit, in the middle
       lea ecx,[rdi*2+7 + 8*8]
     shr ecx,3
   push 1
      pop rdx
     call [MSVCRT.calloc] ; because it zeroes the memory
 xchg eax,edi
        stosd
       scasd

label steps        dword at rdi-4
label max_steps       dword at rdi-8

  ; initial conditions
        mov ecx,eax
 mov ebx,eax
 xchg ebp,eax
        mov dl,'1'    ; starting state

; ESI = command line parameters (ad hoc state table)
; RDI = reserved tape memory base
;  DL = current state of machine
;  DH = tape symbol at position ECX
; EBP = least significant used bit on tape
; ECX = current tape position
; EBX = most significant used bit on tape

.outer:
 ; retrieve tape symbol: '0' or '1'
  mov dh,'0' shr 1
  bt [rdi],ecx
        rcl dh,1
    push rsi
    jmp .inner

.next:    pop rsi
     add esi,5*8
 
; this should never happen...
   cmp qword [rsi],0
   jne .inner
  ; early out, no transition from current state/tape
  mov eax,[max_steps]
 mov [steps],eax
     jmp .fail

.inner:
        push rsi
    ; does state match?
 lodsq
       cmp [rax],dl
        jne .next
   ; does tape match?
  lodsq
       cmp [rax],dh
        jne .next
   ; new state: allow any byte, '0' is HALT state
        lodsq
       mov dl,[rax]
        ; update tape: only two state tape initialized to zero
  lodsq
       btr [rdi],ecx ; assume zero
 cmp byte [rax],'1'
        jne @F
      bts [rdi],ecx ; set to one
@@:   ; move tape position: -1, 0, 1
  lodsq
       cmp byte [rax],'0'
        je @F
       sbb eax,eax
 add ecx,eax
 not eax
     sub ecx,eax
@@:  pop rsi
     pop rsi
     ; update tape bounds
        cmp ecx,ebp
 cmovc ebp,ecx ; update lower bound
  cmp ebx,ecx
 cmovc ebx,ecx ; update upper bound
  ; count steps
       inc [steps]
 ; end if HALT state
 cmp dl,'0'
        je .output
  ; end if MAX_STEPS has been reached
 mov eax,[steps]
     sub eax,[max_steps]
 jc .outer

.fail:     push '2'
  pop rcx
     ; force carry to exit loop
  xchg ebx,ebp
        jmp .two

.output:
        ; read a bit and output zero or one
 xor ecx,ecx
 bt [rdi],ebp
        adc ecx,'0'
.two:      inc ebp
     call [MSVCRT.putchar]
       cmp ebx,ebp
 jnc .output
 ; output step count
 mov ecx,step_count
  mov edx,[steps]
     call [MSVCRT.printf]
        
    call [MSVCRT.exit]

data import
       library MSVCRT,'MSVCRT'

       import  MSVCRT,\
           MSVCRT.__getmainargs,'__getmainargs',\
           MSVCRT.atol,'atol',\
             MSVCRT.calloc,'calloc',\
         MSVCRT.exit,'exit',\
             MSVCRT.printf,'printf',\
         MSVCRT.putchar,'putchar'
end data

step_count db 10,13,'%d',10,13,?    
Source code is very small with the comments removed. MSVCRT was used to reduce the IAT to a single DLL. Using a bit string for the tape to conserve memory - want to test large BBs to confirm it works.

Edit: code updated slightly - no attempt to reduce the size of source.


Last edited by bitRAKE on 21 Jan 2009, 02:42; edited 4 times in total
Post 01 Jan 2009, 02:40
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:  
Goto page 1, 2, 3  Next

< 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 can attach files in this forum
You can download files in this forum


Copyright © 1999-2019, Tomasz Grysztar.

Powered by rwasa.