Curriculum T5 Calcolo e simboli
lezione 4
Simone Martini
Dipartimento di Informatica – Scienza e Ingegneria Alma mater studiorum • Universit` a di Bologna
Collegio Superiore
novembre 2012 – gennaio 2013
Indice di “On computable numbers”
(Introduzione)
1
Computing machines.
2
Definitions.
Automatic machines. Computing machines. Circle and circle-free numbers. Computable sequences and numbers.
3
Examples of computing machines.
4
Abbreviated tables. Further examples.
5
Enumeration of computable sequences.
6
The universal computing machine.
7
Detailed description of the universal machine.
8
Application of the diagonal process.
9
The extent of the computable numbers.
10
Examples of large classes of numbers which are computable.
11
Application to the Entscheidungsproblem.
APPENDIX
I contributi
Una definizione di “calcolabile” (la MdT) 1 Computing machines.
2 Definitions.
3 Examples of computing machines.
4 Abbreviated tables.
9 The extent of the computable numbers.
10 Examples of large classes of numbers which are computable.
L’esistenza di macchine universali 5 Enumeration of computable sequences.
6 The universal computing machine.
7 Detailed description of the universal machine.
L’esistenza di problemi non risolubili meccanicamente 8 Application of the diagonal process.
Risposta negativa allo Entscheidungsproblem.
11 Application to the Entscheidungsproblem.
Equivalenza
The theorem that all effectively calculable (λ-definable) sequences are computable and its converse are proved below in outline.
Le descrizioni di cosa ` e un calcolo, come viene condotto, quali sono le operazioni elementari, ecc. sono necessariamente diverse.
Equivalenza “estensionale” sugli oggetti matematici calcolati.
Funzioni calcolabili sui naturali
Invece di sequenze (infinite) calcolabili Funzioni calcolabili da Naturali a Naturali f : N → N `e (Turing-)calcolabile sse
esiste una MdT M f tale che per ogni n ∈ N,
se M f inizia con un nastro che contiene (una ragionevole rappresentazione di) n, termina in una configurazione in cui sul nastro ` e presente (una ragionevole rappresentazione di) f (n).
Funzioni parziali:
se f non ` e definita su un certo n, l’esecuzione di M f su n non
termina (diverge).
Codifiche
Fissiamo Σ
Fissiamo una codifica di N su Σ p q : N −→ Σ
E.g., per Σ = {0, 1, #}, la codifica di n ` e il binario di n preceduto e terminato da #:
pnq = #bin(n)#
Fissiamo un modo di presentare la codifica sul nastro
(posizione della testina ecc.)
Funzioni Turing-calcolabili
La funzione calcolata da una MdT M ` e quella funzione parziale f : N −→ N cos`ı definita:
(i) se M(pnq) termina nella configurazione pmq, allora f (n) = m;
(ii) M(pnq) non termina, allora f (n) non `e definita.
Una funzione parziale f : N −→ N `e Turing-calcolabile sse c’`e una
MdT che calcola f .
Funzioni n-arie
Possiamo fissare codifiche di N k su Σ
p(n 1 , . . . , n k )q = ##bin(n 1 )# . . . #bin(n k )##
Definisci: T k = {f : N k −→ N | f c’`e una MdT che calcola f } La classe delle funzioni Turing-calcolabili:
T = [
k≥0
T k
Funzioni ricorsive ` a la Kleene
Quali funzioni stanno in T ?
Base functions:
I
Constant zero: Z : N → N, Z (y ) = 0;
I
Successor: S : N → N, S(y ) = y + 1;
I
Projections: for any k ∈ N and i ≤ k, π k i : N k → N, π i k (y 1 , . . . , y k ) = y i .
The function f is defined by composition from g , h 1 , . . . , h n if f (y 1 , . . . , y k ) = g (h 1 (y 1 , . . . , y k ), . . . , h n (y 1 , . . . , y k ))
The function f is defined by primitive recursion from g and h if f (0, y ) = g (y )
f (x + 1, y ) = h(x , y , f (x , y ))
Quali funzioni stanno in T ?
Base functions:
I
Constant zero: Z : N → N, Z (y ) = 0;
I
Successor: S : N → N, S(y ) = y + 1;
I
Projections: for any k ∈ N and i ≤ k, π k i : N k → N, π i k (y 1 , . . . , y k ) = y i .
The function f is defined by composition from g , h 1 , . . . , h n if f (y 1 , . . . , y k ) = g (h 1 (y 1 , . . . , y k ), . . . , h n (y 1 , . . . , y k ))
The function f is defined by primitive recursion from g and h if f (0, y ) = g (y )
f (x + 1, y ) = h(x , y , f (x , y ))
Quali funzioni stanno in T ?
Base functions:
I
Constant zero: Z : N → N, Z (y ) = 0;
I
Successor: S : N → N, S(y ) = y + 1;
I
Projections: for any k ∈ N and i ≤ k, π k i : N k → N, π i k (y 1 , . . . , y k ) = y i .
The function f is defined by composition from g , h 1 , . . . , h n if f (y 1 , . . . , y k ) = g (h 1 (y 1 , . . . , y k ), . . . , h n (y 1 , . . . , y k ))
The function f is defined by primitive recursion from g and h if f (0, y ) = g (y )
f (x + 1, y ) = h(x , y , f (x , y ))
Funzioni ricorsive primitive
f (0, y ) = g (y )
f (x + 1, y ) = h(x , y , f (x , y )) La somma:
add (0, y ) = y
add (x + 1, y ) = S (add (x , y )) Definizione ufficiale:
add (0, y ) = π 1 1 (y )
Funzioni ricorsive primitive: la spina
somma:
add (0, y ) = y
add (x + 1, y ) = S (add (x , y )) prodotto
prd (0, y ) = 0
prd (x + 1, y ) = add (x , prd (x , y )) esponenziazione
exp(0, y ) = 1
exp(x + 1, y ) = prd (x , exp(x , y )) torre di esponenziali
te(0, y ) = 1
te(x + 1, y ) = exp(x , te(x , y ))
La spina
torre di torre di esponenziali:
tte(0, y ) = 1
tte(x + 1, y ) = te(x , tte(x , y )) . . .
in generale, prendi sp 1 = add e definisci
sp k+1 (0, y ) = 1
sp k+1 (x + 1, y ) = sp k (x , sp k+1 (x , y ))
Abbiamo finito?
Abbiamo dato una descrizione induttiva di una classe di funzioni:
the least class of functions containing the base functions and closed under composition and primitive recursion: PR.
Per caso PR = T ? Certo che no!
Mancano tutte le funzioni propriamente parziali (cio` e non definite su un argomento)
Mancano anche funzioni totali (pe la funzione di Ackermann).
Abbiamo finito?
Abbiamo dato una descrizione induttiva di una classe di funzioni:
the least class of functions containing the base functions and closed under composition and primitive recursion: PR.
Per caso PR = T ? Certo che no!
Mancano tutte le funzioni propriamente parziali (cio` e non definite su un argomento)
Mancano anche funzioni totali (pe la funzione di Ackermann).
La funzione di Ackermann
La spina “esaurisce” le funzioni primitive ricorsive La funzione
Ack(k, x , y ) = sp k (x , y )
`
e ben definita, ma non pu` o comparire nella spina perch´ e
cresce pi` u velocemente di ogni funzione della spina stessa.
Allarghiamo la classe
The function f is defined by minimization from g if f (y ) = the least z such that (i) g (z, y ) = 0 and
(ii) g (x , y ) is defined for all x ≤ z
Notation : f (y ) = µz.g (z, y ) = 0
The (general) recursive functions R, is the least class of
functions containing the base functions and closed under
composition, primitive recursion, and minimization.
Allarghiamo la classe
The function f is defined by minimization from g if f (y ) = the least z such that (i) g (z, y ) = 0 and
(ii) g (x , y ) is defined for all x ≤ z
Notation : f (y ) = µz.g (z, y ) = 0
The (general) recursive functions R, is the least class of
functions containing the base functions and closed under
composition, primitive recursion, and minimization.
Equivalenza
T = R
Logica combinatoria: CL
Due costanti atomiche: K e S.
Termini costruiti “giustapponendo” stringhe:
(i) K ` e un termine; S ` e un termine
(ii) se s e t sono termini, (st) ` e un termine.
Esempi: (KS), (KK), ((KK))(KS)), ((SK)K).
Calcolo per riscrittura di termini: t → s.
((Ks)t) → s
(((Sp)t)r ) → ((pr )(tr ))
Esempio: sia t un termine qualsiasi:
(((SK)K)t) → (Kt)(Kt) → t.
Equivalenza
Possiamo dare una codifica dei naturali come termini di CL.
Def: B = ((S(KS))K) (((Bf )g )x ) → (f (gx )) Def: I = ((SK)K)
0 = (KI); 1 = I; 2 = ((SB)I); 3 = ((SB)(((SB)I))).
Possiamo dare un’opportuna nozione di funzione CL-calcolabile.
T = CL-calcolabile
Equivalenza
Possiamo dare una codifica dei naturali come termini di CL.
Def: B = ((S(KS))K) (((Bf )g )x ) → (f (gx )) Def: I = ((SK)K)
0 = (KI); 1 = I; 2 = ((SB)I); 3 = ((SB)(((SB)I))).
Possiamo dare un’opportuna nozione di funzione CL-calcolabile.
T = CL-calcolabile
Random Access Machines
Una sequenza di registri: R0, R1, . . . , Rn.
Ogni registro contiene un intero (arbitrariamente grande).
Istruzioni:
1
CLR Rn
2
INC Rn
3
JEQ Rn, Rm, k
Un programma ` e una sequenza ordinata di istruzioni
L’esecuzione procede in sequenza, se non modificata da JEQ.
L’esecuzione termina dopo l’ultima istruzione della sequenza.
Equivalenza
Possiamo dare un’opportuna nozione di funzione RAM-calcolabile.
T = RAM-calcolabile
Equivalenza
Possiamo dare un’opportuna nozione di funzione RAM-calcolabile.
T = RAM-calcolabile
Equivalenze
Turing: T Kleene: R
G¨ odel: equazioni ricorsive Church: λ-calcolo
Post: sistemi di riscrittura Kolmogorov
Curry: CL
Melzak, Minsky, Lambek (?): RAM . . .
e tutti i linguaggi di programmazione!
Giustificano il nome di funzioni calcolabili tout court:
C
Equivalenze
Turing: T Kleene: R
G¨ odel: equazioni ricorsive Church: λ-calcolo
Post: sistemi di riscrittura Kolmogorov
Curry: CL
Melzak, Minsky, Lambek (?): RAM . . .
e tutti i linguaggi di programmazione!
Giustificano il nome di funzioni calcolabili tout court:
C
La tesi di Church
Ogni funzione intuitivamente calcolabile ` e Turing-calcolabile
Church, 1936
3S6 ALONZO CHURCH.
it follows by the same method, using a generalization of Theorem IV to functions of more than two positive integers.
7. The notion of effective calculability. We now define the notion, already discussed, of an effectively c~~lculable function of positive integers by identifying i t with the notion of a recursive function of positive integers
l8(or of a A-definable function of positive integers). This definition is thought to be justified by the considerations which follow, so far as positive justification can ever be obtained for the selection of a formal definition to correspond to an intuitive notion.
It has already been pointed out that, for every function of positive integers which is effectively calculable in the sense just defined, there exists an algorithm for the calculation of its values.
Conversely it is true, under the same definition of effective calculability, that every function, an algorithm for the calculation of the values of which exists, is effectively calculable. For example, in the case of a function P of one positive integer, an algorithm consists in a method by which, given any positive integer n, a sequence of expressions (in some notation) E,,, E,,, . .. , E,,,,, can be obtained; where Enl is effectively calculable when n is given; where E,i is effectively calculable when n and the expressions Enj, j < i, are given;
and where, when n and all the expressions En( up to and including E,,, are given, the fact that the algorithm has terminated becomes effectively known and the value of P ( n ) is effectively calculable. Suppose that we set up a system of Godel representations for the notation employed in the expressions Eni, and that we then further adopt the method of G d e l of representing a finite sequence of expressions Em,,E,,, . . . , E,i by the single positive integer i?en13enz. . . pienz where e,,, e,,, . . . , en< are respectively the Godel representa- tions of E,,, E,,, . . . , E,i (in particular representing a vacuous sequence of expressions by the positive integer 1). Then we may define a function G of two positive integers such that, if x represents the finite sequence.
E,,, E,,, . . . , Erik, then G(n, 2) is equal to the Godel representation of E%i, where i = k + 1, or is equal to 10 if k = r, (that is if the algorithm has terminated with E,&), and in any other case G(n, x) is equal to 1. And we may define a function H of two positive integers, such that the value of H ( n , x) is the same as that of G(n, x), except in the case that G(n, x) = 10, in which case H ( n , x) = P ( n ) . If the interpretation is allowed that the
The question of the relationship betwen effective calculability and recursiveness
[A. Church. An Unsolvable Problem of Elementary Number Theory.
American Journal of Mathematics, Vol. 58, No. 2 (Apr., 1936), 345-363]
31 / 35
La recensione di Church, 1937
REVIEWS 43
structions, can be regarded as a kind of Turing machine. It is thus immediately clear that computa- bility, so defined, can be identified with (especially, is no less general than) the notion of effectiveness as it appears in certain mathematical problems (various forms of the Entscheidungsproblem, various problems to find complete sets of invariants in topology, group theory, etc., and in general any prob- lem which concerns the discovery of an algorithm).
The principal result is that there exist sequences (well-defined on classical grounds) which are not computable. In particular the deducibility problem of the functional calculus of first order (Hilbert and Ackermann's engere Funktionenkalkul) is unsolvable in the sense that, if the formulas of this calculus are enumerated in a straightforward manner, the sequence whose nth term is 0 or 1, according as the nth formula in the enumeration is or is not deducible, is not computable. (The proof here re- quires some correction in matters of detail.)
In an appendix the author sketches a proof of equivalence of "computability" in his sense and
"effective calculability" in the sense of the present reviewer (American journal of mathematics, vol. 58 (1936), pp. 345-363, see review in this
JOURNAL,vol. 1, pp. 73-74). The author's result con- cerning the existence of uncomputable sequences was also anticipated, in terms of effective calcula- bility, in the cited paper. His work was, however, done independently, being nearly complete and known in substance to a number of persons at the time that the paper appeared.
As a matter of fact, there is involved here the equivalence of three different notions: computa- bility by a Turing machine, general recursiveness in the sense of Herbrand-Godel-Kleene, and X-de- finability in the sense of Kleene and the present reviewer. Of these, the first has the advantage of making the identification with effectiveness in the ordinary (not explicitly defined) sense evident immediately-i.e. without the necessity of proving preliminary theorems. The second and third have the advantage of suitability for embodiment in a system of symbolic logic.
ALONZO CHURCH
EMIL L. POST. Finite combinatory processes-formulation 1. The journal of symbolic logic, vol.
1 (1936), PP. 103-105.
The author proposes a definition of "finite 1-process" which is similar in formulation, and in fact equivalent, to computation by a Turing machine (see the preceding review). He does not, how- ever, regard his formulation as certainly to be identified with effectiveness in the ordinary sense, but takes this identification as a "working hypothesis" in need of continual verification. To this the reviewer would object that effectiveness in the ordinary sense has not been given an exact definition, and hence the working hypothesis in question has not an exact meaning. To define effectiveness as computability by an arbitrary machine, subject to restrictions of finiteness, would seem to be an adequate representation of the ordinary notion, and if this is done the need for a working hypothesis disappears.
The present paper was written independently of Turing's, which was at the time in press but
had not yet appeared. ALONZO CHURCH
H. B. SnTH. The algebra of propositions. Philosophy of science, vol. 3 (1936), pp. 551-578.
The author is proposing a calculus of propositions based on four primitive ideas: disjunction p+q, conjunction pq, negation p', and implication p L q. Although not explicitly stated, it is appar- ently intended that the first three operations shall obey all the usual laws. The implication p L q is not, however, to be identified with p'+q, and is thus in some degree analogous to C. I. Lewis's p q. A modal operation I p1 I analogous to Lewis's Op, is defined as (p 0)', where 0 is the null-proposition (a proposition q such that q Lq'). Equivalence is expressed by p= q, apparently to be defined as (P L q)(q LP)-
On intuitive grounds not entirely clear, the author requires that "all modal distinctions" shall be recognized. That is, let two expressions be formed from the letter p, each by a finite number of applications of negation and the modal operation, negation being nowhere applied twice in succession (i.e. without one or more intervening applications of the modal operation); then these two expressions shall not be assumed equivalent unless they are identical expressions.
An immediate difficulty is that if we assume (1) P L IIPI 'I 'and (2) (p Z q)(q Z r) L (p Z r) and the principle of inference (3), "If P and PQ Z R then Q Z R," then it is possible to infer I PI '=-| I PI I 'I '.
This the author meets by rejecting (2). (In connection with an earlier note on this same point, the
This content downloaded by the authorized user from 192.168.72.222 on Wed, 5 Dec 2012 05:21:03 AM
[A. Church. Review of “On computable numbers”.
The Journal of Symbolic Logic, Vol. 2, No. 1 (Mar., 1937), pp. 42-43]
32 / 35
La tesi di Church
Ogni funzione intuitivamente calcolabile ` e Turing-calcolabile Un principio di filosofia naturale. . .
Finora non smentito.
O forse s`ı, dalla computazione quantistica?
La tesi di Church
Ogni funzione intuitivamente calcolabile ` e Turing-calcolabile Un principio di filosofia naturale. . .
Finora non smentito.
O forse s`ı, dalla computazione quantistica?
Scienza digitale
Il concetto di calcolo e di calcolabile:
Permette la descrizione della realt` a (non solo del virtuale!) Permette di spiegarla
Permette di modificarla
in modi nuovi e irriducibili alle altre scienze.
Ambient intelligence: sensing and actuation
Smart cities and homes
Scienza digitale
Il concetto di calcolo e di calcolabile:
Permette la descrizione della realt` a (non solo del virtuale!) Permette di spiegarla
Permette di modificarla
in modi nuovi e irriducibili alle altre scienze.
Ambient intelligence: sensing and actuation
Smart cities and homes
Alfabeto o linguaggio?
Alfabeto:
il calcolo ` e manipolazione combinatoria di simboli Linguaggio:
la descrizione del calcolo a livelli e con modi diversi
Davvero il linguaggio conta?
Altre definizioni della calcolabilit` a
I
Turing: T
I
Kleene: R
I
G¨ odel: equazioni ricorsive
I
Church: λ-calcolo
I
Post: sistemi di riscrittura
I
Kolmogorov
I
. . .
I
e tutti i linguaggi di programmazione!
Sono tutti equivalenti
La classe delle funzioni calcolabili
` e indipendente dal linguaggio in cui ` e definita
Davvero il linguaggio conta?
Altre definizioni della calcolabilit` a
I
Turing: T
I
Kleene: R
I
G¨ odel: equazioni ricorsive
I
Church: λ-calcolo
I
Post: sistemi di riscrittura
I
Kolmogorov
I
. . .
I
e tutti i linguaggi di programmazione!
Sono tutti equivalenti La classe delle funzioni calcolabili
` e indipendente dal linguaggio in cui ` e definita
Un paradosso?
La nozione di calcolabile ` e invariante per cambio di linguaggio mentre
Un calcolo ` e (estremamente) sensibile al linguaggio in cui ` e espresso
♦ Una MdT sporca un numero potenzialmente infinito di celle (con simboli da alfabeto finito)
♦ Una RAM sporca un numero finito di registri (con interi potenzialmente infiniti)
♦ Un λ-termine definisce solo funzioni sequenziali
(sui λ-termini)
Un paradosso?
La nozione di calcolabile ` e invariante per cambio di linguaggio mentre
Un calcolo ` e (estremamente) sensibile al linguaggio in cui ` e espresso
♦ Una MdT sporca un numero potenzialmente infinito di celle (con simboli da alfabeto finito)
♦ Una RAM sporca un numero finito di registri (con interi potenzialmente infiniti)
♦ Un λ-termine definisce solo funzioni sequenziali
(sui λ-termini)
Equivalenze
Equivalenza attraverso codifica (“g¨ odelizzazione”) Distrugge la struttura:
I
del problema
I
della sua soluzione
Anche in traduzioni “composizionali”: compilazione
Irriducibilit` a
Livelli di descrizione: gerarchie (“stack”) Fenomeni emergenti
Riduzione di un livello ad un altro
I
possibile in principio (ovviet` a!)
I
sbagliata metodologicamente
I
non esistono traduzioni fedeli, neppure all’interno della stessa lingua
Una lingua riempie una cella nell’alveare delle percezioni e delle
interpretazioni possibili. Articola una gerarchia di valori, di
significati e di supposizioni che non corrisponde esattamente a
quella di nessun altra lingua.
Irriducibilit` a
Livelli di descrizione: gerarchie (“stack”) Fenomeni emergenti
Riduzione di un livello ad un altro
I
possibile in principio (ovviet` a!)
I
sbagliata metodologicamente
I
non esistono traduzioni fedeli, neppure all’interno della stessa lingua
Una lingua riempie una cella nell’alveare delle percezioni e delle interpretazioni possibili. Articola una gerarchia di valori, di significati e di supposizioni che non corrisponde esattamente a quella di nessun altra lingua.
[G. Steiner, Errata, cap. 7, 1997]
Informatica: tre personæ
Un insieme di applicazioni
Una tecnologia che rende possibili quelle applicazioni
Una scienza che fonda quella tecnologia
Alcuni concetti
L’informatica:
Studia i procedimenti effettivi di elaborazione dell’informazione.
Contribuisce alle scienze con concetti propri, quali:
I
effettivit` a
I
complessit` a computazionale
I
gerarchia di astrazione
I
informazione
Condivide con altre scienze:
I
interazione
I
comunicazione
I
problem solving
Ma soprattutto. . .
Mette a disposizione strumenti linguistici
Affinch´ e ci` o sia possibile e semplice
Cio` e evocativo, sintetico, economico
Nella pluralit` a feconda dei linguaggi
Ipsa forma est substantia
L’essenza dell’informatica risiede nell’immateriale dell’espressione linguistica del calcolo e dell’interazione.
Il modo di esprimere un concetto (un algoritmo, la struttura di un protocollo, un’architettura software) ` e altrettanto importante del concetto espresso.
Questa forma ` e influenzata in modo cruciale dal linguaggio che
scegliamo per esprimerla.
In altre scienze. . .
In altre scienze. . .
Matematica: troppo facile!
In altre scienze. . .
Chimica:
Antoine-Laurent de Lavoisier,
Trait´ e ´ el´ ementaire de chimie, 1789
In altre scienze. . .
SCIENCE AND LINGUISTICS *
Benjamin Lee Whorf
Every normal person in the world, past infancy in years, can and does talk. By virtue of that fact, every person — civilized or uncivilized — carries through life certain naive but deeply rooted ideas about talking and its relation to thinking. Because of their firm connection with speech habits that have become unconscious and automatic, these notions tend to be rather intolerant of opposition. They are by no means entirely personal and haphazard; their basis is definitely systematic, so that we are justified in calling them a system of natural logic — a term that seems to me preferable to the term common sense, often used for the same thing.
According to natural logic, the fact that every person has talked fluently since infancy makes every man his own authority on the process by which he formulates and
*
Reprinted from Technol. Rev., 42:229-231, 247-248, no. 6 (April 1940).
Figure 9. Languages dissect nature differently. The different isolates of meaning (thoughts) used by English and Shawnee in reporting the same experience, that of cleaning a gun by running the ramrod through it. The pronouns ‘I’ and ‘it’ are not shown by symbols, as they have the same meaning in each language. In Shawnee ni- equals ‘1’; -a equals ‘it.’
Linguistica:
Edward Sapir e Benjamin Whorf
1930ss
Linguaggi cosiddetti di programmazione
Prescrizione del calcolo: marginale Astrazione: centrale
I
del problema
I
della soluzione
I
delle interazioni interne
I
delle interazioni con l’esterno
Astrazione e linguaggi
Ricchi modelli dei dati Ricchi modelli procedurali Ricchi modelli di interazione
Ricchi modelli di concorrenza e sincronizzazione
Articolazione del reale
Un oggetto (artefatto) software ` e un modo per rendere intelligibile la realt` a
Categorie nuove ed irriducibili a quelle di altre scienze
I
Effettivit` a
I
Complessit` a (computazionale), feasibility
I
Interazione (tra agenti)
I
