- #1

PainterGuy

- 940

- 69

Is Alan Turing given too much credit when it comes to computers? He is presented as someone who played a pivotal role with the realization of a computer. What Turing did as an answer to Hilbert's problem was a great achievement from mathematical point of view.

Alan Turing was mathematician and it all started with his paper in 1936, "On Computable Numbers, with an Application to the Entscheidungsproblem", https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf. In this paper he envisioned an entirely hypothetical machine.

The computer technology was already on its way of progress and becoming mature as time passed as the two excerpts below show. It's not that Turing envision a machine which didn't exist before or nobody had thought of before. The idea was already there and so were physical computing devices; Charles Babbage had carefully thought about in in 19th century. I can not see how Turing's 1936 paper played such as important role that his name is associated so much with modern computer.

Could you please comment on it? Thank you for your help, in advance.

Source: https://en.wikipedia.org/wiki/Charles_Babbage#Computing_pioneerBabbage's machines were among the first mechanical computers. That they were not actually completed was largely because of funding problems and clashes of personality, most notably with George Biddell Airy, the Astronomer Royal.

While Babbage's machines were mechanical and unwieldy, their basic architecture was similar to a modern computer. The data and program memory were separated, operation was instruction-based, the control unit could make conditional jumps, and the machine had a separate I/O unit.

The major innovation was that the Analytical Engine was to be programmed using punched cards: the Engine was intended to use loops of Jacquard's punched cards to control a mechanical calculator, which could use as input the results of preceding computations. The machine was also intended to employ several features subsequently used in modern computers, including sequential control, branching and looping. It would have been the first mechanical device to be, in principle, Turing-complete. The Engine was not a single physical machine, but rather a succession of designs that Babbage tinkered with until his death in 1871.

Source: https://en.wikipedia.org/wiki/Torpedo_Data_Computer#HistoryIn 1932, the Bureau of Ordnance (BuOrd) initiated development of the TDC with Arma Corporation and Ford Instruments. This culminated in the "very complicated" Mark 1 in 1938. This was retrofitted into older boats, beginning with Dolphin and up through the newest Salmons.

The first submarine designed to use the TDC was Tambor, launched in 1940 with the Mark III, located in the conning tower.[20] (This differed from earlier outfits.) It proved to be the best torpedo fire control system of World War II.

In 1943, the Torpedo Data Computer Mark IV was developed to support the Mark 18 torpedo.

**You can choose to ignore all the material given below but it attempts to support my own opinion that Turing didn't play such a crucial role.**

**Background to the Turing's paper:**

Turing's 1936 paper was written as an answer to one of the three problems posed by the mathematician Hilbert in 1928. The answers to two of the three problems posed by Hilbert were given by Gödel in 1930.

Source: https://en.wiktionary.org/wiki/EntscheidungsproblemEntscheidungsproblem

A decision problem of finding a way to decide whether a formula is true or provable within a given system.

Source: https://en.wikipedia.org/wiki/EntscheidungsproblemEntscheidungsproblem is a challenge posed by David Hilbert and Wilhelm Ackermann in 1928. The problem asks for an algorithm that considers, as input, a statement and answers "Yes" or "No" according to whether the statement is universally valid, i.e., valid in every structure satisfying the axioms.

...

By the completeness theorem of first-order logic, a statement is universally valid if and only if it can be deduced from the axioms, so the Entscheidungsproblem can also be viewed as asking for an algorithm to decide whether a given statement is provable from the axioms using the rules of logic.

...

In 1936, Alonzo Church and Alan Turing published independent papers showing that a general solution to the Entscheidungsproblem is impossible, assuming that the intuitive notion of "effectively calculable" is captured by the functions computable by a Turing machine (or equivalently, by those expressible in the lambda calculus). This assumption is now known as the Church–Turing thesis.

...

Before the question could be answered, the notion of "algorithm" had to be formally defined. This was done by Alonzo Church in 1935 with the concept of "effective calculability" based on his λ-calculus, and by Alan Turing the next year with his concept of Turing machines.

Alonzo Church was PhD advisor to Turing.

In 1930 Gödel came up with his incompleteness theorems. This means that in mathematical logic there are going to be some truths which are though true can never be proved to be so.

https://www.quantamagazine.org/how-godels-incompleteness-theorems-work-20200714/His incompleteness theorems meant there can be no mathematical theory of everything, no unification of what’s provable and what’s true. What mathematicians can prove depends on their starting assumptions, not on any fundamental ground truth from which all answers spring.

https://en.wikipedia.org/wiki/Entscheidungsproblem#Negative_answerIf 'algorithm' is understood as meaning a method that can be represented as a Turing machine, and with the answer to the latter question negative (in general), the question about the existence of an algorithm for theEntscheidungsproblemalso must be negative (in general).

**My own understanding:**

Hilbert posed the decision problem in 1928 which was concerned about finding a general algorithm to decide whether a mathematical formula is true or provable.

Church and Turing, around 1936, came up with an answer, using different and independent approaches, which showed that there exists no such algorithm which can be used to show if every mathematical formula is true or provable. For example, one can find an algorithm which could be used to decide whether a given formula is true or provable but it cannot used for every formula out there since no such algorithm exists. For example, no algorithm could be used to decide if Goldbach's Conjecture is true or provable.

Source: /watch?v=I4pQbo5MQOs (add www.youtube.com in front)In Gödel’s paradigm, statements still are either true or false, but true statements can either be provable or unprovable within a given set of axioms.

Source: https://www.philocomp.net/computing/hilbert.htmGödel's incompleteness theorems left theEntscheidungsproblemas unfinished business. Although he had shown that any consistent axiomatic system of arithmetic would leave some arithmetical truths unprovable, this did not in itself rule out the existence of some "effectively computable" decision procedure which would infallibly, and in a finite time, reveal whether or not any given proposition P was, or was not, provable.

**General important related info:**

Bombe was a electromechanical machine used to decrypt the codes generated by German Enigma machine in World War 2. Turing contributed to making of Bombe machine.

Lorenz cipher was an encryption machine used by German army during World War 2. Colossus computer(s) was used by British to decrypt encrypted code generated by Lorenz cipher.

For more info check: https://en.wikipedia.org/wiki/Lorenz_cipher

Source: https://en.wikipedia.org/wiki/Colossus_computerColossus was a set of computers developed by British codebreakers in the years 1943–1945[1] to help in the cryptanalysis of the Lorenz cipher. Colossus used thermionic valves (vacuum tubes) to perform Boolean and counting operations. Colossus is thus regarded[2] as the world's first programmable, electronic, digital computer, although it was programmed by switches and plugs and not by a stored program.[3]

Colossus was designed by General Post Office (GPO) research telephone engineer Tommy Flowers[1] to solve a problem posed by mathematician Max Newman at the Government Code and Cypher School (GC&CS) at Bletchley Park. Alan Turing's use of probability in cryptanalysis (see Banburismus) contributed to its design.

Source: https://en.wikipedia.org/wiki/ENIACENIAC was the first programmable, electronic, general-purpose digital computer, completed in 1945. There were other computers that had these features, but the ENIAC had all of them in one package. It was Turing-complete and able to solve "a large class of numerical problems" through reprogramming.

Source: https://www.cl.cam.ac.uk/projects/raspberrypi/tutorials/turing-machine/one.htmlWhat is a Turing machine?

A Turing machine is a hypothetical machine thought of by the mathematician Alan Turing in 1936. Despite its simplicity, the machine can simulate ANY computer algorithm, no matter how complicated it is!

Source: https://stackoverflow.com/questions/7284/what-is-turing-completeA Turing Complete system means a system in which a program can be written that will find an answer (although with no guarantees regarding runtime or memory).

So, if somebody says "my new thing is Turing Complete" that means in principle (although often not in practice) it could be used to solve any computation problem.

Entscheidungsproblem stands for "decision problem" in German.

Source: https://historyofinformation.com/detail.php?entryid=735Turing conceived of the universal machine as a means of answering the last of the three questions about mathematics posed by David Hilbert in 1928: (1) is mathematics complete; (2) is mathematics consistent; and (3) is mathematics decidable.

...

The Czech logician Kurt Gödel had already shown that arithmetic (and by extension mathematics) was both inconsistent and incomplete. Turing showed, by means of his universal machine, that mathematics was also undecidable.

Source: https://www.britannica.com/technology/ENIACENIAC was enormous. It occupied the 50-by-30-foot (15-by-9-metre) basement of the Moore School, where its 40 panels were arranged, U-shaped, along three walls. Each panel was about 2 feet wide by 2 feet deep by 8 feet high (0.6 metre by 0.6 metre by 2.4 metres). With more than 17,000 vacuum tubes, 70,000 resistors, 10,000 capacitors, 6,000 switches, and 1,500 relays, it was easily the most complex electronic system theretofore built. ENIAC ran continuously (in part to extend tube life), generating 174 kilowatts of heat and thus requiring its own air conditioning system. It could execute up to 5,000 additions per second, several orders of magnitude faster than its electromechanical predecessors. It and subsequent computers employing vacuum tubes are known as first-generation computers. (With 1,500 mechanical relays, ENIAC was still transitional to later, fully electronic computers.)

Source: https://en.wikipedia.org/wiki/Turing_completenessThe Church–Turing thesis conjectures that any function whose values can be computed by an algorithm can be computed by a Turing machine,

Source: https://en.wikipedia.org/wiki/Turing_completeness#HistoryTuring completeness is significant in that every real-world design for a computing device can be simulated by a universal Turing machine. The Church–Turing thesis states that this is a law of mathematics – that a universal Turing machine can, in principle, perform any calculation that any other programmable computer can. This says nothing about the effort needed to write the program, or the time it may take for the machine to perform the calculation, or any abilities the machine may possesses that have nothing to do with computation.

Source: https://en.wikipedia.org/wiki/Turing_completeness#HistoryCharles Babbage's analytical engine (1830s) would have been the first Turing-complete machine if it had been built at the time it was designed. Babbage appreciated that the machine was capable of great feats of calculation, including primitive logical reasoning, but he did not appreciate that no other machine could do better. From the 1830s until the 1940s, mechanical calculating machines such as adders and multipliers were built and improved, but they could not perform a conditional branch and therefore were not Turing-complete.

Source: https://en.wikipedia.org/wiki/Turing_completeness#HistoryIn 1941 Konrad Zuse completed the Z3 computer. Zuse was not familiar with Turing's work on computability at the time. In particular, the Z3 lacked dedicated facilities for a conditional jump, thereby precluding it from being Turing complete. However, in 1998, it was shown by Rojas that the Z3 is capable of simulating conditional jumps, and therefore Turing complete in theory. To do this, its tape program would have to be long enough to execute every possible path through both sides of every branch.

The first computer capable of conditional branching in practice, and therefore Turing complete in practice, was the ENIAC in 1946. Zuse's Z4 computer was operational in 1945, but it did not support conditional branching until 1950.

https://en.wikipedia.org/wiki/Turing_machineTuring machines proved the existence of fundamental limitations on the power of mechanical computation. While they can express arbitrary computations, their minimalist design makes them unsuitable for computation in practice: real-world computers are based on different designs that, unlike Turing machines, use random-access memory.

Source: https://en.wikipedia.org/wiki/Operating_system#HistoryEarly computers were built to perform a series of single tasks, like a calculator. Basic operating system features were developed in the 1950s, such as resident monitor functions that could automatically run different programs in succession to speed up processing. Operating systems did not exist in their modern and more complex forms until the early 1960s. Hardware features were added, that enabled use of runtime libraries, interrupts, and parallel processing. When personal computers became popular in the 1980s, operating systems were made for them similar in concept to those used on larger computers.

In the 1940s, the earliest electronic digital systems had no operating systems. Electronic systems of this time were programmed on rows of mechanical switches or by jumper wires on plugboards. These were special-purpose systems that, for example, generated ballistics tables for the military or controlled the printing of payroll checks from data on punched paper cards. After programmable general-purpose computers were invented, machine languages(consisting of strings of the binary digits 0 and 1 on punched paper tape) were introduced that sped up the programming process (Stern, 1981).

In the early 1950s, a computer could execute only one program at a time. Each user had sole use of the computer for a limited period and would arrive at a scheduled time with their program and data on punched paper cards or punched tape. The program would be loaded into the machine, and the machine would be set to work until the program completed or crashed.

**Helpful links:**

1: https://en.wikipedia.org/wiki/Turing's_proof

2: https://en.wikipedia.org/wiki/Enigma_machine

3: https://en.wikipedia.org/wiki/Bombe

4: https://en.wikipedia.org/wiki/Bletchley_Park

5: https://en.wikipedia.org/wiki/Torpedo_Data_Computer

6: https://en.wikipedia.org/wiki/Resident_monitor

7: https://en.wikipedia.org/wiki/Alan_Turing

8: https://en.wikipedia.org/wiki/Gödel's_incompleteness_theorems

9: /watch?v=t37GQgUPa6k (add www.youtube.com in front)

10: /watch?v=macM_MtS_w4 (add www.youtube.com in front)

11: https://en.wikipedia.org/wiki/Goldbach's_conjecture

12: https://www.scientificamerican.com/article/what-is-goumldels-proof

13: /watch?v=I4pQbo5MQOs (add www.youtube.com in front)

14: https://www.newscientist.com/articl...ing-found-machine-thinking-in-the-human-mind/

15: https://cs.stackexchange.com/questi...of-turings-answer-to-the-entscheidungsproblem