flat assembler
Message board for the users of flat assembler.

Index > Heap > Shortest Universal Turing Implementation Contest!

Goto page Previous  1, 2, 3  Next
Author
Thread Post new topic Reply to topic
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 16904
Location: In your JS exploiting you and your system
revolution
How long is your tape? What happens when you reach the end of it?
Post 01 Jan 2009, 02:44
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2800
Location: dank orb
bitRAKE
The user sets the maximum number of steps (defined in the competition as the first command line parameter). Tape is at least twice the maximum number of steps to cover all possibilities. Not dynamic because that is more code. I'd use a memory mapped file if that was the case.
Post 01 Jan 2009, 02: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: 16904
Location: In your JS exploiting you and your system
revolution
The competition webpage also mentions about creative source code formatting. I wonder how we can do that in assembly?
Post 01 Jan 2009, 02:57
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2800
Location: dank orb
bitRAKE
My understanding of:
Quote:
We suggest that you format your program in a more creative way than simply forming excessively long lines.
...was to not reduce size if it overly complicated the source. They have some (unrealistic, imho) hope people will take other approaches to the UTM. But the command line form dictates how such a simple program should be executed if size reduction is the goal, again imho.

[edit] Hector posted my entry to the topic webpage.
Post 01 Jan 2009, 03:07
View user's profile Send private message Visit poster's website Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2145
Location: Estonia
Madis731
I wonder why they haven't tested it. Your program works with some examples I grabbed from other sources' comments Very Happy
Post 09 Jan 2009, 13:11
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2800
Location: dank orb
bitRAKE
Looks like the leading entry converted my assembly code to C++, Laughing
Post 21 Jan 2009, 02:39
View user's profile Send private message Visit poster's website Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2145
Location: Estonia
Madis731
And looks like your code is tested Smile
Actually I took a second look at the source and it seems the simplest way to compress the source is to lose the MSVCRT. prefix afterall. No weird equs are necessary

Btw, how did you measure "EXE is 973 bytes" anyway? Padding makes it 1024.
Post 07 May 2009, 07:17
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
bitshifter



Joined: 04 Dec 2007
Posts: 759
Location: Massachusetts, USA
bitshifter
It seems that some characters may be shaved of the fastest C/C++
version because an int and a char* are the same thing.
I all really depends on the de-referencing, so maybe im wrong.
First thing to do is spread it out so i can actually see and count stuff.
Maybe i will screw around with this and see if i am correct or not.
Right now Alex Stangl and John Tromp's version is 285 chars of code...
Post 07 May 2009, 08:20
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 16904
Location: In your JS exploiting you and your system
revolution
The website lists the size for the source code, not the binary. ASM code will almost always lose when compared like that.
Post 07 May 2009, 12:56
View user's profile Send private message Visit poster's website Reply with quote
bitshifter



Joined: 04 Dec 2007
Posts: 759
Location: Massachusetts, USA
bitshifter
True, but there is a seperate class for each language.

_________________
Coding a 3D game engine with fasm is like trying to eat an elephant,
you just have to keep focused and take it one 'byte' at a time.
Post 07 May 2009, 14:46
View user's profile Send private message Reply with quote
Borsuc



Joined: 29 Dec 2005
Posts: 2468
Location: Bucharest, Romania
Borsuc
revolution wrote:
The website lists the size for the source code, not the binary. ASM code will almost always lose when compared like that.
Remember the member 2 we had here?
Let's hire him!

_________________
Previously known as The_Grey_Beast
Post 07 May 2009, 22:10
View user's profile Send private message Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2800
Location: dank orb
bitRAKE
The assembly source code could be compressed with EQU and MACRO. Also, a DOS version would be much smaller (both executable and source).
Madis731 wrote:
Btw, how did you measure "EXE is 973 bytes" anyway? Padding makes it 1024.
I don't recall - maybe I used another program to trim the padding because I had a smaller one that worked and FASM doesn't seem able to produce the smaller one directly.
Post 08 May 2009, 00:13
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2800
Location: dank orb
bitRAKE
We could construct the 8-bit version here.

For example, we will need a way to access the tape to read/write state information. Limiting tape memory to 64k would be one method, but we could use all availble memory with something like:
Code:
; dx:ax = tape position
;    si = 128 bits per paragraph
       div si ; 128 = 16 bytes/paragraph * 8 bits/byte
     mov ds,ax
   bt [0],dx ; bt [si],dx to reduce size?    
The tape position would be adjusted based on availble memory to start in the middle - also taking into account start paragraph of program.
Post 08 May 2009, 01:23
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: 16904
Location: In your JS exploiting you and your system
revolution
I have invented a new computer language, I call it BB (as in Busy Beaver). Now this language has only one directive: B

So, I invented this language to win the contest. The entire source code is one byte:
Code:
B    
It seems the executable size is unimportant to this contest so the BB compiler only has to implement a back-end that does the function. Should be easy to write in fasm. And indeed bitRAKE has provided the basics of the generated code for us! Razz
Code:
The compiler steps:

1: Load the source file.
2: Check that it is one byte and that the byte is 0x42, if not, fail
3: Output the binary data from bitRAKE's submission.
4: Done.    
Hehe, easy.
Post 09 May 2009, 11:59
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2800
Location: dank orb
bitRAKE
Actually, the contest requires a UTM - which can, of course, implement BB's. Though your idea is sound - the contest web page lists the code size for Mathematica - which practically has the function built-in, lol.

Behind all of this the question of complexity remains. It seems an important topic and at the base of information science. How do we define it in a useful manner?

Which reminds me of a favorite quote:
John von Neumann wrote:
You should call it entropy, for two reasons. In the first place your uncertainty function has been used in statistical mechanics under that name, so it already has a name. In the second place, and more important, no one really knows what entropy really is, so in a debate you will always have the advantage.
(Suggesting to Claude Shannon a name for his new uncertainty function,
as quoted in Scientific American Vol. 225 , (1971), p. 180)
Post 09 May 2009, 14:54
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2800
Location: dank orb
bitRAKE
Post 02 Nov 2010, 07:06
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2800
Location: dank orb
bitRAKE
2014: A new lower bound for S(7) was calculated at: > 10^10^10^10^10^7
Proving_the_bound_for_S(7)

Seven states are probably enough to build a universe.

_________________
¯\(°_o)/¯ unlicense.org
Post 24 May 2019, 16:52
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: 16904
Location: In your JS exploiting you and your system
revolution
bitRAKE wrote:
Seven states are probably enough to build a universe.
Yes, I agree. But how much diversity would such a universe have? I sometimes wonder if simulations on a home computer could become internally self aware and it begins to wonder about it's world, ... and then suddenly someone presses CTRL-C to kill the errant program. Sad


Last edited by revolution on 24 May 2019, 17:50; edited 1 time in total
Post 24 May 2019, 17:01
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2800
Location: dank orb
bitRAKE
At the lowest scale it might not be diverse, but at larger scales the complexity is virtually unbounded. Maybe dark energy is the Turing tape - existing at such a minor scale as to be beyond our perception, yet abundant and fundamental to the evolution of the universe.

_________________
¯\(°_o)/¯ unlicense.org
Post 24 May 2019, 17:26
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2800
Location: dank orb
bitRAKE
Here is a little puzzle for you: what is the correlation between random Turing machines and the compressibility of their tape after some large number of steps? I don't think it's related to the BB() problem - as that tape is easily compressed - more interesting is the TMs at the other end of the spectrum.

_________________
¯\(°_o)/¯ unlicense.org
Post 24 May 2019, 18:24
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 Previous  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.