History and theory of computers

Here you can find literature on the history of early computers and theoretic background on how they work.

Contents

1       A brief history of computers

2       Semiconductors, doping and transistors

3       Logic gates as the building block of programmable computers

3.1        Digital circuit simulation

3.1.1         An interactive virtual CPU from logic gates in Logism by R.J. Astwick

3.2        How the CPU works as part of the von Neumann architecture

1       A brief history of computers

At all times have humans created tools and machines that were designed to make life easier. The next step was to create machines that could react to input by changing state, thereby being able to accommodate for different situations and tasks. What dictates the nature of the machine’s state based on the the input can be called a program. First programs were completely implemented in hardware, as illustrated by ancient programmable analog “computers” such as Ismail al-Jazari’s astronomical castleclock which featured a reprogrammable length of the day (1206 AD). The extent of programmability extended Building on calculating machines by Wilhelm Schickard (1623) and Blaise Pascal (developed between 1642 and 1649), Charles Babbage and his son Henry conceptualized the first universally programmable (Turing-complete if it had infinite storage capacity) mechanical computer, the Analytical Engine (1888-1906). They planned to use punched cards for storage. Punched paper tapes had been invented by Basile Bouchon in 1725 to control the patterns woven by a loom and in 1804/1805 Joseph Marie Jacquard had demonstrated a mechanism that used punch cards to fully automate loom operation. In 1835, Semen Korsakov presented devices for the mechanical readout and comparison of information stored in punched cards to the Imperial Academy of Sciences in St. Petersburg.

In 1906, the automatic Feed Tabulator type 1 of the Electric Tabulating System by Herman Hollerith (produced by The Tabulating Company) was extended by a control board allowing functions to be encoded using jumper wires for that year's U.S. census. After Herman Hollerith sold his company, the resulting company was renamed to International Business Machines Corporation (IBM) and his machine was sold under the name IBM type 090. Further contributions came from L. Cobrie and Wallace J. Eckert who pioneered complex calculation on calculating machines. The Z3 by Conrad Zuse from 1941 was the first universally programmable electro-mechanic computer whose switches were mechanical relays, but it lacked the conditional branching of a Turing machine. To increase speed and prevent wear-out, vacuum tubes were introduced as electric switches in later computers. The first programmable electric digital computer was the Colossus built by Flowers in 1943. The first Turing-complete (if it had infinite storage capacity) computer of this type was the Electronic Numerical Integrator and Computer (ENIAC) that was completed in 1946. The first Stored-Program Computers (i.e. controllable by a program stored in a main random access memory (RAM) were IBM's Selective Sequence Electronic Calculator (SSEC), built under the direction of Columbia Professor Wallace Eckert and his staff in 1946-47 and the Small-Scale Experimental Machine (SSEM) or “Manchester Baby” from 1948. The first fully capable computer that implemented the von Neumann Architecture envisioned in 1945 (see section 2.2) was the Electronic Delay Storage Automatic Calculator (EDSAC) by Maurice V. Wilkes and his team from 1949. The Ferranti Mark 1 or “Machester Electronic Computer” was the first turing complete general purpose computer to be commercially available. Arguably the first mini computer was the PDP-1 by Digital Equipment Solution (DEC) from 1960.  The more user-friendly mini computer LINC was designed by Wesley A. Clark, Charles Molnar and others at MIT in 1962 and its commercial production by DEC started in 1964. 

2       Semiconductors, doping and transistors

The next revolution in computing was the advent of transistors and further miniaturization. Therefore, I would like to point you to information on how transistors work. As I come from a chemistry background, I was baffled how different the terms used by physicists and chemists are when they talk about solid state matter. However, it was enlightening to see that the underlying concepts of band theory and ligand field theory / molecular orbital theory  (see here) are basically the same.  

In order to understand how semiconductor-based circuit components work, it is advisable to have a look at how doping affects the properties of materials. Recent studies reveal the electronic structure of doped materials. (see here, here, here, and here)

Doping of semiconductors affects their band gap and thereby their conductivity. The electronic properties at the junction between regions of the semiconductor that are negatively doped (impurities with one valence electron less than the bulk material) and positively doped (impurities with one valence electron in excess) allow for transistors, diodes and other electronic circuit compounds to be produced from semiconductors. 

The rectifying effect was first described in Braun, F. (1874), Über die Stromleitung durch Schwefelmetalle [On current conduction through metal sulfides], Annalen der Physik und Chemie, 153 (4): 556-563. and an early description of the effect of the surface on the current of a semiconductor device was made by  Adams, W.G. and Day, R.E. (1877). The Action of Light on Selenium, Phil. Trans. R. Soc. Lond. 167, 313-349. The first description of an unheated device with properties similar to a vacuum tube was patented in 1925 by Julius Lilienfeld (Patents US1745175, US1900018) and later Oskar Heil patented his field effect transistor in 1934 (Patent GB439457).^[4] But the technology for realizing these constructions were not available at that time.

Theoretic work on surface states by Igor Tamm and William Shockley (Tamm, I. (1932) On the possible bound states of electrons on a crystal surface. Phys. Z. Soviet Union. 1: 733; Shockley 1939) as well as the theories on rectification by Mott and extensions by Davydov and by Shottky at Siemens AG explained, that at point contacts on charged semiconductors, extra electrons from the charged bulk material would flow into the point contact and form a neutral barrier layer. The Mott-Shottky-Davydov theory was published in 1939 and the more accurate theory by Bethe in 1942. Herbert F. Mataré and Heinrich Welker are said to have observed the transistor effect while experimenting with duodiodes between 1942 and 1944. At Compagnie des Freins et Signaux Westinghouse, Heinrich Welker envisaged his concept of the field effect transistor. Materé and Welker soon became aware of the limited modulation with their first devices in 1945 and continued development for the next years. Similarly, theoretic work on the field effect by William Shockley and G.L. Pearson from 1945 and initial experiments with semiconductor device similar too a MOSFET showed less modulation than expected. Shockleys new empoyee John Bardeen came up with the explanation that electrons could become trapped in surface state not only at point contacts but at every semiconductor surface. These trapped electrons cannot contribute to conductivity and shield the bulk semiconductor from external influence. The result enabled Bardeen and Walter Brattain to manufacture the first point contact transistor at Shockleys lab in 1947. The independently developed European field effect transistor of Herbert F. Mataré and Walker was presented  shortly after in 1948 (patents FR1010427, US2673948). In the following years, different circuit components were manufactured by placing differently doped semiconductor regions next to each other.

Fig. 1: Replication of the point contact transistor that was internally presented at Bell Labs in December 1947. Source: Federal Government of the United States of America (2000). "White House Millenium Council. National Millenium Time Capsule". The original image is in the public domain.

The first silicon-based transistor was manufactured by Morris Tanenbaum at Bell Labs in 1954. In the same year, Gordon Kidd Teal at Texas Instruments presented his silicon-based Transistor which was commercialized in 1955. After  Tanenbaum, Calvin S. Fuller and others had developed the gas diffusion process for efficient doping in 1954/1955 Silicon-based transistor production.

Shortly after, the first computers with all vacuum tubes being replaced by discrete transistors emerged: The prototype IBM 604 transistorized calculator (presented in 1954) and the Harwell CADET, which first operated in February 1955. The IBM 608 transistor calculator was the first commercially available fully transistorized computer. It was announced in April 1955 and first shipped in December 1957. After the surface-barrier transistor was developed by Philco in 1953, the Philco Transac models S-1000 scientific computer and S-2000 electronic data processing computer were announced in 1957 but did not ship until sometime after the fall of 1958.

All the semiconductor-based cirquit components were screaming for miniaturization and after initial trials by Werner Jacobi (Siemens AG) and G.W.A. Dummer that were aimed at integrating several circuit components, an operational Germanium-based integrated circuit (IC) was realized by Jack Kilby at Texas Instruments in 1958. After Kurt Lehovec of Sprague Electric had discovered the principle of p–n junction isolation (Patent US3029366 A), a group at Fairchild Semiconductor led by Jay Last was the first to produce ICs reliably on a single silicon substrate based on the planar process by Jean Hoemi (Patente US 3025589, US 3064167) and Robert Noyce’s developments. The first ALU integrated circuit was created by Fairchild Semiconductor. Later, they produced the FSC 9341, which was copied by Texas Instruments as the 74181 chip and sold as SN74181). In 1971 the first single-chip microprocessors and microcontrollers were developed: Starting with limited functionality calculator-on-a-chip designs like the Mostek MK6010 and the chip GI 250 of the Monroe/Litton Royal Digital III calculator by Pico Electronics and General Instrument as well as the TMS0100 calculator-on-a-chip family including the TMS1802NC by Texas Instruments created by Gary Boone and Michael Cochran at Texas Instruments, chips became more and more tailored towards general purpose computing, resulting in the TMS 1000 (patents US3757306 and US4074351), which went on the market in 1974. The Intel 4004 chip was the first commercially available single-chip CPU, announced in November 1971 as Intel C4004.

This development coincided with the advent of personal computers and operating systems. The highly accessible programming language BASIC (Beginners All-purporse Symbolic Instruction Code) was developed in 1964. DOS/360, developed by IBM in 1966 and UNIX, developed at Bell Laboratories in 1969 were multi-user operating system for professional users. Initially, they only had a command line interface. Modern human – machine interaction was pioneered at the Stanford Research Institute of the Stanford University by Dough Engelbart (inventor of the 1963 computer mouse), Dustin Lindberg, Bill English and others. They demonstrated their oN-Line System (NLS) featuring editing of texts and graphs, collaborative work, hyperlinks, computer-mouse control and a GUI with program windows on a Scientific Data Systems SDS 940 in 1968 (watch “the mother of all demos” or “The Demo” online). David A. Evans developed the "Journal" feature during his phD studies. Telefunken had already commercialized the ball mouse RKS 100-86 developed by Rainer Mallebrein in 1966.

In 1973, the “Sac State 8008” system was operational at California State University, Sacramento. Bill Pentz, who led a team on the COmputerized MEdical REcords System (COMERs) at the Computer Science Department within the School of Engineering at California State University, Sacramento, was developing a simple general purpose computer based on the Intel 8008. When asking a friend who worked at Tektronix Inc. for advice, he was offered a position at that company and Tektronix Inc. built him a reliable custom computer based on the Intel 8008. This computer was fitted with a with a Tektronix 4023 graphical terminal and a memory ROM/RAM expansion card. Bill Pentz developed firmware to run IBM’s Basic Assembler Language (BAL) on the Intel 8008. Using code for an assembler, a BASIC interpreter and an operating system that every student had to submit for examinations, Bill Pentz made the system rund a Disk Operating System. A Tektronix 9600 baud serial communications interface from 1973 was also also added. The printed circuid boards and original manuals of components were preserved by John Moorhead and are on display at the Digibarn Museum.

Fig. 2: CAD drawing of the “Sac State 8008” system. This image is Copyright (c) 1998-2018 Digibarn Computer Museum, some rights reserved under the Creative Commons Attribution-Noncommercial 3.0 License.

In 1973 the minicomputer Xerox Alto was introduced at the Xerox Palo Alto Research Center (Xerox PARC). It was designed mostly by Charles P. Thacker. Industrial Design and manufacturing was sub-contracted to Xerox. It was used internally and at universities and featured everything above as well as a GUI using the desktop metaphor first introduced by Alan Kay at Xerox PARC in 1970. It was the basis of the first commercially available personal computer featuring all this, the Xerox 8081 Information System (“Xerox Star”) of 1981.

After David Richie had developed the programming language C at Bell Laboratories, the workstation and server operating system UNIX was rewritten in this new programming language between 1972 and 1974.

The first commercially available computer based on a single-chip microprocessor that also featured a keyboard and a monitor (CRT display) was the Apple I from 1976 that was designed by Steve Wozniak. It was programmed using Apple BASIC but featured no real operating system. After the Apple II from 1977 was fitted with a 5¼” floppy disk system in 1978, a Disk Operating System was commissioned from the company Shepardson Microsystems where its development was done by Paul Laughton. After Intel had released the 16 Bit CPU Intel 8086 and Tim Peterson had developed the operating system QDOS for it, Microsoft licenced QDOS-86 and ported it for the IBM Personal Computer (PC) that was released with a debugged version of MS-DOS 1.14, called PC-DOS 1.0. After Apple had licenced the Xerox GUI and released the Apple Lisa featuring Lisa OS and a computer mouse in 1883, the concept introduced with the Xerox Alto and Xerox Star became a widely accepted standard. Microsoft also licenced the Xerox GUI and in the same year, similar graphical user interfaces were developed for the IBM personal computer (PC). Microsoft introduced a computer mouse for the IBM PC in 1983 and released Microsoft Windows 1.0 in 1985. After AT&T commercialized its UNIX System III in 1982, the UNIX source code could not be distributet for a minimal fee anymore. This finally led to the emergence of the GNU (GNU is not UNIX) project. Since the original UNIX-like Kernel, GNU Hurd, is still not production-ready in 2020, most GNU distributions use the Kernel "Linux" which Linus Torvalds developed in 1991. GNU/Linux distributions like Debian, Ubuntu as well as other operating systems with Linux Kernel (Android) made open-source software more and more popular.

3       Logic gates as the building block of programmable computers

In my opinion, the evolution of switching mechanisms and miniaturization is not the most important aspect about computers. The flexibility of programmable, Turing-complete machines is, what makes
them revolutionary. In all modern computers this flexibility comes from the combination of calculations in the binary system and a vast number of gates that allow for performing Boolean logic. It does not matter how these logic gates are implemented in hardware (using a specific layout of resistors, diodes and relay switches or electronic switches such as transistors). What matters is the interplay of the logic gates. 

3.1       Digital circuit simulation

The Autodesk circuits feature of the tinkercad online tool by Autodesk (tinkercad.com) contains a digital circuit simulator that supports a virtual Arduino Uno Rev.3 microcontroller device as a building block that can be integrated into virtual circuits. Programs that would run on a real Arduino Uno Rev.3 development board can be uploaded into the respective section of the online-tool to simulate the program execution in the virtual circuit. The Arduino Simulator 1.5 by Xevro.be is a standalone program for offline-usage and available for free.

3.1.1     An interactive virtual CPU from logic gates in Logism by R.J. Astwick

Logism (download cs3410 Cornell version 2.7.2 from the material section at http://www.cs.cornell.edu/courses/cs3410/2015sp/ ) is an excellent open source, interactive digital circuit simulator. It helps a lot in understanding electronic circuits and computer components. You can use it to open the virtual central processing unit (CPU) by R.J. Astwickand Dirk Sudholt (download-link: https://drive.google.com/drive/folders/0B6iPp93rMnxLfnNpTnJXWVJ5X1JfbFdCMDl5VmE3U1VWZkVoTzZSR1V6SnE2UG4tVEpGRlE). By clicking on the circuit components in logism, one can investigate the underlying circuit at the level of individual gates. For your own circuit designs, you should use Logism evolution cs3410 Cornell fork version 2.12 or newer (.jar file at http://www.cs.cornell.edu/courses/cs3410/2017sp/resources/) which allows export as a VHDL file or Verilog file that is compatible with the Qflow toolchain and Verilator or Aldec Active-HDL.

Fig. 3: Interactive virtural CPU in Logism. Taken from the bacholor thesis of R.J. Astwick. Copyright by R.J. Astwick, 2015.

3.2       How the CPU works as part of the von Neumann architecture

aaaa

Copyright © DerAndere 2018-2020