Manufactorium--a logic game. (Kind of a turing machine programming game)

The Game Room
41

I was thinking about Turing completeness last night, while half asleep. I saw that there was an argument that it is Turing complete, but I didn’t really read the argument. Last night I was wondering if it’s possible to make an arbitrary number of copies of a string. Shouldn’t a Turning complete system be able to do that?

I couldn’t think of a way to do it. But I’m not convinced it can’t be done. What I could do is, for every x and y, build a machine that makes y copies of a string of length x. These machines get super-huge really quickly. (The only way I can think of to do it is have a different physical region correspond to every possible string of that length–which adds up to a lot of regions once x gets very large, and those regions get larger and larger as y grows.)

What I couldn’t think of a way to do is build a machine that, for every x and y, makes x copies of strings of length y.

Again, in case the difference got past you:

I can see how, for every x and y, to build a machine that makes y copies of a string of length x.

I can’t see who to build a machne that, for every x and y, makes y copies of a string of length x.

In other words, give me the x and y, and I can build you a machine. But I can’t build you a machine that deals with arbitrary x and y.

(I also couldn’t see a way to build a machine that deals with arbitary number of copies even given string length. Also vice versa.)

However, I was thinking about this while mentally exhausted, so I am not surprised if I missed something. If someone sees a way to do this, I’d be interested in knowing that. I’d then think about it some more…

Anyway, I’m right, right, that a Turing complete machine should be able to do this?

Maybe not. Maybe it can be that it’s Turing complete on an interpretation of its mechanisms that doesn’t include the operation I described as one that is interpreted as the completion of some task or other. (?)

42

Now I’ve read through the argument that it’s Turing complete.

I see I was making the mistake of requiring an interpretation where the game’s colors are each a symbol for the turing machine, and the game’s “blanks” (of which really there can be only one per tape) as the “blank” symbol for the turing machine.

But instead, you could simply interpret red as blank, blue as mark, yellow as a marker separating cells (though I’m not sure you’d need this if each dot is just a single symbol) and green as head position. IIRC (and I probably don’t) a machine with just a single symbol in addition to the “blank” symbol can be a Turing machine.

If I’m remembering that wrong, you could still do it using pairs of dots for symbols with yellows separating them.

By the way, making n copies of a string of length m for arbitrary m and n is just multiplication, basically, so of course a Turing complete machine should be able to do it. But I think that on this interpretation, it can be done. The thing would be huge.

43

I’ll assume that the input comes in the form of (string to copy)(green)(number of copies). My solution is (in sketch form):

First, the working form of the tape is
(original string)(green)(partial copy)(green)(finished copy i)(green) … (green)(finished copy 1)(yellow)(remaining number of copies)(green)

The original string also contains a yellow, marking place.

The preprocessing is: put a yellow at the very start of the string, and one after the green,and a green after the number. So now the string looks like
(yellow)(original string)(green)(empty string)(yellow)(number)(green)
Step 1: Search until you find the yellow, and examine the dot after it. If it is blue or red, swap the locations of the yellow and blue/red, move to the end of the string, and on to the end of the partial copy, and add the blue/red to it. Read through the entire rest of the tape to get to the start, and repeat step 1.
If the dot after the yellow is green, just remove the yellow, go to the number, decrement it, and go to step 2.
Step 2: Test if the number is zero. If so, do whatever clean up is necessary, and accept. Otherwise put a yellow at the start of the start of the original string, and an extra green at the end of it, find your way back to the start, and goto step 1.

Obviously leaving out some details, but hopefully understandable.

Right, the question isn’t whether it is a Turing machine (it’s clearly not) but whether it has the same computational power as one. The argument is that it can be used to simulate any Turing machine, so it must.

44

Only in so far as I’ve been trying to avoid O(infinity) solutions. Trying not entirely successfully, at that: I keep on ending up making machines that will accept valid solutions but send invalid ones into an infinite loop, or vice-versa. I think I need to be a bit more meticulous about putting in yellows and greens to mark the end of string.

45

Useful trick I just discovered: Copying machines from one challenge to another. On the original machine, click the save button, and copy the code. Paste it into a text editor. Then go to the new challenge, click the save button, and make note of what the puzzle number is. Change the lvl= value to the new number in your text editor, and paste that into the new challenge.

46

Out of curiosity, what exactly was the manner in which your Ophanim solution was not robust?

47

It didn’t deal with leading zeroes correctly. If the numbers had differing amounts of leading zeroes, and this difference made a difference in string length (as in, the smaller number had a longer string), the machine could incorrectly reject or accept. Given that only the random tests had leading zeroes, and the fairly narrow circumstances to trigger the error, I knew I could get it to accept by trying again, and so I did.

48

Ah, yes, I haven’t thought about time efficiency either beyond “Will this finish in my lifetime?”, but I was actually referring in that post to space efficiency (as in number of pieces).

49

I’m perversely proud of my rocket planes solution, because it’s so remarkably slow:


?lvl=27&code=c12:4f0;c11:4f0;c15:8f3;g10:4f3;b9:5f2;p10:5f3;i11:5f4;c12:5f2;c13:5f2;r14:4f3;p14:5f2;q15:5f6;r13:6f3;b14:6f0;r15:6f3;q10:6f6;c11:6f1;c10:7f3;c11:7f1;b12:7f2;p13:7f3;r14:7f0;q13:8f7;c12:8f0;c11:8f1;c15:7f3;c10:8f3;c12:10f3;c15:9f0;c14:9f0;c13:9f0;c10:9f2;c11:9f2;c12:9f3;

What it does is transcribe the input, except that it moves the first misplaced blue dot one position toward the beginning of the string. Repeat until there are no more misplaced dots.

50

I’ve taken a look at some of the designs that work in record time. It looks like many of them work by taking advantage of knowledge of the preset test strips, which feels to me like cheating.

51

Just solved ophanim, but hoo-boy is it ugly.


?lvl=30&code=y11:5f2;r11:6f2;q11:7f1;c12:4f3;c12:5f3;c12:6f3;p12:7f7;y13:5f0;b13:6f0;q13:7f5;c13:8f3;c13:9f3;c13:10f2;c12:3f3;c11:3f2;c13:3f0;c11:9f3;c11:8f3;c11:10f0;c12:8f3;c12:9f3;c12:10f3;c15:3f0;c15:4f3;i15:5f1;c15:6f3;c15:7f2;i15:8f0;c15:9f1;c15:10f2;c16:3f0;b16:4f0;q16:5f5;c16:6f1;p16:7f6;q16:8f7;r16:9f0;c16:10f2;c14:3f0;c14:5f0;g14:7f2;c14:8f0;c14:10f2;c6:3f2;c6:4f1;c6:5f1;c6:6f1;c6:7f1;y6:8f1;c6:9f1;c6:10f1;c7:3f2;c7:4f1;g7:5f1;i7:8f6;i7:10f6;c8:3f2;r8:4f2;q8:5f1;c8:6f1;p8:7f4;q8:8f3;b8:9f2;c8:10f0;c9:3f2;c9:4f3;i9:5f5;c9:6f3;c9:7f0;i9:8f4;c9:9f1;c9:10f0;c10:3f2;c10:5f2;g10:7f0;c10:8f2;c10:10f0;y12:2f3;g18:3f0;c18:4f1;c18:5f1;c18:6f1;c18:7f1;c18:8f1;c18:9f1;c18:10f1;i17:10f7;c17:3f0;c7:7f3;c7:9f3;q7:11f3;c8:11f3;c8:12f3;c8:13f2;c9:13f2;c10:13f2;c6:11f1;c17:7f3;i17:8f5;c17:9f3;q17:11f3;c11:13f2;q12:11f3;q13:13f7;c13:11f3;p17:12f7;c16:12f2;c18:12f0;c17:13f0;c16:13f0;c15:13f0;c14:13f0;c16:11f3;c18:11f3;p13:12f3;c14:12f0;c17:5f2;
52

Here’s my (unoptimised) solution for Ophanim:


?lvl=30&code=y12:2f3;c8:2f2;c9:2f2;c10:2f2;c11:2f2;c13:2f0;c14:2f0;c15:2f0;c16:2f0;c17:2f0;c18:2f0;q8:3f6;p8:4f0;q8:5f2;b9:3f3;c9:4f0;r9:5f1;g10:4f0;b11:3f2;q11:4f1;c12:3f3;p12:4f3;r13:3f0;q13:4f5;g14:4f2;r15:3f3;c15:4f2;b15:5f1;q16:3f0;p16:4f2;q16:5f4;c18:3f1;c18:4f1;c18:5f1;c8:6f3;c16:6f2;c17:6f2;c18:6f1;c6:7f2;c6:8f1;c6:9f1;c6:10f1;c6:11f1;c7:7f2;c7:11f0;c8:7f2;q8:8f6;p8:9f0;q8:10f2;c8:11f0;c9:7f2;b9:8f3;c9:9f0;r9:10f1;c10:7f2;g10:9f0;c11:7f2;b11:8f2;q11:9f1;y12:7f3;c12:8f3;p12:9f3;c12:10f3;c13:7f0;r13:8f0;q13:9f5;c14:7f0;g14:9f2;c15:7f0;r15:8f3;c15:9f2;b15:10f1;c16:7f0;q16:8f0;p16:9f2;q16:10f4;c16:11f2;c17:11f2;c18:7f1;c18:8f1;c18:9f1;c18:10f1;c18:11f1;q12:11f7;c11:11f3;c17:8f1;c17:7f0;c17:3f1;p11:12f7;q11:13f1;r10:12f2;q17:4f6;q17:9f6;q7:9f0;c7:8f1;q7:4f4;c7:5f3;c7:6f3;

I’ve got two loops: “Default Pass” and “Default Fail”, that tell me whether, so far, A > B. Starting from the little end, I compare An and Bn:
[ul]
[li]If An > Bn, the glyph is sent to the “Default Pass” loop.[/li][li]If An < Bn, the glyph is sent to the “Default Fail” loop.[/li][li]If An = Bn, the glyph remains on the same loop.[/li][/ul]
This continues until there are no more digits in A.

53

Yours is better than mine. Now we must be enemies :mad:

When I was in college, I used to call this “homework”. Why am I enjoying it now?

54

Because now you have other work to procrastinate…

55

This game makes me feel not smart. I am up to the Soldiers column, though. I and my mediocre brain will claw our way through to the bitter end.

56

I have solutions for Metatron and Judiciary worked out in my head, but I can’t fit them in the allowed space :mad:

57

That’s always the problem, isn’t it? Something that may help: throughout the game, you frequently need a certain structure that reads through a red/blue string, copying all dots except the last, with different exits depending on whether the last dot was red or blue. For most of my solutions, I used a 3 by 5 monstrosity to achieve this, but I eventually realised that it can be done in a mere 2 by 3. This saves a lot of space.

58

I’ve also been using a stock 3 by 5 setup for it; probably even the same one. I haven’t yet figured out the 2 by 3, but I imagine the hint that it exists will be really helpful; thanks!

(I still haven’t finished Metatron (been trying to return to my interrupted ostensible productivity), but I’m confident once I do, I can use it to go back and do Ophanim properly, simply by altering it a little to treat the second number as its one’s complement, so that the final carry bit tells the result of the comparison)

59

Figured it out, assuming the design should have three exits and react as follows: A) if the last red/blue is followed by a green, then delete both, and exit out the red-green or blue-green exits, accordingly, B) if the last red/blue is followed by yellow, then delete both, and keep going as if neither was there in the first place, C) if the last red/blue is followed by nothing, get stuck in an infinite loop, and D) if there is no last red/blue (i.e., if it starts with green, yellow, or lack of input), exit out the error exit without changing anything.

60

That is indeed the design I used. You have to know what you’re expecting at the end of it, but you generally do. :slight_smile: