Index
> Heap > Shortest Universal Turing Implementation Contest!Goto page Previous 1, 2, 3 Next |
| Author |
|
|
revolution
How long is your tape? What happens when you reach the end of it?
|
|||
01 Jan 2009, 02:44 |
|
|
revolution
The competition webpage also mentions about creative source code formatting. I wonder how we can do that in assembly?
|
|||
|
01 Jan 2009, 02:57 |
|
|
bitRAKE
My understanding of:
Quote: We suggest that you format your program in a more creative way than simply forming excessively long lines. [edit] Hector posted my entry to the topic webpage. |
|||
|
01 Jan 2009, 03:07 |
|
|
Madis731
I wonder why they haven't tested it. Your program works with some examples I grabbed from other sources' comments
 |
|||
|
09 Jan 2009, 13:11 |
|
|
bitRAKE
Looks like the leading entry converted my assembly code to C++,
 |
|||
|
21 Jan 2009, 02:39 |
|
|
Madis731
And looks like your code is tested
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. |
|||
|
07 May 2009, 07:17 |
|
|
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... |
|||
|
07 May 2009, 08:20 |
|
|
revolution
The website lists the size for the source code, not the binary. ASM code will almost always lose when compared like that.
|
|||
|
07 May 2009, 12:56 |
|
|
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. |
|||
|
07 May 2009, 14:46 |
|
|
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. Let's hire him! _________________ Previously known as The_Grey_Beast |
|||
|
07 May 2009, 22:10 |
|
|
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. |
|||
|
08 May 2009, 00:13 |
|
|
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? |
|||
|
08 May 2009, 01:23 |
|
|
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  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. |
|||
|
09 May 2009, 11:59 |
|
|
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. |
|||
|
09 May 2009, 14:54 |
|
|
bitRAKE
http://www.aturingmachine.com/
See the busy beaver at work... http://www.aturingmachine.com/examplesBB3.php http://www.aturingmachine.com/examplesBB4.php |
|||
|
02 Nov 2010, 07:06 |
|
|
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. |
|||
|
24 May 2019, 16:52 |
|
|
revolution
bitRAKE wrote: Seven states are probably enough to build a universe.  Last edited by revolution on 24 May 2019, 17:50; edited 1 time in total |
|||
|
24 May 2019, 17:01 |
|
|
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.
|
|||
|
24 May 2019, 17:26 |
|
|
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.
|
|||
|
24 May 2019, 18:24 |
|
| Goto page Previous 1, 2, 3 Next < Last Thread | Next Thread > |
Forum Rules:
|