Make a turing-complete computer in stock KSP

[ItCameFromDuna]

Here's a delightfully nerdy challenge for you geniuses: build a computer (or at least a proof-of-concept) that is Turing-complete in stock KSP (DLC allowed). Here's the wikipedia article on Turing-completeness to get you started: https://en.wikipedia.org/wiki/Turing_completeness. Basically, a computer capable of computing anything commutable.

Numerous games, from Minecraft to Magic the Gathering have proven to be Turing-complete, so I have a question: is KSP? Could you build a complex marble run with mechanical logic gates? Misuse the KAL controller? There are numerous approaches that might work. I'm curious to see what you all come up with!

[camacju]

If I remember correctly, you can chain KAL controllers, and make combinational logic out of that. Not sure how you'd implement latches however

[Pds314]

10 hours ago, camacju said:

If I remember correctly, you can chain KAL controllers, and make combinational logic out of that. Not sure how you'd implement latches however

hmm... RS NOR could be made with a hinge and two  continually running Junos as input wires, and a third which the hinge conditionally blocks as an output wire. Inverted output could be a fourth Juno.

Wire multiplexing and repeaters can be achieved by using one Juno to unblock an array of Junos all at once with a plate or comb structure, with the mechanism springloaded by the strength of the hinge to go back to normal if the input gets blocked.

An AND gate can be made using two hinges or pistons to block a Juno and then having two blockable input Junos.

A NOT gate would just be a Juno that blocks another Juno using a springloaded hinge. Two of these could also be used to make a latch.

An OR gate would be pretty trivial. Two Junos facing at the same springloaded piston/hinge and a third that is unblocked when force is applied.

There could be multiple types of more and less precise clocks, from servos that periodically block Junos, to KALs and more, with a NOT gate feeding into itself (think a sprinkler blocking mechanism) or a trio of NOT Gates in a loop also being an option.

One issue I can see is that  the write wire for RAM would either need an awful lot of wire multiplexing or a more complicated mechanism so that only the active address can block the beam and then you only need a repeater once every 10 meters.

One solution I can think of is to do ram writes the same way as multiplexers. Right, have a bunch of / all of the addresses all open at once and only the one that the addressing logic picks gets written to. Basically using a big shield thing to stop the RAM from being written while the addressing logic is being set.

Now, as to RAM addressing logic itself, this is a bit tricky. We want basically want each bit of the address to eliminate half the possibilities leaving only one left. I would argue that the easiest way to do this is to push a bunch of increasingly stretched out checkerboard-shaped blockers out of the way. The first being one address wide per checkers square, the second being 2, the third being 4, the fourth being 8, then 16, 32, etc.

There would be a tradeoff here in terms of speed and complexity vs address size. Very deep checkerboard blockers would take longer to move up and down or rotate out of the way, so it probably pays to make your ram somewhat compact. Also you probably want to put the blowers for the addressing system near the middle of the RAM for stability.

 

One really nice feature of all this is that because engine thrust rays are noncolliding, overlapping wires is trivially easy. This might be good for displays, ribbon cables, GPUs, etc.

 

Now that I think about it some more, if you use cheats, then it might generally be better to use the smallest rockets you can rather than a big bulky Juno except in applications where high thrust is needed to quickly move something bulky. And KAL overclocking can actually fix the thrust issue. So maybe ant engines or something set to infinite fuel are preferable to Junos.

 

If we want a design that works in zero G, one option would be to use two springloaded NOT gates as the basis for the latch.

If we want a design which can operate under acceleration or rotation, then making stronger springloading force and very light blockers might help. In principle, I don't see any particular limit on the G tolerance in any given direction that a NOT gate can take.

 

In terms of constructing other gates, a compact XOR gate might be able to be made using a servo and two engines coming from input wires, with a third engine in the middle. The servo would be springloaded to go toward the middle, blocking the thrust from the third engine, and if both or neither input wire is active, would stay there. Otherwise, it would move to one side, allowing the thrust from that engine to go through. One issue here is that the timing of the two inputs needs to be perfect or it will create a short pulse when switching from neither to both. But that's pretty much true of all XOR gate designs because that's an intended behavior of XOR gates.

If you want to clean up the signal or add a deliberate delay, one option would be to have low power engines, heavy blockers, a long travel distance, and light springloading on a repeater. This will basically average out the signal over a longer period so it can ignore short on/off pulses.

 

Edited November 10, 2021 by Pds314

[Ultimate Steve]

I'm not a computer guy, so the only measure of Turing completeness I can understand is the overly literal tape and head model of the actual turning machine itself, so I have been thinking about how I would build it.

I don't think this will end up using any KAL controllers, except in self contained always-looping components, as unless I am missing something, they cannot be triggered by in-game events.

As such, my idea is pretty much entirely mechanical.

I am thinking of having the "tape" be a long line of structural pieces with a bistable "flipping" mechanism. The data would be binary encoded, if the mechanism is on the left, it is a 0, if its on the right, its a 1.

This would be read by shooting two engines at a target on the flipping mechanism. Depending on the mechanism, the target would block one of the engine plumes. On the other side of the target there would be two paddles, which would actuate and trigger the program.

In order to write to the tape, a mechanism controlled by the program would uncover one of two "flipping" engines and would set the tape cell to right or left.

The program itself could be done any number of ways, and is probably the most complicated part, but the easiest one for me to wrap my head around would be to do something like the following marble machine:

The machine would drop a cylindrical or round fuel tank when directed to, and it would go through the flippers, and at each "exit" there would be an instruction or combination of instructions. Like for example, the fuel tank could fall onto an arm that activates the "set the current position to 1" or "set to 0" or "go right 1" or "set to 0 then go right 1" or "Go left until you cannot go left any more" or something, and the magic would be in the arrangement of the flippers, which would be different for each program. Flippers, because, it would allow for the program to branch depending on what the previous cells did.

The right/left actuation could probably be done with a massive gear beneath the tape, but I have not gotten that far yet.

Here is a proof of concept tape segment and part of the reader/write head:

Edit: Forgot to mention that this would require the infinite fuel and ignore max temperature cheats unless it is well designed.

 

Edited November 10, 2021 by Ultimate Steve

[Ultimate Steve]

Update:

Writing to the tape is now possible, although it involves user input at the moment (turning the servo on the right). Without any input it will revert back to non writing mode so once I add the automated input method I can keep the current hardware and drop the servo strength to 0.

[Pds314]

Thinking big here, one of the concerns I've having is just how truly terrible the part count will be. I doubt practical, addressible RAM can be under 10 parts per bit, with multiple of them being engines or something.

I originally thought it might be possible to do something like an 8 bit CPU because this stuff would be pretty simple to actually copy and paste all over in the editor and implement pretty sophisticated computer architecture that way. But I'm thinking that would be >10000 parts or some nonsense. Needless to say, that might work with Minecraft but not so much here.

I think in terms of practical CPUs, saying we're gonna need it to be a RISC machine is an extreme understatement. I'm not even sure a well-fleshed out 4-bit machine is doable.

Edited November 10, 2021 by Pds314

[Ultimate Steve]

12 minutes ago, Pds314 said:

Thinking big here, one of the concerns I've having is just how truly terrible the part count will be. I doubt practical, addressible RAM can be under 10 parts per bit, with multiple of them being engines or something.

I originally thought it might be possible to do something like an 8 bit CPU because this stuff would be pretty simple to actually copy and paste all over in the editor and implement pretty sophisticated computer architecture that way. But I'm thinking that would be >10000 parts or some nonsense. Needless to say, that might work with Minecraft but not so much here.

I think im terms of practical CPUs, saying we're gonna need it to be a RISC machine is an extreme understatement. I'm not even sure a well-fleshed out 4-bit machine is doable.

Yeah, anything beyond very simple is probably going to require NASA levels of computing power. I will consider my machine a success if I can write a "program" for it that can add 2+2 (and other 2 bit binary numbers by association) and I'm already looking at several hundred parts just for that. 

[Pds314]

6 minutes ago, Ultimate Steve said:

Yeah, anything beyond very simple is probably going to require NASA levels of computing power. I will consider my machine a success if I can write a "program" for it that can add 2+2 (and other 2 bit binary numbers by association) and I'm already looking at several hundred parts just for that. 

Maybe manipulating the the loaded vessel position relative to the root part of multiple crafts to physics unload unnecessary components of the machine in separate crafts could extend the possibilities? No need to completely unload them. Just make it so the game isn't spending lots of effort calculating physics for, say, a block of RAM that's currently not in use. It will still render it but it won't need to do physics for it.

Edited November 10, 2021 by Pds314

[Ultimate Steve]

 

Last update for a while, I have a class to go to.

It now has a few reliability improvements to the read/write head, improvements to the memory (slight brakes, enough so that it can't spontaneously bit flip, but slight enough that the engines can still change it) and most notably, the tape can now be moved back and forth so different cells can be read or written to.

I'll have to make something that will ensure that the gear only moves 48 degrees each time it is actuated, which I'm thinking will be difficult. Then I have to make the gear and write head actuatable by mechanical means, and then I have to actually make it programmable.

But good progress in the few hours I spent on it.

[Ultimate Steve]

Update from class: The marble machine idea for programming is out. I have a new idea, the chute and state idea.

 

Basically, there are a certain number of "states" or mini programs or functions if you will. Each state will have a 0 or 1 sub variation. There will be two ramps (one for 0, one for 1), with a number of trapdoors beneath them. When the current cell is read, a ball will be sent down the 1 or 0 chute depending on if the cell is a 1 or 0. It will then fall down the open trap door (the others will be closed).

Each set of two trap doors corresponds to a program state. When a ball falls down the trap door, it will strike a number of levers that will mechanically execute various instructions. These instructions are:

• READ - reads the current cell and will drop a ball down the 0 or 1 ramp depending on the value of the cell.
• LEFT 1 - moves left 1 cell.
• RIGHT 1 - moves right 1 cell.
• SET 1 - set the current cell to a 1.
• SET 0 - set the current cell to a 2.
• FULL RIGHT - go right until a stop block is met.
• FULL LEFT - go left until a stop block is met. These two are a convenient way of not having to do a lot of right or left 1 commands and are not needed but are here to save on time and part count.
• GO TO STATE: Changes the "state" of the program, closing all trap doors and then opening the two trapdoors corresponding to the desired state.

Basically, every "state" is a mini program which will take the value of the current cell and will then execute commands before possibly switching states and then triggering the next read command.

 

If I am right, I can do my 2+2 program with a 10 cell long strip and 5 or 6 states.

 

Of course that was hard to say, and easier said than done.

[Ultimate Steve]

Latest update, currently on version C10.

I have added a mechanism that only allows the tape to rotate 48 degrees ish, or one rotation. It works by using a second gear that is rotation limited to about plus or minus 50 degrees. I can tweak this if I find that it oversets or undersets in one direction or the other (currently oversetting going left so I will tweak that limit). However, the issue with not being able to go past 48 degrees is that you can only go one tape position. To fix this, this "Limiting gear" is toggleable. It is attached to an arm made of flexible parts, and is only engaged with the main gear when an engine is on, pushing it upwards enough for it to engage. When this engine is off, it falls away into a catcher designed to reset it to a neutral zero degree position.

To go, say, one to the right, first the engaging engine will fire, raising the limiting gear up. Then, the engine that rotates the main gear to the right will turn on. The gear will rotate, but only as far as the limiting gear will allow, which is equivalent to one tape cell. Then, the rotation engine will be turned off. After that, the engaging engine will also turn off, lowering the gear back down, resetting it.

This mechanism also greatly simplified my proposed "FULL RIGHT" and "FULL LEFT" actions, as if you just drop the limiting gear out of the way, you can spin the wheel to your heart's content.

It is still not very reliable, I will work on that. It works moving the tape one way but not the other at the moment, but it should be a pretty easy fix, I should just need to more harshly limit the rotation of the limiting gear in one direction.

The really good news, though, is that every operation (besides go to state which can't be added until I have the rest of the machine) is currently implemented and can be controlled by toggling on and off engines. Well, technically read toggle isn't there yet but it is really easy to add. This is good because the machine itself will activate these operations by blocking engine plumes.

[dnbattley]

Oh my! I've been thinking about this for a while now and have some ideas using the KAL approach, and this is all the motivation I need to dust off that prior work and contribute to this.

What are the outcomes we need to achieve to fully realise this: if we can generate and link AND, OR and NOT gates is that enough?

[ItCameFromDuna]

2 hours ago, dnbattley said:

What are the outcomes we need to achieve to fully realise this: if we can generate and link AND, OR and NOT gates is that enough?

I'd say AND, OR, and NOT (or go with a NAND so you just need one gate) and some proof-of-concept of randomly-accessible memory (probably just a flip-flop or something) or some equivalent would qualify. Obviously I'd love to see a functional computer though.

[camacju]

2 hours ago, dnbattley said:

What are the outcomes we need to achieve to fully realise this: if we can generate and link AND, OR and NOT gates is that enough?

You can achieve any combinational logic circuit with NOT gates and at least one of AND and OR. This is called NAND logic or NOR logic. Additionally, you can implement latches just using combinational logic gates and a feedback loop, so really all you need to do is build a NAND/NOR gate. For example, here is a RS-NOR latch:

From a NOR gate you can make all other gates:

NOT A = A NOR A
A OR B = (A NOR B) NOR (A NOR B)
A AND B = (A NOR A) NOR (B NOR B)

et cetera

 

[Ultimate Steve]

Ok, so good and bad news:

Good news, I've been working on the program memory.

This is the "chute and state" mechanism as described above. When a RAM cell is read from the strip, it will release an FL-T200 tank down either the right or left side depending on if the cell is a 1 or a 0.

Depending on what state the program is in, one of the trapdoors will open. Currently, you can see that door number 2 is open (the structural panel by the kickback booster). The fuel tank will fall down this open hole and on the way down will strike a number of levers corresponding to actions, which could be thought of as lines of computer code. These levers are attached to shafts, shown on the right side of the machine. These shafts will rotate when the levers are struck, and the movement will be transferred to the rest of the machine, executing the instructions.

Each set of 2 shafts corresponds to one of the 7 instructions, so programming can be changed via deleting or adding levers to each state. It could execute all 7 commands in one state, but in practice it won't, so this poses a problem as the fuel tank can start going fast enough to be destroyed. This is what all of the wings are for. They rotate on a clock controlled by a KAL loop, to slow down the fuel tank and allow time for the commands to execute. Currently it is on a 5 second clock but I will probably need to slow that down. Each one of the wing panels also has a shaft coming off the right hand side although these won't be used to transfer anything, it was just a convenient place to put it.

The bottom lever will change the state and also toggle the reading of the current cell (the read and state commands have been merged). So when the fuel tank reaches the bottom, it will close the trapdoors by shoving the kickback booster forwards, and will open one of the other trapdoors (each one has a twitch engine to open it), so that the next fuel tank will take a different path down the chute.

So this block of program memory can hold 8 states, and each state can execute up to 7 instructions, but with no repeats. This is a problem, which leads me to the bad news: A Turing machine should be able to go any number of spaces right or left, and because my move 1 commands cannot be repeated easily, the design as it stands wouldn't meet the criteria for turing completeness. So, I will have to add some mechanism that can move left and right an arbitrary amount of spaces. I have an idea for how to go about this, but it won't be elegant.

More bad news, this block of program memory is 360 parts. The rest of the machine is at around 200 parts. Seeing as I have so much more to add, it will probably end up at over 1000 parts.

The reliability isn't being great either.

 

Anyway, I wrote up some "code" for the 2+2 program.

Spoiler

Initial state for the strip:

 

S 0 1 0 1 H 0 0 0 S

The bolded number indicates the starting position of the read head.

 

The S's are stop blocks, which act as the start and stop points for a program, so I don't have to always say "Go left 5 spaces" and "Go left 4 spaces", I can just say "Go left until you hit a stop block."

The H is a halt block, which will block both read heads, so the program will halt when the halt block is read.

The first 2 numbers, 0 and 1, are the first number to be added. The 1s place comes first, followed by the 2s place. This is repeated for the second number to be added, also 0 1. So the stored values are 2 and 2.

The three right hand zeros are where the resultant number will be stored. To simplify the program, it is written the opposite way. The 4s place comes first, followed by the 2s place, followed by the 0s place.

 

So without further ado, the code itself:

 

The code starts with the only manual input, the execution of the only read command.

Note, go to state implies that the current cell will be read.

 

State 1 - Read the 1s place

• Read
• If 0:
  • Right 1
  • Go to state 2
• If 1:
  • Set 0
  • Full Right
  • Go to state 3

State 2 - Read the 2s place

• If 0:
  • Right 1
  • Go to state 1
• If 1:
  • Set 0
  • Full Right
  • Left 1
  • Go to state 4

State 3 - Add the 1s place

• If 0:
  • Set 1
  • Full Left
  • Go to state 1
• If 1:
  • Set 0
  • Left 1
  • Go to state 4

State 4 - Add the 2s place

• If 0:
  • Set 1
  • Full  left
  • Go to state 1
• If 1:
  • Set 0
  • Left 1
  • Go to state 9

State 5 - Add the 4s place

• If 0:
  • Set 1
  • Full Left
  • Go to state 1
• If 1:
  • Left 1
  • If this happens you have somehow gotten 3+3 to equal more than 7 so the machine is probably broken

Basically, the program will first read the 1s place of the first number. If it is a 0, there is no work to be done so it moves on to the 2s place and reads that. But if there is a 1, and a 1 needs to be added, it sets that 1 to a 0 (saying to the program's future self that it has already been done) and goes over to the 1s place of the third number. If it is 0, it adds 1 and returns to the beginning. If it is a 1, the program sets it to a 0 and goes over to the 2s place. If that is a 0, fantastic, 1+1=10 so it sets it to a 1 and goes back to the beginning. If it is a 1, it carries again over to the 4s place, which is always going to be 0 unless something really bad has happened.

The 2s place works similar, except that it skips to the 2s place of number 3. After number 1 is read it goes to number 2 and repeats the process. This goes on until both numbers 1 and 2 are  all zeros. At this point, the program would go right one more space and try to read the halt block, stopping. The answer would be read from the tape by eye, and if it works, it should be the sum of the two input numbers.

 

End state (hopefully):

S 0 0 0 0 H 1 0 0 S

 

This can add up to 3+3=6. In order to add another binary digit, two more states and 3 more tape cells are needed, so the current 8 state machine could be programmed to add up to 7+7=14. Adding another state could get it to 15+15=30.

 

 

One problem though is that the program has a go left after a full right, so I'd have to find some way to suspend the go left until the full right has been confirmed to be completed. That is easier said than done.

 

 

 

 

 

 

 

[Ultimate Steve]

Here are some not gates and repeaters I've been working on to transfer the signal from the program memory to the machine:

 

[dnbattley]

Well... I think it's fair to say that I had a good evening:

 

[Ultimate Steve]

Another update. I have created a mechanism which can semi reliably loop an action an arbitrary number of times. This will replace the "Right 1" and "Left 1" actions with arbitrary "Right N" and "Left N" actions. It is currently set up for N to be between 1 and 4, but it can be arbitrarily expanded if your computer has enough power and you are willing to tune it.

So there is a stack of fuel tanks. A hopper will be built to funnel more in, although my 2+2 program will probably not need the capacity. To trigger this machine, the program memory will unblock 1 of the 4 Thud engines off to the left for a short period of time. This will shove a fuel tank over into the second shaft, using an arm which will then retract. This fuel tank will then block a set of engines. The lack of an engine plume will be detected by a not gate and a 4 to 1 funnel which will send a signal to the mechanism that needs to be looped, in this case, the move right and move left mechanisms (not attached yet). The mechanism will send a signal back when it is finished doing what it needs to do, which will then retract the trap doors beneath the fuel tank and immediately snap them back in, allowing the fuel tank to advance one position, where the exact same thing happens again.

When the fuel tank falls out of the bottom of the machine, it will stop looping, so the higher the fuel tank starts, the more times it will loop.

Unfortunately it is over 150 parts and I need 2 of them.

Some good news, though, that is every major component unless I decide to redo the program memory to use engine sensors instead of levers.  Now I just have the very daunting task of improving reliability and connecting it all together...

 

[dnbattley]

My logic board craft file is now posted here: https://kerbalx.com/dnbattley/Logic-test-3

[Ultimate Steve]

I spent several hours today trying to connect the looping mechanism to the main machine, and I did get it to work one time, but there is just so much to go wrong that it is very, very unreliable. The looping machine itself is alright now that I've had time to tune it, but the two machines are not playing well with each other.

The main culprit is the gear that limits the rotation of the main gear to 48 degrees. It is incredibly inconsistent, and the sequence of events required to lift it into position, wait for it to turn, release it, wait for it to settle down, and then trigger the next loop is too complicated and variable to reliably be done with my current repeaters and other components.

I think I might redesign the entire tape actuation system to use a piston system instead of a gear system. However, to make this work I might also have to redesign the RAM itself, so this would probably be enough to designate this as the Mk2.

[dnbattley]

I've had a busy, but productive weekend, and proudly present:

 

[dnbattley]

@TriggerAu: this one's for you ☝️!

[AtomicTech]

On 11/14/2021 at 7:06 AM, dnbattley said:

I've had a busy, but productive weekend, and proudly present:

 

Very cool!