flat assembler
Message board for the users of flat assembler.

Index > Heap > Wolfram 2,3 Turing Machine Prize Won

Author
Thread Post new topic Reply to topic
bitRAKE



Joined: 21 Jul 2003
Posts: 2937
Location: vpcmipstrm
bitRAKE
Alex Smith, a 20-year-old undergraduate in Birmingham, UK, has
given a 40-page proof that Wolfram's 2,3 Turing machine is indeed
universal.

http://www.wolframscience.com/prizes/tm23/solved.html

Programming just got easier due to computational equivalence and a smaller universal computational unit. Interesting proof.
Post 24 Oct 2007, 19:20
View user's profile Send private message Visit poster's website Reply with quote
tom tobias



Joined: 09 Sep 2003
Posts: 1320
Location: usa
tom tobias
bitRAKE wrote:

Programming just got easier due to computational equivalence and a smaller universal computational unit. Interesting proof.
Good. thanks, interesting web site. However, your conclusion, above, seems a tad optimistic, looking at history.
Seems to me, we have heard this refrain before.
Something is new, and interesting, and presto: now programming has become easier.
I am sure that I have heard someone express that optimistic opinion elsewhere.....
Anyway, just in case, things stay as they are, i.e. BULKIER = BETTER, then, it is reassuring to know that terabyte drives are available:
http://www.tomshardware.com/2007/04/17/hitachi_7k1000_terabyte_hard_drive/
Smile
Post 24 Oct 2007, 20:22
View user's profile Send private message Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2937
Location: vpcmipstrm
bitRAKE
Code:
;  in     out
; 0 01 -> 0 10 -
; 0 10 -> 0 01 -
; 0 11 -> 1 10 +

; 1 01 -> 0 11 +
; 1 10 -> 1 01 +
; 1 11 -> 0 01 -
; ^-- state
;   ^^-- color[BA]
;  direction --^

; tape position
; esi tape side A
; edi tape side B
_010:
  btr [edi],ecx
_001:
_111:
  dec ecx
State0:
  btc [esi],ecx
  jnc _010
  bts [edi],ecx
  jnc _001
_011:
  inc ecx
State1:
  bts [esi],ecx
  jnc _110
  btc [edi],ecx
  jc _111
  inc ecx
  jmp State0
_110:
  btr [edi],ecx
  inc ecx
  jmp State1    
The above code executes the 2,3 machine. ESI:EDI acts as four color tape (memory) - 00 condition is not handled (or rather, handled incorrectly). Just load your code into memory, set start position in ECX and jmp to State0/1. Laughing

I'll see if I can make it smaller - should be really easy - maybe even a couple instruction loop because I've done Wolfram's 110 rule in a couple instructions (it's only two color though).

The machine doesn't have a halt condition. Maybe, run it in a thread and watch the evolution of memory, or halt with page gaurds on memory?
Post 24 Oct 2007, 21:09
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 can attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar. Also on YouTube, Twitter.

Website powered by rwasa.