## Manufactoria - Make Turing Machines with Conveyor Belts

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

### Re: Manufactoria - Make Turing Machines with Conveyor Belts

Regarding your bounds, using my total coverage tester, I get the following data:

Code: Select all
`4    4046         126/run5   10228  +  6k  193/run6   24958  + 14k  230/run7   59188  + 36k  267/run8  137206  + 77k  304/run9  312976  +175k  343/run`

So it looks like increasing the tape length by 1 adds about 40 steps to the average running time. So, the algorithm is linear.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Xanthir
My HERO!!!

Posts: 3993
Joined: Tue Feb 20, 2007 12:49 am UTC

### Re: Manufactoria - Make Turing Machines with Conveyor Belts

I don't seem to believe that, though.

In the worst case, it replaces all the Bs with Ys (so that's roughly N steps).
Then it loops through the string and until there are no Ys, it does YB->BR, YR->RB, so that's N Ys, and thus N steps for each N Ys. The break-condition takes N steps as well.

So shouldn't it be about 2N + N2?

In the expected case it's different because the worst case time of the algorithm depends on the longest section of Bs in the initial tape.

mr-mitch

Posts: 450
Joined: Sun Jul 05, 2009 6:56 pm UTC

### Re: Manufactoria - Make Turing Machines with Conveyor Belts

Based on what you say about your algorithm's worst case, it's very reasonable that the n^2 term is too small to show up in the average data. It's like quicksort, which is actually O(n^2), but acts like O(n*log(n)) in the average case.

For most tapes, the n^2 part of the algorithm is swamped by the linear part.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Xanthir
My HERO!!!

Posts: 3993
Joined: Tue Feb 20, 2007 12:49 am UTC

### Re: Manufactoria - Make Turing Machines with Conveyor Belts

@Xanthir: I hereby confirm that your emulator works perfectly well in Safari. (Could it not do so, given that Chrome supports it as well?)
Hey, like coding? Perhaps you should check out the red spider project.
Feel free to call me Julian. J+ is just an abbreviation.

Jplus

Posts: 1091
Joined: Wed Apr 21, 2010 12:29 pm UTC

### Re: Manufactoria - Make Turing Machines with Conveyor Belts

Safari and Chrome only share WebKit, their rendering engine. Their JS engines are completely different, and so programs might work in one and not the other.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Xanthir
My HERO!!!

Posts: 3993
Joined: Tue Feb 20, 2007 12:49 am UTC

### Re: Manufactoria - Make Turing Machines with Conveyor Belts

Jeezus, I nerd-sniped myself on Manufactoria again. Just finished Ophanim, with a better solution than my best of last time. I don't think I ever managed to finish Metatron myself, actually - I'll attempt it tomorrow.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Xanthir
My HERO!!!

Posts: 3993
Joined: Tue Feb 20, 2007 12:49 am UTC

### Re: Manufactoria - Make Turing Machines with Conveyor Belts

You've sniped me too. Is there a list of levels somewhere, so that I don't have to retry all the lower levels? I got up to the new levels again, but closed my browser and lost it all.
mr-mitch

Posts: 450
Joined: Sun Jul 05, 2009 6:56 pm UTC

### Re: Manufactoria - Make Turing Machines with Conveyor Belts

Huh? Assuming you aren't blocking things from Flash, it should save your progress automatically.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Xanthir
My HERO!!!

Posts: 3993
Joined: Tue Feb 20, 2007 12:49 am UTC

### Re: Manufactoria - Make Turing Machines with Conveyor Belts

Damn this is a fun game. I beat all the regular levels over the last two days and I'm working on the bonus levels now.

I really wish the numbers were little endian for the math problems though
Derek

Posts: 963
Joined: Wed Aug 18, 2010 4:15 am UTC

### Re: Manufactoria - Make Turing Machines with Conveyor Belts

It amuses me that I completely understand the first half or so of this thread from playing the game, but it's turned into implementing various algorithms that I don't know about as a non-computer scientist and proper analysis of the scaling of those solutions.

I'm stuck on 4 or 5 levels now, two of which I'm pretty sure I have a solution for, but those solutions require me to know how to solve the other problems (e.g. if I knew how to move all the blues to the front [or equivalently, reds to the back], then I'd be able to implement all sorts of nifty things that deal with that sorted set-up...), so I just need a break through moment on one to get momentum again. I'm pretty sure sorting them shouldn't be terribly difficult, but hum...

Anyway, I notice both this and the similar logic box game involve 4 possible states (red/blue/green/yellow). Is there any particular significance to that? I was under the impression that these modeled how computer actually worked on a low level, but I thought computers boiled down to just 1's and 0's, not 1's and 0's and 2 other states.

Many of my solutions for the later levels that allow green/yellow markers I only ended up using one colour of (typically just to mark the beginning of a string) as opposed to both. If space wasn't a concern, could those later levels actually be solved without using yellow/green at all? Or do those tasks really need a minimum of 3 states to solve?

Dopefish

Posts: 692
Joined: Sun Sep 20, 2009 5:46 am UTC
Location: The Well of Wishes

### Re: Manufactoria - Make Turing Machines with Conveyor Belts

Working on Officers, Police, and Academics.

Finally finished Robomecha.

Super fun game.
DaBigCheez wrote:Because I totally think Snark's the kind of guy who could pull off a stunt like "let teammate get vigkilled by your drone D1, to make yourself a "confirmed town" for not going against it, then pick off everyone while laughing about it."

Snark

Posts: 317
Joined: Mon Feb 27, 2012 3:22 pm UTC
Location: Washington D.C.

### Re: Manufactoria - Make Turing Machines with Conveyor Belts

Got Ophanim. Getting everything within the workspace was quite tricky. Usually I keep state by using alternate paths, but for this one I had to write state bits to the tape. My solution:

Overview:
Spoiler:
Call the first string A, the second string B.
1. Strip leading zeroes. This ensures that the first bit in each number is 1, and therefore the longer string after stripping leading zeroes must be greater.
2. Loop through the strings, stripping and comparing the first bit of each. If the bits are equal, go to (2). If the B is greater, print one yellow marker and go to (3). If the A is greater, print two yellow markers and go to (3). If the A runs out of bits, then A is no longer than B, and all bits so far have been equal, so A <= B and REJECT. If B runs out of bits, then A is longer so A > B and ACCEPT.
3. Loop through the strings, stripping the first bit of each. If the A runs out of bits, go to (4). If the B runs out of bits, the A is longer so A > B and ACCEPT.
4. Count the yellow markers. If there is one, A < B (either in bits, or length) so REJECT. If there are two then check if B has any bits left. If yes, REJECT, if no, ACCEPT.

Some simplifications are probably possible. Like, I think I could use 0/1 yellow markers instead of 1/2.

Code:
Spoiler:
?lvl=30&code=p11:2f0;c11:3f1;p10:2f0;r10:3f1;b10:1f3;c11:1f0;b6:3f2;p7:2f3;p7:3f3;r8:3f0;c9:2f1;c9:1f0;c8:2f0;c6:2f3;q8:1f1;g7:1f3;g12:2f0;q7:4f7;g6:4f3;c13:2f1;c13:1f2;c7:5f2;c7:6f1;p7:7f2;c7:8f3;c7:9f2;r7:10f3;p7:11f4;b7:12f1;r8:4f3;p8:5f2;b8:6f1;r8:8f3;p8:9f2;b8:10f1;c8:11f0;c9:11f0;c10:9f2;i11:8f5;i11:9f7;c12:8f3;i12:9f7;c12:10f3;c6:5f3;c6:6f3;c6:7f2;c6:8f1;c6:9f1;g6:10f1;q6:11f4;q9:5f6;g9:6f2;p10:6f6;c10:5f2;c11:5f2;c12:5f2;c11:6f2;c12:6f3;c12:7f3;y13:5f1;c13:6f1;c13:7f1;c13:8f1;y13:9f1;c13:3f1;c14:1f2;c15:1f3;c13:4f1;r14:2f2;p15:2f7;b16:2f0;c10:7f2;c11:7f3;g9:8f2;q9:9f2;p10:8f6;c11:10f0;c10:10f0;c9:10f3;c17:1f0;c16:1f0;c15:4f3;i15:5f1;c15:6f2;b15:7f2;p16:4f7;c16:6f3;p16:7f7;q16:8f3;c17:4f3;c17:5f3;c17:6f0;r17:7f0;g17:8f3;c18:4f1;c18:5f1;c18:6f1;c18:7f1;c18:8f1;c18:10f1;c18:11f1;c18:12f1;q15:3f3;g16:3f3;c18:3f1;c18:2f1;c18:1f0;c16:5f0;q14:5f0;g14:6f3;c13:13f0;c18:9f1;c17:9f0;c16:9f3;c15:12f3;c15:13f2;c16:13f2;c17:13f2;c18:13f1;q16:11f7;p16:12f7;y17:11f0;c16:10f3;c17:12f3;c14:8f3;c14:9f3;q14:10f3;c15:11f0;c12:11f0;c11:11f0;c10:11f3;c10:12f3;c10:13f2;c11:13f2;c13:10f3;i13:11f1;p13:12f7;i14:11f6;q14:7f2
Derek

Posts: 963
Joined: Wed Aug 18, 2010 4:15 am UTC

### Re: Manufactoria - Make Turing Machines with Conveyor Belts

Dopefish wrote:Anyway, I notice both this and the similar logic box game involve 4 possible states (red/blue/green/yellow). Is there any particular significance to that? I was under the impression that these modeled how computer actually worked on a low level, but I thought computers boiled down to just 1's and 0's, not 1's and 0's and 2 other states.

+1 for the cutest computer-related remark I've seen in years.

(Answer: neither Manufactoria nor Logic Box model the way actual computers work on a low level. If you're interested, the similar but somewhat harder game Kohctpyktop comes closer.)
Hey, like coding? Perhaps you should check out the red spider project.
Feel free to call me Julian. J+ is just an abbreviation.

Jplus

Posts: 1091
Joined: Wed Apr 21, 2010 12:29 pm UTC

### Re: Manufactoria - Make Turing Machines with Conveyor Belts

Even Konstructor isn't perfect, as IIRC every cell is pulled down (ie if it's not connected to any signals, it automatically gets a 0 value, rather than being some floating indeterminate value) which means you only need to have extra pins for power, and not ground. But it's still pretty close to how ICs work.

The reason that Manufactoria needs the extra states is that the tape isn't a good model for TM memory... in particular, the strict queue nature of it. Say you only had the R/B states, and you want to read the last bit on the tape (as one of the puzzles requires you to do). So you read all the bits off the tape until you get to the end. At that point, if you haven't written any new bits to the tape, then all memory of those earlier bits is lost, or some limited amount of information about them is stored in where the robot's standing on the grid... which is obviously limited by how big your machine is. On the other hand, if you do write to the tape, you can't tell where the original end of the tape is, without having G/W to use as a position marker.
While no one overhear you quickly tell me not cow cow.

phlip
Restorer of Worlds

Posts: 6737
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

### Re: Manufactoria - Make Turing Machines with Conveyor Belts

Jplus wrote: If you're interested, the similar but somewhat harder game Kohctpyktop comes closer.

Oh geez, somewhat harder is a bit of an understatement. Not necessarily because of the logic involved, but because the almost total lack of explanation of whats what, and the help video is only marginally beneficial. Still, after about an hour of testing things and re-watching the help video repeatedly, I think I've got the mechanics figured out and have now completed the first two levels (to be fair, the first level is given in the video), and can start grappling with the logic instead.

Anyway, thanks for that. Carry on with implementing Linux within Manufactoria, or whatever deep coding magics y'all are working on now.

Dopefish

Posts: 692
Joined: Sun Sep 20, 2009 5:46 am UTC
Location: The Well of Wishes

### Re: Manufactoria - Make Turing Machines with Conveyor Belts

I've got a great solution to Metatron (add two numbers), but the grid is too small to contain the termination check.

phlip wrote:Even Konstructor isn't perfect, as IIRC every cell is pulled down (ie if it's not connected to any signals, it automatically gets a 0 value, rather than being some floating indeterminate value) which means you only need to have extra pins for power, and not ground. But it's still pretty close to how ICs work.

The reason that Manufactoria needs the extra states is that the tape isn't a good model for TM memory... in particular, the strict queue nature of it. Say you only had the R/B states, and you want to read the last bit on the tape (as one of the puzzles requires you to do). So you read all the bits off the tape until you get to the end. At that point, if you haven't written any new bits to the tape, then all memory of those earlier bits is lost, or some limited amount of information about them is stored in where the robot's standing on the grid... which is obviously limited by how big your machine is. On the other hand, if you do write to the tape, you can't tell where the original end of the tape is, without having G/W to use as a position marker.

I don't think you need 4 states for Manufactoria. You can map the four states onto pairs of bits: Let R be RR, B be RB, G be BR, and Y be BB. Writers are trivial to implement, and readers are only a bit harder (the issue is that to implement a pass through, you'll have to reprint the first bit and loop back through the entire queue to get it into the right position. It's also very easy to write an encoder or decoder from one representation to the other. Solutions would take a lot more space though.
Derek

Posts: 963
Joined: Wed Aug 18, 2010 4:15 am UTC

### Re: Manufactoria - Make Turing Machines with Conveyor Belts

Derek wrote:It's also very easy to write an encoder or decoder from one representation to the other.

This is the bit that I disagree with... sure, you can write a thing that goes through and reads R's and B's and writes RR's and RB's, but how does it know when it's done?
While no one overhear you quickly tell me not cow cow.

phlip
Restorer of Worlds

Posts: 6737
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

### Re: Manufactoria - Make Turing Machines with Conveyor Belts

phlip wrote:
Derek wrote:It's also very easy to write an encoder or decoder from one representation to the other.

This is the bit that I disagree with... sure, you can write a thing that goes through and reads R's and B's and writes RR's and RB's, but how does it know when it's done?

Yeah, if you were guaranteed that the input was in the new format, then sure you don't need the extra colours, but if the input is unencoded, then you need the extra colours for precisely the reason you described.

Derek wrote:I've got a great solution to Metatron (add two numbers), but the grid is too small to contain the termination check.

The size restriction is part of the problem, dude
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

jestingrabbit

Posts: 5186
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### Re: Manufactoria - Make Turing Machines with Conveyor Belts

phlip wrote:
Derek wrote:It's also very easy to write an encoder or decoder from one representation to the other.

This is the bit that I disagree with... sure, you can write a thing that goes through and reads R's and B's and writes RR's and RB's, but how does it know when it's done?

Fine, do this: R -> RRR, B -> RRB, G -> RBR, Y -> RBB, meta-marker -> B

A valid encoded string contains characters of 3 bits each, and the first bit is always R.

To encode a string:
1. Write a meta-marker (B).
2. If the next bit is B, consume it and finish. Otherwise, go to (3).
3. Read the next two bits and write out R, B, G, or Y as appropriate.
4. Go to (2).

To create a RB branch (GY is symmetric):
1. Write a meta-marker (B).
2. Read the next three bits. If RRR, exit 1, if RRB, exit 2. Otherwise, write the bits back and go to (3).
3. If the next bit is B, consume it and exit 3. Otherwise, copy the next three bits and go to (3).
Derek

Posts: 963
Joined: Wed Aug 18, 2010 4:15 am UTC

### Re: Manufactoria - Make Turing Machines with Conveyor Belts

That still doesn't do the reverse, where you're given an arbitrary input string and try to encode it in your scheme.

The real puzzles would be unsolvable too, if the input strings could be any arbitrary sequences of R/B/G/W... you need the ability to store something out-of-band that can be used as a marker.
While no one overhear you quickly tell me not cow cow.

phlip
Restorer of Worlds

Posts: 6737
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

### Re: Manufactoria - Make Turing Machines with Conveyor Belts

I wrote the encoding step wrong, but what I meant to say wouldn't work either (this is what happens at 2:30 am).

The branch implementation is correct though, and shows that you only need red and blue symbols if your inputs and outputs are encoded correctly. So to the question of "Is a 2-symbol version of Manufactoria Turing Complete?" the answer is still yes.

EDIT: I finally got my termination check small enough to complete Metatron:

Code:
Spoiler:
Code: Select all
`?lvl=31&code=c7:5f2;c7:6f1;c8:5f2;q8:7f0;g8:8f3;c9:5f3;i9:6f5;p9:7f7;q9:8f7;c9:9f3;c10:5f0;c10:6f3;i10:7f7;c11:5f0;c11:6f0;q11:7f2;c12:4f3;c12:5f0;c12:6f1;c13:4f0;c13:5f2;c13:6f1;c14:2f2;r14:3f1;c14:4f0;c14:5f2;q14:7f0;c15:2f2;q15:3f0;g15:4f0;c15:5f3;i15:6f5;p15:7f7;q15:8f7;c16:2f3;p16:3f7;q16:4f7;c16:5f0;c16:6f3;i16:7f7;y16:8f3;c17:2f0;q17:3f6;g17:4f2;c17:5f0;c17:6f0;q17:7f2;c18:2f0;b18:3f1;c18:4f3;c18:5f0;c18:6f1;c6:7f1;c6:6f1;c13:3f1;g10:8f3;b10:9f3;c8:6f2;c14:6f2;y17:8f3;y11:8f3;r11:9f3;r16:9f3;b17:9f3;c8:10f2;r8:9f3;r7:7f1;b12:7f1;b18:7f1;r13:7f1;c9:10f2;c10:10f2;c11:10f2;c12:10f2;c6:5f1;c6:10f1;c6:9f1;c6:8f1;c6:12f1;c6:11f1;c6:13f1;i14:10f3;c15:10f2;c6:3f2;c6:4f1;c11:3f2;r8:11f3;p8:12f4;b8:13f1;c9:11f3;c9:12f0;c9:13f1;g10:11f0;q10:12f4;y10:13f0;r11:11f3;p11:12f4;b11:13f1;c12:11f3;g12:12f0;c13:11f0;g13:12f0;i14:11f0;q14:12f0;c14:13f0;c15:11f0;i15:12f2;c15:13f1;b16:11f2;q16:12f7;c16:13f0;p17:11f3;q17:12f7;r18:11f0;c16:10f2;c13:10f2;g12:8f3;b12:9f3;c14:8f0;c13:8f0;g14:9f0;g13:9f1;y7:11f0;q7:12f0;g7:13f0;r7:2f2;p7:3f2;b7:4f2;i8:3f3;c8:4f1;c8:2f2;c9:2f2;p10:2f2;b10:3f1;r10:1f3;c17:10f3;c13:13f0;q9:3f6;g9:4f3;g12:2f3;g12:3f2;c13:2f2;q11:2f6;`

Screenshot:
Spoiler:
Derek

Posts: 963
Joined: Wed Aug 18, 2010 4:15 am UTC

### Re: Manufactoria - Make Turing Machines with Conveyor Belts

And of course people posting here has dragged me back in. Here's a rather silly metatron that I've been thinking about.

Spoiler:
?lvl=31&code=r8:3f2;y9:1f3;y9:2f2;p9:3f1;c9:4f1;c9:5f1;c9:6f1;q10:1f3;c10:2f1;b10:3f0;c10:4f0;y10:5f2;c10:6f0;c11:1f3;g11:2f3;c11:3f3;p11:4f3;q11:5f3;g11:6f0;c12:2f0;r12:3f2;c12:4f2;c12:5f3;p12:6f3;c13:1f3;q13:2f1;p13:3f1;c13:4f1;c13:5f1;g13:6f1;y14:1f0;y14:2f1;b14:3f0;q12:7f3;y11:7f2;g13:7f2;g14:7f3;g12:9f2;c12:10f1;q12:11f0;y13:8f2;q13:9f0;g13:10f2;c13:11f0;c14:8f3;q14:9f3;b14:10f2;c14:11f0;g15:9f2;p15:10f3;q15:11f7;c16:9f3;r16:10f0;c12:12f3;

Unary.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

jestingrabbit

Posts: 5186
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### Re: Manufactoria - Make Turing Machines with Conveyor Belts

Oh gosh, that is silly, and very very clever. Definitely the smallest non-crazy-packed machine for that level I've ever seen.

Also, as yet another public service announcement, I'd like to again plug my Manufactoria emulator: http://xanthir.com/manufactoria

Just take your level string save, and replace the url part (the part before the ?) with my url. Bam, you have a link to your level reproduced in the emulator. You can see the board (animated!) and run both arbitrary single testcases or do easy total-coverage testing with it. For example, here's jestingrabbit's level.

(My next feature should be to give it a secondary mode where you can link to it as an image and it'll just return an SVG of the board.)

(My other next feature will be the ability to actually see the machine running when you give it a single testcase.)
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Xanthir
My HERO!!!

Posts: 3993
Joined: Tue Feb 20, 2007 12:49 am UTC