Page **1** of **9**

### Manufactoria - Make Turing Machines with Conveyor Belts

Posted: **Tue May 25, 2010 1:40 am UTC**

by **Vault**

ManufactoriaBasically the object is to accept or reject different patterns of colored dots using conveyor belts and branches. Later you get to add your own dots. Given an infinite robot grid, the game is probably Turing complete.

This thread is split off of the discussion in the FT thread.

-------------

Currently I'm stuck on the Rocket Planes level. It wants me to sort the dots, and so far I am incapable of figuring out how to sort on top of only a queue.

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

Posted: **Tue May 25, 2010 1:46 am UTC**

by **joshz**

If I could have some way of storing variables, that would make it far easier, but I'm not sure how.

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

Posted: **Tue May 25, 2010 1:49 am UTC**

by **Steax**

For which part? The lower half supports adding in your own markers, so that's basically writing your own variables.

Also, has anyone found out how to save the game? It's kind of irritating to have to keep saving the codes. I want to see the big tree diagram-thing.

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

Posted: **Tue May 25, 2010 2:00 am UTC**

by **Vault**

I found the bottom half a lot easier than the top half for just that reason. You can just set a marker on the end, do the necessary transformations with one or two BR gates, and get rid of the marker you set right before it goes through the end.

And what do you mean by save? My progress has been preserved as I've gone away and come back to it.

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

Posted: **Tue May 25, 2010 2:06 am UTC**

by **Steax**

Oh, I didn't realize it auto-saved. Just tried it and it does load back. No problem with that then.

And yes, I found the lower half a lot easier. Being allowed to add in my own variables also eases my head a lot.

I'm also stuck on rocket planes, but I'm edging closer to it...

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

Posted: **Tue May 25, 2010 8:16 am UTC**

by **Ephphatha**

This game is addictive. I finally managed to get past Robomecha after being stuck on it for a while when I worked out that I can send it to a particular track and use that to indicate the second last value read. Ended up with a design that used 34 pieces (the first working version was about 50).

Edit: Having trouble on Android

. Any hints on what I should be doing?

EditEdit: Got it, but I'm sure my solution actually had an infinite loop in it if more reds than blues were provided... Lucky that situation never came up.

EditEditEdit: Oh wow, Soldiers! was stupidly easy.

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

Posted: **Tue May 25, 2010 10:26 am UTC**

by **joshz**

By variable, I really mean a counting variable. So I can count number of blues and reds, or stop reading after the nth dot.

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

Posted: **Tue May 25, 2010 11:07 am UTC**

by **phlip**

Hey, looking at the credits, it's made by the same guy as Конструктор... I thought they looked similar.

[edit] Wait, no, just inspired by it. Still, the appearance and sense of humour is very similar.

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

Posted: **Tue May 25, 2010 12:45 pm UTC**

by **Ephphatha**

Currently doing robo children with, no joke, the worst possible solution. I bubblesort the list (think I took it from my solution to rocket planes) then read through the list until I find the end of the blues and the start of the reds, drop one of each, and repeat. If there's a solo element left, fail. One of the random inputs (or maybe it's a scripted input, I dunno) is a tape of about 30 symbols, with the last 10/15 blue and a few blues scattered randomly. I've had it running on the fastest speed for the past 10 minutes and it's still not through the sorting phase yet...

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

Posted: **Tue May 25, 2010 12:59 pm UTC**

by **jaap**

joshz wrote:By variable, I really mean a counting variable. So I can count number of blues and reds, or stop reading after the nth dot.

You can't do that. Here are a few hints/techniques that may help.

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

Posted: **Tue May 25, 2010 2:15 pm UTC**

by **Briareos**

I'm stuck on Androids as well. Since it's the classic example of a non-regular language, I keep wanting to use a push-down automaton. But I think having that design stuck in my head is making it more difficult for me.

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

Posted: **Tue May 25, 2010 2:48 pm UTC**

by **Ephphatha**

If you want a hint, unspoiler below. (I had to redo it actually, I deleted my solution somehow

)

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

Posted: **Tue May 25, 2010 4:22 pm UTC**

by **Vault**

I still haven't got past the sorting one. The solution that I came up with works for the most part, but is prone to getting stuck in an infinite loop. (Which I guess means that it doesn't actually work).

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

Posted: **Tue May 25, 2010 4:35 pm UTC**

by **TheChewanater**

This game is really making me appreciate my CPU more.

I'm stuck on android right now. My biggest problem is that the board is too small for my ugly solution.

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

Posted: **Tue May 25, 2010 5:01 pm UTC**

by **evilbeanfiend**

Vault wrote:I still haven't got past the sorting one. The solution that I came up with works for the most part, but is prone to getting stuck in an infinite loop. (Which I guess means that it doesn't actually work).

hint

also a number of my saved machines seem to have become corrupted

have to do them again now

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

Posted: **Tue May 25, 2010 5:55 pm UTC**

by **Berengal**

I've got a real decent solution for robo-children now. It's worst-case is O(n log_5 n), but it usually works in O(n) with a kick-ass constant factor.

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

Posted: **Tue May 25, 2010 6:58 pm UTC**

by **TheChewanater**

EDIT AGAIN: Well, that actually doesn't always do what I expect it to.

EDIT: This seems to work some of the times.

Oops, I misunderstood the Android one. I thought it just needed to have the same number of each, so I did this:

Which worked great until I got to one with the same number of reds and blues but all scrambled up.

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

Posted: **Tue May 25, 2010 7:43 pm UTC**

by **D4N_**

I basically just joined (after a long time lurking) to say how awesome this game is. I just finished Androids and have already wasted a few hours on this game. It seems a lot of the taking the dots as binary levels are pretty simple if you're already familiar with binary. I'm still stuck on the Rocket Planes level but will probably give it a good go again later.

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

Posted: **Tue May 25, 2010 8:05 pm UTC**

by **Briareos**

Just finished a disastrously inefficient implementation of Rocket Planes. Back to work on Androids.

EDIT: Got it! I think working on Rocket Planes helped a lot. Now to look at you guys' spoilers.

EDIT: Soldiers? That was straightforward.

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

Posted: **Tue May 25, 2010 8:59 pm UTC**

by **levantis**

can anybody tell how to reverse a string or place an element in the front?

by the way, about the equality - you can place a marker at the end for a blue and delete it for a red. placing a lot of markers in the beginning avoids underflow.

also, you can drop the adjacent red/blue and replace consecutive runs with green/yellow respectively. then repeat with different colors. dunno why, but it worked all the time.

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

Posted: **Tue May 25, 2010 10:34 pm UTC**

by **JavaBean**

I'm surprised everyone is having so much trouble with Rocket Planes - that wasn't the one that tripped me up. The general approach I used was

A more detailed (still pseudo-code) algorithm:

For an actual answer, if you're into that kind of thing:

?lvl=27&code=p12:7f3;b11:7f2;r14:6f3;p14:7f2;c13:7f2;c16:8f3;c16:9f3;c16:10f3;c16:11f0;c15:11f0;c14:11f0;c13:11f0;b14:8f3;p14:9f3;r15:9f0;q14:10f1;i12:10f6;c10:8f1;c10:7f1;c10:6f2;c11:6f2;r13:10f0;b13:9f2;g12:6f3;c12:4f3;c12:5f3;q12:8f0;c12:9f3;c11:10f0;c10:10f1;c10:9f1;q15:8f3;r15:7f3;

On the other hand, I'm glad someone had enough trouble with Rocket Planes to start this thread - it's an excellent game and I wouldn't have found it otherwise. I'm having a heck of a time testing A>B; does anyone else think the binary numbers ought to be given to us with the least significant bit first, rather than last? It would make every numerical program easier, as far as I can see.

Also, to reverse a string: that one is tricky. It's easy enough to move the first symbol to the back, but that's only the first step. I found a useful question to ask myself was:

The answer I came up with for my solution was:

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

Posted: **Wed May 26, 2010 12:42 am UTC**

by **joshz**

For androids, does it need to be n blue in a row then n red in a row? Because I accepted BBRBBRRRBR and it said I should've rejected it.

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

Posted: **Wed May 26, 2010 1:01 am UTC**

by **Token**

Man, I loved this game. It was surprisingly fun going over my early solutions once I'd finished, and seeing how easy it then was to make everything much more elegant.

As far as Androids: it needs to be N consecutive blues, then N consecutive reds, then nothing. There's at least one fairly neat solution.

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

Posted: **Wed May 26, 2010 1:05 am UTC**

by **TheChewanater**

I agree with everyone who says soldiers was too easy. Took two seconds.

So, what sort of property do powers of four have in binary that makes them easily recognizable?

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

Posted: **Wed May 26, 2010 1:05 am UTC**

by **joshz**

Is there any that just requires the same number of reds and blues? Cause I solved that.

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

Posted: **Wed May 26, 2010 1:19 am UTC**

by **D4N_**

Robo-Children requires the same number of reds and blues in any order, so yes.

It seems that if you can find a small enough sort (in terms of space on the board) then you can find out if there are the same number of reds and blues by combining it with the Android solution, shame there isn't a way to plug solutions together to make more complicated ones.

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

Posted: **Wed May 26, 2010 1:33 am UTC**

by **TheChewanater**

I used the same algorithm for androids as robo-children. In reality, this wouldn't work for all sceneries in the androids level, but I don't care. It worked for me, was efficient, and was reusable.

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

Posted: **Wed May 26, 2010 1:49 am UTC**

by **joshz**

OK, so what I have right now for android accepts same number in any order. How do I modify that to make it accept only in a row order? Also, my current alg is extremely inefficient (space-wise) so I'm not sure how much I could fit.

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

Posted: **Wed May 26, 2010 1:53 am UTC**

by **Dason**

joshz wrote:OK, so what I have right now for android accepts same number in any order. How do I modify that to make it accept only in a row order? Also, my current alg is extremely inefficient (space-wise) so I'm not sure how much I could fit.

I haven't looked at your solution yet but to solve the problem why don't you just check to see if you have the pattern (X blue)(Y Red)(Nothing else), if not then reject, otherwise send it into what you have.

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

Posted: **Wed May 26, 2010 2:40 am UTC**

by **joshz**

That's what I'm thinking of doing, I'm just not sure how to fit it. I'll post a screenshot in the morning (7-8ish hours) so you won't have to load my level.

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

Posted: **Wed May 26, 2010 4:23 am UTC**

by **Ephphatha**

TheChewanater wrote:So, what sort of property do powers of four have in binary that makes them easily recognizable?

My solution to that has:

A few undocumented features I've found (and some I've had to be told):

Space flips a branch.

You can make bridges by placing two perpendicular conveyers on the same square.

You can feed a branch from any side.

I kinda like my solution to androids, I can screenshot it if people want but I'll spoiler the procedure below. Try solve it yourself though, it's fun

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

Posted: **Wed May 26, 2010 5:18 am UTC**

by **jaap**

Ephphatha wrote:A few undocumented features I've found (and some I've had to be told):

Space flips a branch.

Damn! I didn't know that.

Another nice feature is that you can copy/paste (select an area, shift-c to copy, shift-v to paste). This works between levels too, so that you can copy parts from one level to the next.

ETA:

My solution to androids seems a bit simpler:

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

Posted: **Wed May 26, 2010 5:36 am UTC**

by **phlip**

Ephphatha wrote:Space flips a branch.

Huh, that'll come in handy.

Ephphatha wrote:You can make bridges by placing two perpendicular conveyers on the same square.

That is documented... somewhere. I'm at work at the moment, so I can't check, but I know the game has told me about that. The tooltip when you select the conveyor tool maybe?

[edit] Yeah, at the bottom of the screen when you have the conveyor selected, it says "Click or drag to place; shift-click to bridge!"... the same thing says "space to flip!" on branches, but I just never noticed.

[edit again] Ah, those status messages aren't on the version of the game linked in the OP... but they are there on

Kongregate. I think the latter is a later version (it says v1.13c on the main menu, whereas the jayisgames one doesn't have a version number there at all).

Ephphatha wrote:You can feed a branch from any side.

It's only on reading this that I actually realised that the unused edge of a branch actually looks kinda like it's supposed to be an input... the idea that the input direction of a branch would matter never occured to me. The conveyor bridge is the only part where the input direction has any effect on the actions.

But yeah, you can do a "move all blues at the head of the tape to the end" type deal by just putting in an R/B branch, and a blue writer on the blue branch pointing right back at the switch again.

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

Posted: **Wed May 26, 2010 6:18 am UTC**

by **Berengal**

I'm pretty sure I saw the space flipping and bridging being explained the first time I played it, because I've known about those all along. I can't seen to find where now though.

Also, robo-children:

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

Posted: **Wed May 26, 2010 6:38 am UTC**

by **Dason**

Berengal wrote:I'm pretty sure I saw the space flipping and bridging being explained the first time I played it, because I've known about those all along. I can't seen to find where now though.

Also, robo-children:

That's beautiful. I didn't realize until reading the recent posts that you could feed into a branch from the sides. I was essentially doing what you have but it's much more a of a clusterfuck because I didn't realize you could feed into the sides.

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

Posted: **Wed May 26, 2010 7:10 am UTC**

by **Glom**

Ok maybe I'm missing something important here. But I'm doing the Robospies puzzle. The puzzle with blue as 1, and red as 0. Accept natural powers of four.

(4, 16, 64... or 100, 10000, 1000000... in binary)

My machine would do that... and it works fine for the first two tests... Gives me 4 first; It accepts. Gives me 2 next; It rejects. But then it gives me 1... Just a blue dot. My machine correctly rejects 1, since it is NOT a power of four. And yet the game says that I should have accepted it.

Is something wrong with the game, or is 1 actually a power of four and I just missed something important?

Here's my machine:

I got it to work doing this:

But it still doesn't seem right. Since... it's wrong!

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

Posted: **Wed May 26, 2010 7:20 am UTC**

by **TNorthover**

Glom wrote:The puzzle with blue as 1, and red as 0. Accept natural powers of four.

(4, 16, 64... or 100, 10000, 1000000... in binary)

[...]

But then it gives me 1... Just a blue dot. My machine correctly rejects 1, since it is NOT a power of four.

4^0 = 1

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

Posted: **Wed May 26, 2010 7:59 am UTC**

by **Glom**

TNorthover wrote:4^0 = 1

derp, that's what I get for playing this stupid game at 4 am

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

Posted: **Wed May 26, 2010 10:43 am UTC**

by **D4N_**

Just finished Rocket-planes. I built it the wrong way round at first so that it shifted blues to the back, so finding out that space flips the branches was really useful. My solution is seriously inefficient though, over 3 minutes on one input (although i haven't trimmed out any unnecessary components yet). Has anyone found an efficient algorithm for this?

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

Posted: **Wed May 26, 2010 10:52 am UTC**

by **joshz**

What I have now for androids:

How can I fit in the logic that only accepts colors in a row?

Oops, that doesn't even work all of the time even for really nice ones. If it doesn't reduce to one of each in one time through, then it fails.