Who invented the Turing machine and how heavy was it?

Answer 1

The Turing machine was "invented" by Alan Turing - around 1936. He later described his machine as:

"...an unlimited memory capacity obtained in the form of an infinite tape marked out into squares, on each of which a symbol could be printed. At any moment there is one symbol in the machine; it is called the scanned symbol. The machine can alter the scanned symbol, and its behavior is in part determined by that symbol, but the symbols on the tape elsewhere do not affect the behavior of the machine. However, the tape can be moved back and forth through the machine, this being one of the elementary operations of the machine. Any symbol on the tape may therefore eventually have an innings."

Since it is a concept rather than an actual physical machine it really doesn't have any physical weight.

Turing described it conceptually to answer the questions of:

· Does a machine exist that can determine whether any arbitrary machine on its tape is "circular" (e.g., freezes, or fails to continue its computational task)?

and

· Does a machine exist that can determine whether any arbitrary machine on its tape ever prints a given symbol?

The motivation for the conceptual machine was to answer the "Entsheidungsproblem" also known as Hilbert's 10th question:

Given a Diophantine equationwith any number of unknown quantities and with rational integral coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers. The Entscheidungsproblem [decision problem for first-order logic] is solved when we know a procedure that allows for any given logical expression to decide by finitely many operations its validity or satisfiability ... The Entscheidungsproblem must be considered the main problem of mathematical logic.

(translated from the original statement in German)

Using the idea of the Turing machine (which Turing actually called an "a-machine" or "automatic machine") Turing showed that in fact the Entsheidungsproblem is uncomputable - that is - there is no possible process that fits the description of Hilbert's 10th question.