Dominion Strategy Forum

Please login or register.

Login with username, password and session length
Pages: 1 ... 9 10 [11]  All

Author Topic: a fascinating puzzle game  (Read 25836 times)

0 Members and 1 Guest are viewing this topic.

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3384
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2639
    • View Profile
Re: a fascinating puzzle game
« Reply #250 on: February 10, 2014, 07:41:08 pm »
0

Looking more into the definitions and such, I now don't know if it is one or not...  Could someone who would be able to tell figure out?

(edit, if it isn't, I think it would be pretty easy to turn it into one)
« Last Edit: February 10, 2014, 08:19:40 pm by sudgy »
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

   Quote from: sudgy on June 31, 2011, 11:47:46 pm

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3384
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2639
    • View Profile
Re: a fascinating puzzle game
« Reply #251 on: February 11, 2014, 01:14:09 am »
0

I figured out one thing I didn't make.  I didn't make the head have a state...  Here's the last one but with states:

Code: [Select]
http://xorballs.dskl.net/#3,end,[109,new:44bE],[76,Turing%20Machine:02707615618425726bD27436738B44bA46648bk66767bj685725774],[72,Almost%20Turing%20Machine:02704613614bF15716623725530633734bP40041bC42bB43A45bD46450553bH54B55461766572774bQ765837845],[75,Color%20Memory:12614415430634H35G40044aV45050I54J555807827846],[107,State%20Write%20Test:11714620721022424F306400413425448817846],[108,Turing%20Machine-1:037040086480585],[77,Tape:00604405415J21722630731aG32bI34641bG42bJ43644bF45A47648751553A55756bD57463764bO67572774bN75976bM78580581I84887bK884],[87,Turing-2:24526442D44745aG46565567484B875],[74,Write%20Test:01706611B14620721022423624A25630633C34D35F400413425434444454467817846],[73,Color%20Split:34C36737C38644A46A47F48754D56757D585],[79,Turing-1:00603904806610C11713D14716F17720721aG22623724aG25526727aG28631B34937540L43B46B479515534546574635644705784827846],[88,Mini-Tape:31734640G41543644bF457537555],[31,Color%20Memory%20Direction:03704105414718622724aW26430634735540042aP46A48050554458562764aX664],[16,init%20reset:217241254306337340354400443455487537540554635648677685815844],[80,Tape-2:04C40B41E44648750751C585],[78,Tape-1:44B480585],[81,Tape-3:43C44B54E],[86,Tape-7:40G],[85,Tape-6:045084481585],[84,Tape-5:116174217221262286306325357360400419426437447463475489527535557561584805864],[82,Tape-4%20%28Delay%29:00704510918422723724725726727631732aG33aG34aG35aG36aG38B40bL41242843B44B45B46B481517577585705724],[32,BR%20Partial%20Color%20Memory:04506416aU26aS27C28435645046348866aT67D68476aU846864],[25,Partial%20Color%20Memory:04506416aU26aS27C28435636aS37D38945046348856aT57E58B66aT67F68476aU846864],[33,YG%20Partial%20Color%20Memory:04506416aU26aS27E28435645046348866aT67F68476aU846864],[83,Tape-4-1:037040086487],[30,53-3:03704005443544B456837840854],[28,53-1:486837840884],[29,53-2:037041084485]
States are manipulated through the right side while all of the previous stuff works on the left.  Green and yellow work the same on the right side, but it changes the state of the head instead (blue and red, because of how I made it work, work like yellow if you wanted to know for some reasons).
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

   Quote from: sudgy on June 31, 2011, 11:47:46 pm

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3384
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2639
    • View Profile
Re: a fascinating puzzle game
« Reply #252 on: February 11, 2014, 04:38:04 am »
0

Alright.  Last one (quintuple posts ftw!).  I made one with rules (and a default rule that is somewhat interesting).  Input from the left checks the tape and state and makes a new tape, state, and moves the tape (according to customizable rules).  It also outputs a bunch of balls which is how many times you have done this.  Input from the top outputs the current cell, and input from the bottom outputs the current state.

Code: [Select]
http://xorballs.dskl.net/#3,end,[135,new:44cA],[134,Final:31732aq37641944c9477],[133,Color%20Fixer:03704005414J33534035444bl53754055674J837840854],[52,Recursion:32733737642aG43944aq477],[109,Turing%20with%20Rules:13618433635640J41B43044c845046747bm485517555574637665],[16,init%20reset:217241254306337340354400443455487537540554635648677685815844],[110,Interpreter:13717bt18622726by28631734641342143aV44148751752564765bn68573774c3785846854864874],[132,Mini%20Turing%20Machine:02603604B10612114015621722bh24025432533K34435736638640143044bE45048150551553454657465566767bh685837841859875],[31,Color%20Memory%20Direction:03704105414718622724aW26430634735540042aP46A48050554458562764aX664],[111,0-%3F:30731C35bp38640A41D44bq48750951E53br58560761F62bs685727737746754],[117,1-%3F:30731C35bu38640A41D44bv48750951E53bw58560761F62bx685727737746754],[122,2-%3F:30731C35bz38640A41D44c048750951E53c158560761F62c2685727737746754],[127,3-%3F:30731C35c438640A41D44c548750951E53c658560761F62c7685727737746754],[76,Turing%20Machine:02707615618425726bD27436738B44bA46648bk66767bj685725774],[105,init%20reset%20copy:217241254306337340354400442455487537540554635648677685815844],[32,BR%20Partial%20Color%20Memory:04506416aU26aS27C28435645046348866aT67D68476aU846864],[25,Partial%20Color%20Memory:04506416aU26aS27C28435636aS37D38945046348856aT57E58B66aT67F68476aU846864],[33,YG%20Partial%20Color%20Memory:04506416aU26aS27E28435645046348866aT67F68476aU846864],[113,0-0:24728634G44A46B47I48756757H58563664B73H74I837846],[114,0-1:24728634H44A46B47I48756757I58563664B73J74I837846],[115,0-2:24728634G44A46B47I48756757J58563664B73J74I837846],[116,0-3:24728634H44A46B47I48756757G58563664B73J74I837846],[118,1-0:24728634G44A46B47I48756757I58563664B73I74I837846],[119,1-1:24728634H44A46B47I48756757J58563664B73G74I837846],[120,1-2:24728634G44A46B47I48756757G58563664B73G74I837846],[121,1-3:24728634H44A46B47I48756757H58563664B73G74I837846],[123,2-0:24728634H44A46B47I48756757J58563664B73J74I837846],[124,2-1:24728634G44A46B47I48756757G58563664B73J74I837846],[125,2-2:24728634H44A46B47I48756757H58563664B73H74I837846],[126,2-3:24728634G44A46B47I48756757I58563664B73G74I837846],[128,3-0:24728634H44A46B47I48756757G58563664B73G74I837846],[129,3-1:24728634G44A46B47I48756757H58563664B73I74I837846],[130,3-2:24728634H44A46B47I48756757I58563664B73I74I837846],[131,3-3:24728634G44A46B47I48756757J58563664B73I74I837846],[75,Color%20Memory:12614415430634H35G40044aV45050I54J555807827846],[72,Almost%20Turing%20Machine:02704613614bF15716623725530633734bP40041bC42bB43A45bD46450553bH54B55461766572774bQ765837845],[108,Turing%20Machine-1:037040086480585],[107,State%20Write%20Test:11714620721022424F306400413425448817846],[30,53-3:03704005443544B456837840854],[28,53-1:486837840884],[29,53-2:037041084485],[77,Tape:00604405415J21722630731aG32bI34641bG42bJ43644bF45A47648751553A55756bD57463764bO67572774bN75976bM78580581I84887bK884],[87,Turing-2:24526442D44745aG46565567484B875],[74,Write%20Test:01706611B14620721022423624A25630633C34D35F400413425434444454467817846],[73,Color%20Split:34C36737C38644A46A47F48754D56757D585],[79,Turing-1:00603904806610C11713D14716F17720721aG22623724aG25526727aG28631B34937540L43B46B479515534546574635644705784827846],[88,Mini-Tape:31734640G41543644bF457537555],[80,Tape-2:04C40B41E44648750751C585],[78,Tape-1:44B480585],[81,Tape-3:43C44B54E],[86,Tape-7:40G],[85,Tape-6:045084481585],[84,Tape-5:116174217221262286306325357360400419426437447463475489527535557561584805864],[82,Tape-4%20%28Delay%29:00704510918422723724725726727631732aG33aG34aG35aG36aG38B40bL41242843B44B45B46B481517577585705724],[83,Tape-4-1:037040086487]
This is the rules configuration I used:

Code: [Select]
{{{1,'L',1},{2,'R',3},{3,'L',3},{0,'R',3}},
 {{2,'L',2},{3,'R',0},{0,'L',0},{1,'R',0}},
 {{3,'R',3},{0,'L',3},{1,'R',1},{2,'L',1}},
 {{0,'R',0},{1,'L',2},{2,'R',2},{3,'L',2}}}

(note, in this discussions, 0 = blue, 1 = red, 2 = yellow, 3 = green)

There are sixteen triples in that.  Each row is what the current state is, and each column is what the current cell is.  So, if the state is 1 and the cell is 2, the instructions are {0,'L',3} which means to change the color of the cell to 0, move the tape left, and change the state to 3.  There are sixteen custom cells in the machine called 0-0, 0-1, 0-2, 0-3, 1-0, 1-1, etc.  You can change these to make whatever rules you want.  The paintbrushes on the right are the ones that changes the cell, the paintbrushes on the bottom are the ones that changes the state, and the one in the middle is the one that moves it left or right.  You could make it not change if you wanted to (by just making it never split to that direction).

I haven't made an easy way to see the whole tape, so it will be hard to see what happens.  It still fully functions though (I tested it with another program to make sure it was working right (not too much, I hope I didn't make a "typo" somewhere)).  Tomorrow, if anybody wants me to, I can say how the whole thing works, but it is extremely late and I need to get to bed.

Oh yeah, also, with the current setup, you can't edit the initial tape.  That could probably be fixed though.
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

   Quote from: sudgy on June 31, 2011, 11:47:46 pm

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3384
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2639
    • View Profile
Re: a fascinating puzzle game
« Reply #253 on: February 11, 2014, 12:00:53 pm »
0

So, I made a couple more features.

Code: [Select]
http://xorballs.dskl.net/#3,end,[135,new:44cA],[134,Final:13714015417c918431732aq37641943744bl477481585635654],[52,Recursion:32733737642aG43944aq477],[109,Turing%20with%20Rules:13618433635640J41B43044c845046747bm485517555574637665],[133,Output%20Interpreter:00602403404J05413514G15A16cC18420623425H32733bK34438C40441742bK43448851555458D65G73674J75A76cC78480583484H854],[16,init%20reset:217241254306337340354400443455487537540554635648677685815844],[132,Mini%20Turing%20Machine:02603604B10612114015621722bh24025432533K34435736638640143044bE45048150551553454657465566767bh685837841859875],[110,Interpreter:13717bt18622726by28631734641342143aV44148751752564765bn68573774c3785846854864874],[136,x10:00608410618920624928930638940448A50558B60568B70578B805844884],[82,Tape-4%20%28Delay%29:00704510918422723724725726727631732aG33aG34aG35aG36aG38B40bL41242843B44B45B46B481517577585705724],[105,init%20reset%20copy:217241254306337340354400442455487537540554635648677685815844],[76,Turing%20Machine:02707615618425726bD27436738B44bA46648bk66767bj685725774],[117,1-%3F:30731C35bu38640A41D44bv48750951E53bw58560761F62bx685727737746754],[122,2-%3F:30731C35bz38640A41D44c048750951E53c158560761F62c2685727737746754],[31,Color%20Memory%20Direction:03704105414718622724aW26430634735540042aP46A48050554458562764aX664],[111,0-%3F:30731C35bp38640A41D44bq48750951E53br58560761F62bs685727737746754],[127,3-%3F:30731C35c438640A41D44c548750951E53c658560761F62c7685727737746754],[83,Tape-4-1:037040086487],[75,Color%20Memory:12614415430634H35G40044aV45050I54J555807827846],[72,Almost%20Turing%20Machine:02704613614bF15716623725530633734bP40041bC42bB43A45bD46450553bH54B55461766572774bQ765837845],[108,Turing%20Machine-1:037040086480585],[107,State%20Write%20Test:11714620721022424F306400413425448817846],[118,1-0:24728634G44A46B47I48756757I58563664B73I74I837846],[119,1-1:24728634H44A46B47I48756757J58563664B73G74I837846],[120,1-2:24728634G44A46B47I48756757G58563664B73G74I837846],[121,1-3:24728634H44A46B47I48756757H58563664B73G74I837846],[123,2-0:24728634H44A46B47I48756757J58563664B73J74I837846],[124,2-1:24728634G44A46B47I48756757G58563664B73J74I837846],[125,2-2:24728634H44A46B47I48756757H58563664B73H74I837846],[126,2-3:24728634G44A46B47I48756757I58563664B73G74I837846],[32,BR%20Partial%20Color%20Memory:04506416aU26aS27C28435645046348866aT67D68476aU846864],[25,Partial%20Color%20Memory:04506416aU26aS27C28435636aS37D38945046348856aT57E58B66aT67F68476aU846864],[33,YG%20Partial%20Color%20Memory:04506416aU26aS27E28435645046348866aT67F68476aU846864],[113,0-0:24728634G44A46B47I48756757H58563664B73H74I837846],[114,0-1:24728634H44A46B47I48756757I58563664B73J74I837846],[115,0-2:24728634G44A46B47I48756757J58563664B73J74I837846],[116,0-3:24728634H44A46B47I48756757G58563664B73J74I837846],[128,3-0:24728634H44A46B47I48756757G58563664B73G74I837846],[129,3-1:24728634G44A46B47I48756757H58563664B73I74I837846],[130,3-2:24728634H44A46B47I48756757I58563664B73I74I837846],[131,3-3:24728634G44A46B47I48756757J58563664B73I74I837846],[77,Tape:00604405415J21722630731aG32bI34641bG42bJ43644bF45A47648751553A55756bD57463764bO67572774bN75976bM78580581I84887bK884],[87,Turing-2:24526442D44745aG46565567484B875],[74,Write%20Test:01706611B14620721022423624A25630633C34D35F400413425434444454467817846],[73,Color%20Split:34C36737C38644A46A47F48754D56757D585],[79,Turing-1:00603904806610C11713D14716F17720721aG22623724aG25526727aG28631B34937540L43B46B479515534546574635644705784827846],[88,Mini-Tape:31734640G41543644bF457537555],[30,53-3:03704005443544B456837840854],[28,53-1:486837840884],[29,53-2:037041084485],[80,Tape-2:04C40B41E44648750751C585],[78,Tape-1:44B480585],[81,Tape-3:43C44B54E],[86,Tape-7:40G],[85,Tape-6:045084481585],[84,Tape-5:116174217221262286306325357360400419426437447463475489527535557561584805864]
Balls coming from the left do the same as before.  Balls coming from the top are like you inputted them directly into the machine on the left.  Balls coming from the bottom are like you inputted them directly into the machine on the right.  A blue ball from the right outputs the ten cells to the left on the tape, and a red ball from the right outputs the ten cells to the right on the tape.  Just a note, putting anything in the top, right, or bottom messes up the machine at the moment (Edit: Inputting a green in the top and bottom will fix it IF you have not put anything else in from the left)...
« Last Edit: February 11, 2014, 12:15:54 pm by sudgy »
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

   Quote from: sudgy on June 31, 2011, 11:47:46 pm

David

  • Steward
  • ***
  • Offline Offline
  • Posts: 29
  • Respect: +7
    • View Profile
Re: a fascinating puzzle game
« Reply #254 on: February 11, 2014, 02:01:55 pm »
0

So what you made first is a tape head, not a Turing machine.
A Turing machine also has a state machine.
What you wrote later sounds like one actual specific Turing machine, but I didn't follow it completely so it would be good if you good do a detailed write-up of that.

The holy grail would be a generic Turing machine that you can program by first inputing the state transition matrix and tape contents after which you tell it to run the program based in the input. Want to give that a shot? :)
Logged

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3384
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2639
    • View Profile
Re: a fascinating puzzle game
« Reply #255 on: February 11, 2014, 02:23:30 pm »
0

So what you made first is a tape head, not a Turing machine.
A Turing machine also has a state machine.
What you wrote later sounds like one actual specific Turing machine, but I didn't follow it completely so it would be good if you good do a detailed write-up of that.

The holy grail would be a generic Turing machine that you can program by first inputing the state transition matrix and tape contents after which you tell it to run the program based in the input. Want to give that a shot? :)

You can easily change the state transition matrix by changing the custom tiles if you want (the 0-0 and such).  Then, if you want, you can change the tape by putting in your own directions into it from the top (and change the state from the bottom if you want) (make sure you end with green).  So, it is easily customizable.

I have to go, I'll do a writeup when I come back.
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

   Quote from: sudgy on June 31, 2011, 11:47:46 pm

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3384
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2639
    • View Profile
Re: a fascinating puzzle game
« Reply #256 on: February 11, 2014, 03:40:54 pm »
0

Code: [Select]
http://xorballs.dskl.net/#3,end,[135,new:44cA],[134,Turing%20Machine:13714015417c918431732aq37641943744bl477481585635654],[133,Output%20Interpreter:00602403404J05413514G15A16cC18420623425H32733bK34438C40441742bK43448851555458D65G73674J75A76cC78480583484H854],[52,Recursion:32733737642aG43944aq477],[109,Turing%20with%20Rules:13618433635640J41B43044c845046747bm485517555574637665],[136,x10:00608410618920624928930638940448A50558B60568B70578B805844884],[82,Tape-4%20%28Delay%29:00704510918422723724725726727631732aG33aG34aG35aG36aG38B40bL41242843B44B45B46B481517577585705724],[16,init%20reset:217241254306337340354400443455487537540554635648677685815844],[132,Mini%20Turing%20Machine:02603604B10612114015621722bh24025432533K34435736638640143044bE45048150551553454657465566767bh685837841859875],[110,Interpreter:13717bt18622726by28631734641342143aV44148751752564765bn68573774c3785846854864874],[83,Tape-4-1:037040086487],[105,init%20reset%20copy:217241254306337340354400442455487537540554635648677685815844],[76,Turing%20Machine%20%28no%20instructions%29:02707615618425726bD27436738B44bA46648bk66767bj685725774],[117,1-%3F:30731C35bu38640A41D44bv48750951E53bw58560761F62bx685727737746754],[122,2-%3F:30731C35bz38640A41D44c048750951E53c158560761F62c2685727737746754],[31,Color%20Memory%20Direction:03704105414718622724aW26430634735540042aP46A48050554458562764aX664],[111,0-%3F:30731C35bp38640A41D44bq48750951E53br58560761F62bs685727737746754],[127,3-%3F:30731C35c438640A41D44c548750951E53c658560761F62c7685727737746754],[75,Color%20Memory:12614415430634H35G40044aV45050I54J555807827846],[72,Tape%20Head:02704613614bF15716623725530633734bP40041bC42bB43A45bD46450553bH54B55461766572774bQ765837845],[108,Turing%20Machine-1:037040086480585],[107,State%20Write%20Test:11714620721022424F306400413425448817846],[118,1-0:24728634G44A46B47I48756757I58563664B73I74I837846],[119,1-1:24728634H44A46B47I48756757J58563664B73G74I837846],[120,1-2:24728634G44A46B47I48756757G58563664B73G74I837846],[121,1-3:24728634H44A46B47I48756757H58563664B73G74I837846],[123,2-0:24728634H44A46B47I48756757J58563664B73J74I837846],[124,2-1:24728634G44A46B47I48756757G58563664B73J74I837846],[125,2-2:24728634H44A46B47I48756757H58563664B73H74I837846],[126,2-3:24728634G44A46B47I48756757I58563664B73G74I837846],[32,BR%20Partial%20Color%20Memory:04506416aU26aS27C28435645046348866aT67D68476aU846864],[25,Partial%20Color%20Memory:04506416aU26aS27C28435636aS37D38945046348856aT57E58B66aT67F68476aU846864],[33,YG%20Partial%20Color%20Memory:04506416aU26aS27E28435645046348866aT67F68476aU846864],[113,0-0:24728634G44A46B47I48756757H58563664B73H74I837846],[114,0-1:24728634H44A46B47I48756757I58563664B73J74I837846],[115,0-2:24728634G44A46B47I48756757J58563664B73J74I837846],[116,0-3:24728634H44A46B47I48756757G58563664B73J74I837846],[128,3-0:24728634H44A46B47I48756757G58563664B73G74I837846],[129,3-1:24728634G44A46B47I48756757H58563664B73I74I837846],[130,3-2:24728634H44A46B47I48756757I58563664B73I74I837846],[131,3-3:24728634G44A46B47I48756757J58563664B73I74I837846],[77,Tape:00604405415J21722630731aG32bI34641bG42bJ43644bF45A47648751553A55756bD57463764bO67572774bN75976bM78580581I84887bK884],[87,Turing-2:24526442D44745aG46565567484B875],[74,Write%20Test:01706611B14620721022423624A25630633C34D35F400413425434444454467817846],[73,Color%20Split:34C36737C38644A46A47F48754D56757D585],[79,Turing-1:00603904806610C11713D14716F17720721aG22623724aG25526727aG28631B34937540L43B46B479515534546574635644705784827846],[88,Mini-Tape:31734640G41543644bF457537555],[30,53-3:03704005443544B456837840854],[28,53-1:486837840884],[29,53-2:037041084485],[80,Tape-2:04C40B41E44648750751C585],[78,Tape-1:44B480585],[81,Tape-3:43C44B54E],[86,Tape-7:40G],[85,Tape-6:045084481585],[84,Tape-5:116174217221262286306325357360400419426437447463475489527535557561584805864]
I'm going to do a full writeup of how to operate it first, then in the next post a full writeup of how it works.

So, here all of the different functions you can do:

1. Advance the machine with the current instructions
       - To do this, all you need to do is input a ball from the left (of any color).  The internal state will advance by one, and a number of balls will go out the right side with how many times you've done this (the first time it outputs one, the second time it outputs two, etc.)

2. Change the tape
       - This is done by inputting from the top.  Commands to the tape are color coded:
                 Blue: Move tape left
                 Red: Move tape right
                 Yellow: Change the color of the cell in the head.  The next ball you input (from the top) is the new color of the cell.  So, inputting Yellow then Red changes the color to red.
                 Green: Outputs the color of the cell in the head.

3. Change the state of the head
       - This is done by inputting from the bottom.  The Green and Yellow commands work the same here for the state as they do in changing the color of the cell in the head.

4. Change the rules
       - This is done by editing the custom tiles 0-0, 0-1, 0-2, etc.  Blue is 0, Red is 1, Yellow is 2, and Green is 3.  If the current state is 2 and the current color is 1, it will go to 2-1 (I recommend you look at that tile to understand how the instructions work).  The instructions in here tell it to change the color to 0, move the tape left, and change the state to 3.  The blue brush on the right is changing the color to 0 (make sure the yellow gets out first so it reads the instructions correctly), the blue brush in the middle is move left (change it to red to move right), and the green brush on the bottom is change the state to 3 (make sure the yellow gets out first again).  By changing these three brushes in all of the num-num tiles, you can make your own rules.

5. Look at the tape
       - Input a blue from the right to see the 10 tiles on the left side of the tape.  Inputting red does the 10 tiles on the right side.

I think this is everything that needs to be done for it to qualify as being configurable enough.

EDIT: I forgot to mention, due to a minor design flaw, after performing actions 2 or 5 you need to input a green from the top before doing action 1 again.  Also, after performing action 3 you need to input a green from the bottom before doing actions 1 again.
« Last Edit: February 11, 2014, 03:55:35 pm by sudgy »
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

   Quote from: sudgy on June 31, 2011, 11:47:46 pm

David

  • Steward
  • ***
  • Offline Offline
  • Posts: 29
  • Respect: +7
    • View Profile
Re: a fascinating puzzle game
« Reply #257 on: February 11, 2014, 03:48:42 pm »
0

Does the transition matrix implement any particular function?

The state machine has at most 4 states, correct?
Logged

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3384
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2639
    • View Profile
Re: a fascinating puzzle game
« Reply #258 on: February 11, 2014, 03:57:33 pm »
0

Does the transition matrix implement any particular function?

Right now it does.

Code: [Select]
{{{1,'L',1},{2,'R',3},{3,'L',3},{0,'R',3}},
 {{2,'L',2},{3,'R',0},{0,'L',0},{1,'R',0}},
 {{3,'R',3},{0,'L',3},{1,'R',1},{2,'L',1}},
 {{0,'R',0},{1,'L',2},{2,'R',2},{3,'L',2}}}

It's this.  The state is the row, the color is the column.  Each triple is {new color, direction to move the tape, new state}.  It can easily be changed to whatever you want, however.

Quote
The state machine has at most 4 states, correct?

Yes.  One for each color.
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

   Quote from: sudgy on June 31, 2011, 11:47:46 pm

David

  • Steward
  • ***
  • Offline Offline
  • Posts: 29
  • Respect: +7
    • View Profile
Re: a fascinating puzzle game
« Reply #259 on: February 11, 2014, 04:13:26 pm »
0

Does the transition matrix implement any particular function?

Right now it does.

Code: [Select]
{{{1,'L',1},{2,'R',3},{3,'L',3},{0,'R',3}},
 {{2,'L',2},{3,'R',0},{0,'L',0},{1,'R',0}},
 {{3,'R',3},{0,'L',3},{1,'R',1},{2,'L',1}},
 {{0,'R',0},{1,'L',2},{2,'R',2},{3,'L',2}}}

It's this.  The state is the row, the color is the column.  Each triple is {new color, direction to move the tape, new state}.  It can easily be changed to whatever you want, however.

I understand. But that's not very easy to read. By "particular function" I meant something that's easy to explain like "addition". Is there anything special about this particular matrix?
Logged

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3384
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2639
    • View Profile
Re: a fascinating puzzle game
« Reply #260 on: February 11, 2014, 04:17:48 pm »
0

Does the transition matrix implement any particular function?

Right now it does.

Code: [Select]
{{{1,'L',1},{2,'R',3},{3,'L',3},{0,'R',3}},
 {{2,'L',2},{3,'R',0},{0,'L',0},{1,'R',0}},
 {{3,'R',3},{0,'L',3},{1,'R',1},{2,'L',1}},
 {{0,'R',0},{1,'L',2},{2,'R',2},{3,'L',2}}}

It's this.  The state is the row, the color is the column.  Each triple is {new color, direction to move the tape, new state}.  It can easily be changed to whatever you want, however.

I understand. But that's not very easy to read. By "particular function" I meant something that's easy to explain like "addition". Is there anything special about this particular matrix?

Oh, no, I ran it in another program and it was the first one I found that doesn't just endlessly go one direction (this one goes back to where it started, goes out, goes back, goes out a bit more, goes back, goes out a bit more, etc.).  I'm sure another set of rules would make something better.
« Last Edit: February 11, 2014, 04:21:56 pm by sudgy »
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

   Quote from: sudgy on June 31, 2011, 11:47:46 pm

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3384
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2639
    • View Profile
Re: a fascinating puzzle game
« Reply #261 on: February 11, 2014, 06:05:24 pm »
0

Alright.  Now for how the whole thing works.  This post is going to be loooooooooong.

[Any part called something like Tape-2 is something that is usually only simple manipulations of directions.  They are very simple and I won't discuss each one (it's easy to tell what they are).  There are a few exceptions, and I'll discuss those]

Tape Head:

I'm going to start with the Tape Head.  It's the first part I made and is somewhat simple.  It works like action 2 of the whole thing, and input and output are from the left.

All balls coming in go into the Write Test.  Basically, there is a switch in there that will stay the same if the ball coming in is blue, green, or red, but if the ball that came in was yellow, the switch changes.  Then, the next ball that comes in resets it but goes out the bottom instead of the right.  This is how it checks if the current ball is supposed to be changing the color of the current cell or not.

Blue, red, and green balls that come in go through the Color Split.  This makes blue balls go up and right, red balls go right and down, and green balls only right.

Before going on, I need to describe Turing-1 and Turing-2:

Turing-1:

For every ball that goes in the Tape Head (that isn't yellow), two balls go in here.  One from the top, then one from the right.  The color of the one from the top determines the direction of the second.  If blue is first, it goes down.  If red is first, it dies.  If green is first, it goes left.  This tile is there to send out the color of the current cell in the correct direction depending on the function.

Turing-2:

This is like Turing-1 but simpler.  A ball will go in from the left then from the bottom.  If the first was red, it goes up.  If not, it dies.

Now, back to the Tape Head.

I'm going to summarize what happens when a Green and Yellow ball go in:

Green: It goes through the Write Test and Color Split.  It hits a split, one of which goes into Turing-1 from the top, and the other goes into Color Memory from the left.  Color Memory is like the solution to level 53, but instead of going a different direction depending on the last color, it turns into the last saved color and goes down.  The current cell's color goes out the bottom, and back into Turing-1.  Because green went in first, it goes out of the left.  From there, it exits the Tape Head.

Yellow: It goes into the Write Test and stops.  The next input goes out of the Write Test to the bottom and goes into the Color Memory from the right.

A brief discussion of how Tape works is needed to understand what happens when a blue or red ball go in (I'll explain how Tape does all of this later.  You shouldn't actually be looking at Tape itself yet).  Each cell can be "initialized" or "not initialized".  Cells are initialized when they have been in the head before, and default as not initialized.  When a blue ball goes into the top of Tape (it will always be blue if it comes in the top), it means that it needs to go to the end of initialized cells and start giving states back towards the head.  The previous cell's state will come out of the right of Tape.  If a ball of any color goes into the bottom of Tape it means to take that color and pass its old color on until it hits one that is not initialized.

So, what Blue and Red do in Tape Head:

Blue: At Color Split, it goes up and right.  The one that goes up goes into the Tape up there from the top.  The output of that Tape (which is what it used to be) goes into the Color Memory from the right to set the state.  The one that went right from Color Split, through Turing-1, gets the current cell's color going down from Turing-1.  It goes into Mini-Tape (Mini-Tape is simple, just look at it) from the bottom.

Red: At Color Split, it goes right and down.  The one that goes right goes into Turing-2, and the current color comes out of it upwards.  It goes into Tape from the bottom.  The one that went down from Color split goes into Mini-Tape (which turns it blue and sends it into its Tape from the top).  The output from this goes into the Color Memory from the right.

And that's it for Tape Head.

Tape:

Tape is the most complicated of all of the tiles. I'll try to explain it.

When a blue ball comes in from the top, it first checks if the tile has been initialized.  If it has, it goes into the next tape from the top.  If it hasn't, it unitializes it again (because the act of checking initializes it) and goes out to the left.  This means it hit the end of initialized cells.

When something comes out from the left of a Tape in a Tape, it splits in three.  The one that goes left uninitializes, the one that goes right sends its current state out to the right (Tape-5 in this case always sends it out to the right), and the one that goes down sets the current state to blue.  This happens when the cell in it used to be the end of initialized cells, and this becomes that.

When something comes out from the right of a Tape in a Tape, it splits in three.  The one that goes up initializes (it turns green so that it gets stopped before doing things blue balls are supposed to do) (looking at it now, this might not need to be here...), the one that goes down sends its current state out to the right, and the one that goes right sets the current state to whatever the color is.  This is when the tape is moving towards the head.

When something comes in from the bottom, it splits.  The one that goes to the left turns yellow and checks if it's initialized.  If it's not initialized, it initializes it.  If it is initialized, it goes down and right and splits right before entering Tape-5.  The one that goes right here makes it so that the next thing that goes in Tape-5 goes left instead of right.  The one that goes up here sees the current color, goes through Tape-5 to the left, and goes into the next Tape from the bottom.  The one that goes to the right (the one from the beginning) needs to wait for the one that goes to the left to finish, so it goes through Tape-4 (Delay).  It should just be called delay probably.  The delay delays it for a while.  When it's done, it sets the color to whatever it is.  This is when the tape is moving away from the head.

That's how the whole Tape Head works.

Turing Machine (no instructions):

This is the Tape Head with states as well.  The Tape Head works the same, but if something comes in from the right, it does stuff with the state.  The State Write Test is the same as the Write Test (but without red and blue).  When green comes in from the right, it goes through the State Write Test fine, goes into Color Memory (which stores the state) from the left, exits from it down, and leaves to the right.  When yellow comes in from the right, it stops at the State Write Test, and the next ball goes down.  This goes into Color Memory from the right.

Mini-Turing Machine: (for lack of a better name)

If something comes in from the left it goes into the Turing Machine (no instructions) from the left and leaves to the left.  If it comes from the top it goes into the Turing Machine (no instructions) to the left, but leaves to the top.  A similar thing happens for right and down.

Turing with Rules:

Balls from the top and bottom go into the Mini-Turing Machine and come out normally.  Balls from the left turn green and split in two.  One checks the current cell's color and the other checks the head's state.  The state then the color (in that order) go into the Interpreter.  The Interpreter interprets the state and color into commands.  Commands that change the tape leave out of the right and go into the Mini-Turing Machine on the left, and commands that change the state leave out of the bottom and go into the Mini-Turing machine on the right.

Interpreter:

When the state comes in, it remembers the color (as a direction) by going into Color Memory Direction from the right.  When the cell's color comes in, it goes into Color Memory Direction from the left and goes the direction of the state.  The directions lead to the num-? tiles.  Commands for the tape go out the right and commands for the state go out the bottom.

num-?:

When the cell's color comes in, it filters by color and goes into the num-num tiles.  Commands for the tape go out the right and commands for the state go out the bottom.

num-num:

When a ball comes in from the left, it turns it into commands.  Commands for the tape go out the right and commands for the state go out the bottom.  On the right is the new color for the tape, in the middle is the direction to move the tape, and to the bottom is the new color of the state.

And, finally:

Turing Machine:

Balls from the left split.  One goes into Turing with Rules, while the other goes into a solution for 57 (Recursion), which leaves out to the right.  Balls from the top and bottom go into and from Turing with Rules normally.  Balls from the right go through Output Interpreter which just turns blue into [B,G,B,G,B,G,B,G,B,G,B,G,B,G,B,G,B,G,B,G,R,R,R,R,R,R,R,R,R,R] and red into the same with B and R switched, and those sequences go into Turing with Rules from the top.


So there you have it.  I don't think I'm too good at explaining this stuff, so sorry if you don't understand..
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

   Quote from: sudgy on June 31, 2011, 11:47:46 pm

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3384
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2639
    • View Profile
Re: a fascinating puzzle game
« Reply #262 on: February 12, 2014, 08:24:11 pm »
0

One other thing, because apparently this Turing Machine is universal, and because you could easily make it with mine, xorballs is Turing complete.
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

   Quote from: sudgy on June 31, 2011, 11:47:46 pm

David

  • Steward
  • ***
  • Offline Offline
  • Posts: 29
  • Respect: +7
    • View Profile
Re: a fascinating puzzle game
« Reply #263 on: February 15, 2014, 07:09:47 am »
0

I've been convinced from the very beginning that Xorballs is Turing complete, but I'm not convince that the proof is quite there yet. The wikipedia article isn't clear on whether the 2,3 Turing machine is proven universal or only conjectured, but it also says "The (2,3) Turing machine also requires an infinite non-repeating input" which your machine doesn't have.

That said, it's still very cool that you made some kind of Turing machine. Congratulations again. I admit I haven't read the entire description because it's still quite hard to follow, but I have a reasonable idea of how it should work. If you want more challenge, you could try making a state machine with an arbitrary number of states, or one that you can program by encoding the states in the initial input :).
Logged

David

  • Steward
  • ***
  • Offline Offline
  • Posts: 29
  • Respect: +7
    • View Profile
Re: a fascinating puzzle game
« Reply #264 on: February 23, 2014, 02:46:08 pm »
0

Another nice challenge that I didn't get around to adding to the game is to create a prime number generator.
Mine takes any color ball from the left and outputs either a blue or a red ball on the right. The sequence it outputs is:

blue (2 is prime)
blue (3 is prime)
red (4 is not prime)
blue (5 is prime)
red (6 is not prime)
etc...
Logged
Pages: 1 ... 9 10 [11]  All
 

Page created in 0.094 seconds with 21 queries.