DIGI-COMP I - A Computer ?

DIGI-COMP I is claimed to be "the first real operating digital computer in plastic".

We agree about the "plastic" part, and won't argue about the "first", but :

Is it really a "computer"?

On first look surely not: no display, no keyboard, only 3-bits of memory.

Even in 1963 nobody would've called it a computer. At that time there already were so many "real operating digital computers", that IBM had to order the chaos with its SYSTEM/360.

As Crocodile Dundee would've said:

"Ha ha, that's not a computer."		"THAT's a COMPUTER!"
	<->

Could it be turned into a computer?

Whenever we like to rehabilitate some crazy retro-computing device, we ask: "is it Turing-complete"?
That means: can it do the same calculations as a Turing machine? If yes, it can do everything a modern computer can do.

But again: DIGI-COMP has no infinite tape, no read/write head, and only a 3-bit state memory. Not a Turing machine!

Things may change when we allow DIGI-COMPs capacity to be expanded. So we separate its "construction" from its "capacity", and only ask if the construction is Turing-complete.

So we break down the big question into three smaller ones:

1. Can you build a Turing machine with a finite state machine?
2. Is DIGI-COMP really a finite-state machine?
3. Could DIGI-COMP be extended with more flip-flops and bigger combinatoric logic without changing the construction? Unlimited?

 If all are "yes", an extended DIGI-COMP could emulate every computer.

1. Can you build a Turing machine with a finite state machine?

I think so. If you have a Turing machine with 2^s  states and a "tape" with 2^t binary cells, its overall state consists of

   s (do encode the "current state")
+ t (to encode the "current tape position under the read/write head")
+ 2^t  (current 0/1 state of all tape cells)

= n Bits.

On each "clock" the combinatory logic calculates a new machine state, a new tape position and new tape cell content.

2. Is DIGI-COMP really a finite-state machine?

We've shown already that DIGI-COMP implements a Medvedev state-machine.

DIGI-COMP implements the Canonical Normal Form (CNF), the logic is a "Sum of Produts". 

Implementation is:

• LOGIC RODs = AND gate inputs = "min terms" = rows in function truths table.
• Optional inverters to AND gates = Tubes on T/F pegs on flip flop sliders
• CLOCK RODs and CLOCK PEGs = AND gate outputs = OR term inputs = "max terms"
• Special condition: every OR is realized with a "CLOCK SET ROD" and results in a flip flop "SET" operation.
  To CLEAR a flip flop, a 2nd inverted AND term for the "clear clock rod" must be programmed.

Only problem: the logic has not enough AND and OR terms. For 3 bits, DIGI-COMP would need 2³ pairs of LOGIC RODs for AND gates and also 2³ clock pegs for each flip flop to OR the 8 AND terms.
But it has only 3 pairs of logic rods/clock rods.

In general: a state-machine with n bits should have an AND-OR network for 2ⁿ terms.

Luckily the problem of "not enough rods" is no additional hazzle, it is handled in the next question:

3. Could DIGI-COMP be extended with more flip-flops and bigger combinatory logic without changing the construction?

This means: can we add more flip-flops? Can we add more AND terms (LOGIC RODs) and more OR terms (CLOCK PEGs)?

Luckily DIGI-COMP has a clean construction, so this can be answered "yes" with confidence.

1. Flip flops can be stacked vertically ad libitum.

2. More LOGIC RODs, LOGIC PEGs, CLOCK RODs and CLOCK PEGs can be added on the flip flop sliders horizontally. We just make longer flip flop sliders .

This can be repeated endlessly ... you understand what I mean:

 So "yes", DIGI-COMP can be scaled up.

It is!

So an extended DIGI-COMP I could execute a Turing machine of arbitrary size, that's the definition of a computer!

However, the result is purely theoretical: to execute a small computer with - say - 1 KByte of memory, you'd need at least a Turing machine with a tape length of 8192 cells. To build that with a DIGI-COMP following the "instructions" above, you'd need 2⁸¹⁹² AND LOGIC RODs to test all possible combinations. Thats 10²⁴⁶⁵ rods and we have only about 10⁸⁵ atoms in the universe! 

But hey: that machine could run many programs in just one clock cycle, because the end state of every possible halting program is already encoded in that giant combinatory logic. That logic matrix would resemble Borges' "Library Of Babel". But its of finite size, so who cares?

Clearly we should think about optimized logic tables first.