flat assembler
Message board for the users of flat assembler.

flat assembler > Heap > Shortest Universal Turing Implementation Contest!

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


Joined: 24 Aug 2004
Posts: 16782
Location: In your JS exploiting you and your system
bitRAKE wrote:
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.
That would be similar to the fractal compression thing I think. If you can discover the generating seed then almost infinite compression ratios can be achieved.
Post 24 May 2019, 19:31
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2795
Location: dank orb
revolution wrote:
That would be similar to the fractal compression thing I think. If you can discover the generating seed then almost infinite compression ratios can be achieved.
True, but the search space is large for that kind of thing. Very Happy I was thinking more along the line of uncompressible TMs have a common higher level language expressed in the graph - definite similarities.


Another problem: what is the minimum states needed for two asynchronous TMs to communicate on a single tape?

ASSUME: tape is initially empty (all zero).

ASSUME: no TM starts on another TM tape position - concurrency of two TMs only possible after some steps.

ASSUME: both TMs are the same - solving the easier problem of one directional communication might provide some insight, but is not the question.

Here the BB() might even be useful for the TMs to find each other in minimal time?

_________________
¯\(°_o)/¯ unlicense.org
Post 24 May 2019, 19:45
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: 16782
Location: In your JS exploiting you and your system
bitRAKE wrote:
Another problem: what is the minimum states needed for two asynchronous TMs to communicate on a single tape?

ASSUME: tape is initially empty (all zero).

ASSUME: no TM starts on another TM tape position - concurrency of two TMs only possible after some steps.

ASSUME: both TMs are the same
Wouldn't that depend upon what is meant by communicate? To communicate the mere existence of the TM one can simply mark the tape with any symbol to show they are present.
Post 24 May 2019, 20:46
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2795
Location: dank orb
revolution wrote:
Wouldn't that depend upon what is meant by communicate? To communicate the mere existence of the TM one can simply mark the tape with any symbol to show they are present.
That's the one directional problem - kind of trivial.

_________________
¯\(°_o)/¯ unlicense.org
Post 24 May 2019, 21:02
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: 16782
Location: In your JS exploiting you and your system
They can both say "I'm here". Isn't that two way communication?

Bob: Hi Jane.
Jane: Hi Bob.

That is two way, right?
Post 24 May 2019, 21:10
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2795
Location: dank orb
Not if they are on different sides of the universe. They both need to detect the other and acknowledge in some way (internally is fine). Saying "Hi" to the tape doesn't count.

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

< 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.