I built the smallest turing-complete combinator computer
Posted: Mon Mar 13, 2017 11:30 pm
by 321freddy
I've seen alot of these combinator computers already but I think they all have one issue: they're huge and therefore pretty impractical.
So I started from scratch and built this tiny computer which completely fits inside the range of just one substation
Tell me what you think of it or if you need further explanation
The program itself is written inside the constant combinators on the left. Basically every module is connected to one big circuit network.
The instructions in a program consist of multiple signals which are added to the main circuit network when the program clock calls that instruction.
Every register and operation has it's own unique signal. The decoder checks for signals with values larger than 1G/smaller than -1G to determine what to do with the incoming signals.
Instructions
Every instruction contains the following signals:
X being the line number in the program (starting with 1),
C being the relative number of lines that should be jumped to reach the next instruction,
T being the amount of ticks the clock should wait until it calls the next instruction
And depending on the instruction some the following signals:
one register/input signal/constant for the instruction with a value of 1.5G + constant,
one target registers or operation with a value of -1,5G
Operations:
Add a (input-)signal to a register (min. 4 ticks):
This adds the value of the iron signal to register A. Iron could be an input from outside.
Add a register to another register (min. 4 ticks):
This adds the value of register A to register B.
Jump be C+I lines if the condition is true, else only jump by C lines (min. 4 ticks):
This jumps 2 lines forward if register G is 1 (which holds the result of A > B)
Reset/Initialize registers (new values are negated, min. 5 ticks):
This sets A to 1 and B to 2.
EDIT: How to add more program memory: http://imgur.com/a/X6nqq
EDIT2: Of course it doesn't calcualte all the fibonacci number
Re: I built the smallest turing-complete combinator computer
Posted: Tue Mar 14, 2017 7:10 am
by MrNardKing
I got a lot into building redstone computers in Minecraft but I don't know how i can use these circuits in Factorio yet. This post deserves more attention , any tips on learning about these? PM me if you want to hear about the redstone computer
Re: I built the smallest turing-complete combinator computer
Posted: Tue Mar 14, 2017 12:29 pm
by 321freddy
I tried building redstone computers myself but I never finished them because they all were in binary and really gigantic so building anything close to usable would just cause too much lag...
If you want some practical examples for combinators you can take a look at the wiki cookbook: https://wiki.factorio.com/Circuit-network_Cookbook
The Circuit network tutorial introduction is also very important if you want to build more advanced circuits: https://wiki.factorio.com/Combinator_Tu ... troduction
Re: I built the smallest turing-complete combinator computer
Posted: Tue Mar 14, 2017 8:23 pm
by MrNardKing
Thank you! I'll check those out today and see if i can build an ALU for starters
Re: I built the smallest turing-complete combinator computer
Posted: Fri Mar 17, 2017 7:28 am
by ssilk
While cleaning up this board I made this temporary sticky.
Re: I built the smallest turing-complete combinator computer
Posted: Thu Mar 23, 2017 2:42 pm
by Gertibrumm
ssilk wrote:While cleaning up this board I made this temporary sticky.
really you should create a subforum "factory controllers" or "factory computer", not sticky, this creation is nice but hardly usable -> I consider it unfinished
there are a couple of creations scattered throughout the forums which would fall into this category.
I would also add ASIC equivalent "factory controllers" into this category which might not be turing complete but execute specific comands.
Re: I built the smallest turing-complete combinator computer
Posted: Wed Mar 29, 2017 4:05 am
by ssilk
Well, I splitted the Show your Creations already in many boards (sometimes I think it's too much, sometimes I think it's just right), so I'll not make another board for such.
And it's temporary, I don't see a problem, cause it want to point to this not for using it but for discussion. But if you insist I can remove it sooner.
Re: I built the smallest turing-complete combinator computer
Posted: Wed Jun 07, 2017 1:22 am
by UpTide
Amazing! Mostly impressed by your miniature decimal display!!!
Re: I built the smallest turing-complete combinator computer
Re: I built the smallest turing-complete combinator computer
Posted: Sun Oct 22, 2017 5:56 am
by TimTravel
Looks really cool! Is there an updated version for 0.15?
Re: I built the smallest turing-complete combinator computer
Posted: Sun Oct 22, 2017 7:54 pm
by 321freddy
TimTravel wrote:Looks really cool! Is there an updated version for 0.15?
Combinators haven't changed so it should still work the same. You can import the bluepint strings to 0.15 using the foreman mod.
Re: I built the smallest turing-complete combinator computer
Posted: Sun Feb 16, 2020 4:51 pm
by judos
Short update. I migrated the blueprint to 0.17 (also the blueprint string was actually inofficially from the foreman mod. So now this string is importable into 0.17 and probably most future versions:
, any tips on learning about these? PM me if you want to hear about the redstone computer 
(