halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running (i.e., halt) or continue to run forever
Turing proved that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist
to prove this, he described a paradox involving a concept now known as "Turing machine"
Visualization of the Turing Machine (Rosario van Tulpe, 2007, CC BY-SA)
a Turing machine #2
Universal Turing machine
"It is possible to invent a single machine which can be used to compute any computable sequence. If this machine U is supplied with a tape on the beginning of which is written the S.D ["standard description" of an action table] of some computing machine M, then U will compute the same sequence as M." (Turing, 1936)
Turing test
"A TT is a way how to address the question "Can machines think?" in a scientifically plausible ye deeply empathic way. More concretely, Turing (1950) proposes that the performance of an AA under question shall be evaluated by a human judge J whose objective is to determine which among two entities - with whom J is in real-time interaction - is of human and which is of artificial nature." (Hromada, 2012)
You are going to hear two pieces of music. One is composed and performed by humans, another is composed and generated by an artificial system. You are going to hear both pieces twice. Subsequently, You are going to write down which piece (first or second) was composed and performed by human beings.