Teza Church Turing, Stefan Popescu [630086]

Teza Church – Turing
Teza Church – Turing
Prof. coordonator: Tătărâm Monica
Prof. coordonator: Tătărâm Monica
Student: [anonimizat]: Popescu
Ștefan-Geo
Ștefan-Geo
rge
rge
București,
București,
Ianuarie 2011
Ianuarie 2011

C
C
up
up
ri
ri
ns
ns
:
:
Capitolu
l
I:
Introducere
………………………………………..
3
Descrierea Tezei………………………………………………. 3
Impactul Tezei………………………………………………… 4
Spectrul lucrării……………………………………………….. 4
Structura lucrării………………………………………………. 4
Capitolul
II:
Contextul
Istoric
……………………
……………
5
Autorii lucrării………………………………………………… 5
Mașini Turing…………………………………………………. 6
Problema Opririi………………………………………………. 7
Entscheidungsproblem………………………………………… 8
Capitolul
III:
Prezentarea
Tezei
…………………
……………..
9
Teza Turing………………………………………………………
.
…
10
Teza lui Church…………………………………………………
…
…
11
Capitolul IV:
Prezentarea Tezei…………………………
……….12
Diverse interpretări ale Tezei…………………………………….12
Interpretări greșite ale Tezei……………………………………14
Teza M
…………………………………………………..14
Bibliografie……………………………………………………….15
2

Capitolul I
Capitolul I
Introducere
Introducere
Teza Church-Turing afirmă că pentru orice metodă efectivă de calcul (sau algoritm)
M se poate construi o Mașină Turing care să o calculeze, cu condiția ca M să
îndeplinească următoarele condiții:
•
M este formulat ca o serie finită de instrucțiuni clare (fiecare instrucțiune fiind
exprimata cu un șir finit de
simboluri).
•
În cazul în care nu se ajunge într-o stare de eroare, M va obține rezultatul dorit
într-un număr finit de pași.
•
M poate fi parcurs de către un om având la dispoziția sa doar hârtie și unelte de
scris.
•
M nu necesită ingeniozitate sau imaginație din partea persoanei desemnate să îl
parcurgă.
Descrierea Tezei
Descrierea Tezei
Teza Church-Turing nu este o axiomă ci mai degrabă o idee – o reuniune a
rezultatelor obținute de doi mari matematicieni: Alan M. Turing și Alonzo Church în
principal ca urmare a analizei Problemei de Decizie (Entscheidungsproblem) propusă de
David Hilbert. Problema consta în găsirea unui algoritm (sau dovedirea că acesta nu
există) care să primească la intrare o descriere a unui limbaj formal și o afirmație în acel
limbaj, și să întoarcă un mesaj corespunzător valorii de adevăr a afirmației. Ambii autori
au ajuns la concluzia că nu există un astfel de algoritm.
Deși scopul celor două lucrări era să dea un răspuns problemei de decizie,
rezultatul a avut un mai mare impact asupra societății științifice. În primul rând, Church,
în lucrarea sa,
a folosit pentru prima dată
noțiun
ile de
funcți
i recursive și
funți
i lambda-
definibile. În timp ce în lucrarea sa, Turing introduce conceptul de Mașină Turing,
denumită de el LCM (logical computing machine) ducând o echivalența între funcțiile
intui
tiv calculabi
le și
cele calcula
bile pe
o Mașină Turing. El
a mai
arătat că nu
exist
ă o
soluție pentru problema deciziei demonstrând că „Problema Opririi” (Halting Problem)
este nedecidabilă pe o Mașină Turing. În mod asemănător, definiția lui Church pentru
funții intuitiv calculabile are două forme echivalente:
1.
O funcț
ie de
num
ere într
egi pozi
ti
ve este efect
iv calcu
lab
ilă dacă acea
sta est
e
λ-definibilă.
2.
O funcț
ie form
ată din num
ere înt
regi se num
ește ef
ectiv ca
lcula
bilă dacă a
ceasta
este recursivă.
3

Pe baza acestora Church a ajuns la concluzia că nu există o funcție calculabilă care să
decidă dacă două expresii λ-calculabile sunt echivalente sau nu. [wikipeida.org]
Impactul Tezei
Impactul Tezei
Teza Church-Turing a avut, și încă are o mare influență în rândul cercetătorilor.
Teza are implicații profunde în domeniul inteligenței artificiale – domeniu în care Turing
însuși și-a dezvoltat multe dintre teoriile sale ulterioare și unde a introdus faimosul său
„joc de imitație”. Testul consta dintr-o persoană numită „interogator” care trebuia să afle
care dintre cele două entități cu care comunică este mașină și care este om pe baza
răspunsurilor date unor întrebări adresate.
Spectrul lucrării
Spectrul lucrării
Lucrarea de față își are ca scop:
•
Prezentarea pe larg a Tezei și contextul în care aceasta a fost
compusă
•
Interpretări și consecințe al Tezei
•
Interpretări greșite ale Tezei
•
Importanța Tezei în domeniul informaticii
Structura lucrării
Structura lucrării
•
Capitolul I – Introducere:
Capitolul I – Introducere:
descrie subiectul pe care se bazează această
lucrare. În acest capitol se prezintă o scurtă descriere a Tezei precum și un
scurt rezumat asupra importanței acelei lucrări. În sfârșit, capitolul se
încheie cu prezentarea i
tem-ilor
ce vor f
i tratați
cu precădere pe parcursul
lucrării precum și un scurt rezumat pe capitole.
•
Capitolul II – Context istoric:
Capitolul II – Context istoric:
în acest capitol vom prezenta o scurtă
biografie a celor doi autori și vom enunța două dintre problemele ce au
motivat lucrarea lui Turing din 1936.
•
Capitolul III – Prezentarea Tezei:
Capitolul III – Prezentarea Tezei:
vom realiza o descriere mai în amănunt
a tezelor celor doi autori, a noțiunilor introduse de ei și echivalența dintre
ideile lor.
•
Capitolul IV:
Capitolul IV:
. În
acest capito
l
vom mai menționa diferit
e
inter
pretări ale
tezei precum și interpretări rezultate din înțelegerea greșită a tezei.
4

Capitolul I
Capitolul I
I
I
Contextul istoric
Contextul istoric
În acest capitol vom prezenta o scurtă biografie a celor doi mari matematicieni
pentru a înțelege mai bine, într-o anumită măsura gândirea lor. Apoi, vom discuta despre
istoria din spatele Tezei și despre noul concept propus de Turing în lucrarea sa din 1936:
Mașina Turing și despre problemele ce au motivat compunerea lucrărilor celor doi,
Problema Deciziei și Problema Opririi.
Autorii lucrării:
Autorii lucrării:
Alan M. Turing
Alan M. Turing
„Al
an
Mat
his
on
Turi
ng
a
fos
t
un
mat
ema
tic
ian
,
log
ici
an,
criptanalist și informatician britanic. Turing este adesea considerat a fi
părintele
informaticii
moderne.”
[ro.wikipedia.org]
Alan Turing s-a născut pe 23 iunie 1912. Un autodidact, până
la vârsta de 5 ani el deja învățase să citească. În 1926, la vârsta de 14
ani, s-a dus la Sherborne School, o școală publică și reputată din
Dorset. În prima zi de școală acolo, a avut o grevă generală în toată Anglia, dar era atât
de hotărât să meargă la școală încât a călătorit singur pe bicicletă 97 km de la
Southampton la școală, înnoptând la un han.
În 1936 publică lucrarea intitulată „
Computable Numbers with an Application to
the
Ents
che
idun
gspr
oble
m
”
(
„
D
e
s
p
r
e
n
u
m
e
r
e
c
a
l
c
u
l
a
b
i
l
e
,
c
u
a
p
l
i
c
a
ț
i
i
î
n
Entscheidungsproblem”). În această lucrare introduce conceptul de „Mașină Turing” și
demonstrează că nu există o soluție a Problemei de Decizie arătând întâi că Problema
Opr
ir
ii
pe
nt
ru
ma
și
ni
le
Tu
ri
ng
es
te
ned
ec
id
ab
il
ă:
nu
se
poa
te
de
ci
de
,
în
ge
ner
al
,
algoritmic, dacă o mașină Turing dată se va opri.
În timpul celui de-al doilea război mondial el a lucrat în domeniul criptanalizei în
a descifra mesajele germane. Între anii 1945-1948 a lucrat în cadrul proiectului ACE
(Automatic Computer Engine) unde și-a început cercetările în domeniul inteligenței
artificiale. Turing a fost persecutat pentru înclinațiile sale homosexuale (fapt pedepsit de
codul penal britanic din acea perioadă), acest fapt marcându-l profund pentru tot restul
vieții. A murit în 1954 din cauza otrăvirii cu cianură.
5

Alonzo Church
Alonzo Church
„Alonzo Church (14 iunie 1903 – 11 august 1995) a fost un matematician și logician
am
eri
ca
n
ca
re
a
adu
s
co
nt
ri
bu
ți
i
ma
jo
re
în
dom
en
ii
pr
ec
um
lo
gi
ca
ma
te
ma
ti
că
și
fundamentele informaticii teoretice” [en.wikipedia.org]
Născut în Washington DC, el a urmat cursurile universitare la Universitatea Princeton de
unde a obținut licența în anul 1924 și diploma de doctorat în anul 1927 având lucrarea
int
itu
lat
ă
„
Alt
erna
tive
s
to
Zerm
elo
's
Assu
mpti
on
”
.
D
u
p
ă
d
o
i
a
n
i
e
l
s
-a
î
nt
o
rs
l
a
Universitatea Princeton ca profesor. Lucrările sale sunt de mare importanță în logica
mat
emat
ică
și
inf
orm
ati
ca
teo
ret
ică
.
Est
e
cre
ato
rul
λ
-c
alc
ulu
lui
.
Est
e
de
ase
men
ea
cunoscu
t
datori
tă tezei Church-Tu
ring și al echivale
nței trasate înt
re puterea de calcul a
mașin
ilor Turing
și a
λ
-calc
ulului
.
Struct
ura
limba
jelor de
program
are
din familia LISP,
precum si limbajele de programare funcțională în general, a fost bazată pe lucrările lui
Church.
Mașini Turing:
Mașini Turing:
Turing a introdus pentru prima dată conceptul teoretic pentru o astfel de mașină –
denumită de el „
Logical Computing Machine
”- pentru a servi ca un model de calcul
ma
te
mat
ic
în
lu
cr
are
a
sa
di
n
19
36
(„
De
sp
re
nu
me
re
ca
lc
ul
ab
il
e,
cu
apl
ic
aț
ii
în
Ent
sch
eid
ungs
prob
lem
”).S
copu
l
ace
sto
r
maș
ini
era
de
a
da
o
def
ini
ție
noț
iun
ii
de
„procedură mecanică”.
Mașinile Turing au o structură ușor de înțeles. Ele sunt alcătuite dintr-o bandă
nemărginită către dreapta, ce este împărțită în celule (vezi figura de mai jos). Inițial,
banda conține o serie finită de simboluri aparținând unui alfabet de intrare, în rest,
câmpurile fiind ocupate de un caracter special numit „blank”. Mașina este dotată cu un
cap de citire/scriere și număr finit de condiționări. Mașina scanează un singur câmp de pe
bandă la un moment dat și doar pe baza acestui simbol și a stării sale curente decide
următorul pas.

6

Definiția unei mașini Turing M poate fi formalizată a
stfel:
M = <Q, V, U,
M = <Q, V, U,
δ
, q
, q
0
0
, B, F>
, B, F>
, unde
Q = mulțime finită de stări;
V = alfabetul de intrare;
U = alfabetul de lucru;
q
0

= stare inițială;
B – simbolul pentru „blank”
F =
mulțimea
stărilor f
inale
O
Mașină Turing Universală (MTU)
Mașină Turing Universală (MTU)
este o mașină Turing ce poate simula alte mașini
Turing (astfel este ilustrat folosirea principiului recursiei de către mașinile Turing). Există
însă probleme când intră în discuție funcții nedecidabile. Un cunoscut exemplu este acela
ca o MTU să poată afla dacă o mașină Turing aleatoare se va opri la primirea unui anumit
input.
Problema Opririi:
Problema Opririi:
Una dintre întrebările puse de Turing în lucrarea sa din 1936 este dacă o mașină
Turing ce a pornit în efectuarea unui proces se va opri sau nu. Turing a demonstrat că nu
există un algoritm general care să decidă dacă la primirea unui input arbitrar un program
se va opri sau nu. Această problemă nedecidabilă (fără soluție) este cunoscută în
literatură sub numele de Problema Opririi (Halting Problem). Turing a ajuns la concluzia
că problema este nedecidabilă demonstrând că nu există o MTU care să primească la
intrare o configurație a unei mașini Turing nu va putea, în general, să decidă dacă acea
mașină Turing se va opri pe o intrare dată. Presupunem că există H(x,y) astfel încât la
pr
im
ir
ea
par
am
et
ri
lo
r
x
(e
ti
ch
et
a
as
oc
ia
tă
un
ei
ma
și
ni
Tu
ri
ng)
și
y
(o
va
lo
ar
e
ce
reprezi
ntă input-ul pentru
mași
na Turing
etich
etată cu
x), întoarce rezultatul 1
dacă
x
se
oprește pe intrarea
y
și 0 în caz contrar. Presupunem prin absurd că mașina H se oprește:
atunci putem construi o altă mașină T(x) care va întoarce 1 dacă H(x,x)=0 și va rula la
infinit dacă H(x,x)=1. Din cele e mai sus ajungem la următoarele concluzii:
•
Dacă T(T) se oprește, atunci H(T,T) = 1 deci T(T) va rula la infinit.
Contradicție.
•
Da
că T(T
)
ru
le
az
ă
la inf
in
it
,
at
un
ci H(T
,T
)
=
0
de
ci T(T
)
=
1.
Contradicție.
Pro
bl
em
a
Op
ri
ri
i
a
fo
st
pri
ma
pr
obl
em
ă
ca
re
a
fo
st
ca
rac
te
ri
zat
ă
ca
fi
in
d
nedecidabilă. Pentru probleme ulterioare, faptul că sunt nedecidabile a putut fi arătat
red
ucâ
nd
u-l
e
la
Pr
obl
em
a
Op
ri
ri
i.
Pro
bl
em
a
De
ci
zi
ei
es
te
un
as
tf
el
de
exe
mp
lu
.
Explicația stă în f
aptul că propoziția care spune că
un algoritm dat se
va opri pe o int
rare
dată poate fi reformulată ca o afirmație despre numere. Deoarece nu există o metodă prin
7

care să se poată decide dacă un algoritm se oprește sau nu, se poate deduce că nu există o
metodă (algoritm) prin care să se poată decide dacă afirmația despre numere este
adevărată sau falsă.
Ent
Ent
schei
schei
dung
dung
sprob
sprob
lem :
lem :
În matematică, Entscheidungsproblem (germană pentru: Problema de Decizie),
este o problemă propusă de David Hilbert în 1928. Problema de Decizie cere găsirea unui
algoritm care primește ca input descrierea unui limbaj formal și un enunț matematic în
acel limbaj și să întoarcă „adevărat” sau „fals” în funcție de valoarea de adevăr a
enunțului. Nu este nevoie ca algoritmul să își justifice răspunsul și nici să ofere o
demonstrație, atâta timp cât întotdeauna ajunge la rezultatul corect. Un astfel de algoritm
ar putea decide, spre exemplu, valoarea de adevăr a unor conjecturi mult dezbătute.
Originile problemei datează din secolul XVII, când Leibniz propunea construcția unei
mașini ce putea efectua calcule astfel încât să determine valorile de adevăr ale unor
afirmații matematice.
Răspunsul la problemă a fost găsit de Alonzo Church în 1935-1936 și de Alan
Turing în 1936-1937, în mod independenta unul de celălalt. Church a dovedit că nu există
o funcție calculabilă ce s
ă primească două expresii de
λ

– calcul și să
returneze
dacă cele
două expresii sunt echivalente sau nu. Turing a redus Problema Opririi pentru mașinile
Turing la Problema Deciziei astfel ajungând la același rezultat ca și Church. Ambele
lucrări au fost influențate de gândirea și rezultatele obținute de Kurt Gödel precum
metoda sa de a asigna un sistem numeric formulelor logice pentru a reduce logica la
calcul aritmetic.
8

Capitolul I
Capitolul I
II
II

Prezentarea Tezei
Prezentarea Tezei
Noțiunea de metodă efectivă calculabila este una informală și lipsită de o definiție
riguroasă. Una dintre realizările lui Turing din lucrarea sa
„
On Computable Numbers, With
an Application to the Entscheidungsproblem(1936)
” a fost introducerea unui predicat formal
care să înlocuiască predicatul informal „calculabil printr-o metodă efectivă”. Church a
in
tr
od
us
ce
va
si
mi
la
r
în
lu
cra
re
a
„
A
n
Un
so
lv
ab
le
Pr
ob
le
m
of
El
em
en
ta
ry
Nu
mb
er
Theory (1936)
”
.
Predicatele înlocuitoare propuse de Turing și Church pot părea, la o primă
vedere, foarte diferite unul de celălalt, dar s-a demonstrat că cele două sunt noțiuni
echivalente, in sensul că ambele predicate descriu aceeași mulțime de funcții matematice.
teza Church-Turing constă în a presupune că acea mulțime de funcții conține toate
funcțiile efectiv calculabile.
Un algoritm poate fi descris ca o metodă de rezolvare pas – cu – pas a unei probleme. Mai
exact, în descrierea unui algoritm sugerăm existența unei entități (agent de calcul)
capabile să efectueze calculele necesare pentru a urma pașii succesivi ai algoritmului.
Mai mult, spunem că un algoritm este incomplet în cazul în care există pași care sa fie
ambigui. Vom numi porțiunea din algoritm care ii permite agentului de calcul să treacă la
următorul pas ca
instrucțiune
. Agentul de
calcul trebuie
să știe
ce pași t
rebuie să urmeze
pentru fiecare instrucțiune pe care o poate întâlni precum și ordinea în care trebuie
executate seria de instrucțiuni.
„A rezolva o problemă” înseamnă că agentul de calcul, căruia i s-a prezentat
enunțul problemei, respectă instrucțiunile algoritmului și în cele din urmă ajunge la
răspuns. Vom numi descrierea problemei (enunțul problemei) ca
input
al algoritmului iar
rezultatul produs de acesta îl vom denumi
output
.
Ne dorim ca noțiunea noastră informală de algoritm sa fie astfel încât să ne putem
imagina cu ușurință executarea acesteia e către un agent uman sau mecanic. Prin urmare,
este necesar ca obiectele pe care agentul de calcul trebuie să le examineze la orice pas, să
fie elemente din mulțimi finite. Dar, de asemenea ne dorim să reprezentăm probleme și
răspunsuri care necesită ca agentul de calcul să poată distinge dintr-un număr arbitrar de
posibilități. Această necesitate este satisfăcută prin construirea de input-uri, output-uri și
valori intermediare folosind simboluri alese din mulțimi finite. Instrucțiunile algoritmului
de asemenea trebuie formulate folosind mulțimi finite de simboluri – mai mult, un
algoritm poate avea un număr limitat de instrucțiuni
O imagine descriptivă asupra acestei noțiuni este cea din citatul următor, luat din
lucrarea lui Rogers din 1959:
9

„Fie o cameră B, înăuntrul căreia se află o persoană, L, împreună cu un
birou, unelte de scris și coli de hârtie. La unul dintre pereții lui B se află
două slot-uri ce fac legătura cu exteriorul, denumite input și output. Dacă
am scrie un număr pe o foaie și i-am livra-o prin slot-ul denumit input, L
o va
primi și va
începe să efectueze anumite calcule. Atunci când termină,
dacă termină, el va scrie numărul obținut după calcule și ni-l returnează
prin slot-ul marcat output. Vom presupune că L posedă un set finit de
instrucțiuni deterministe, finite în lungime, care se referă la modul în care
calculele ar trebui făcute. Ne vom referi la aceste instrucțiuni cu numele
de P. În cele din urmă, presupunem că rezervele de hârtie sunt nelimitate
și că în B există spațiu suficient pentru stocarea unei cantități necesare de
hâ
rt
ie
și
re
ch
iz
it
e
pe
nt
ru
ef
ec
tu
ar
ea
ca
lc
ul
el
or
.
Ar
ma
i
tr
eb
ui
să
presupunem și că persoana L este ea însăși de neobosit, din moment ce nu
ne interesea
ză cât de mult durează
apariți
a unui rezultat, cu condiți
a ca,
în cele din urmă, acesta să apară după efectuarea unui număr limitat de
calcule.”
Teza Turing:
Teza Turing:
Orice proces intuitiv de calcul poate fi implementat pe o mașină Turing.
Orice proces intuitiv de calcul poate fi implementat pe o mașină Turing.
Conceptul formal introdus de Turing este acela de
calcula
bil pe
o mașină
Turing.
El a susținut că ori de câte ori există o metodă efectivă (algoritm) pentru obținerea valorii
unei funcții matematice, funcția poate fi calculată de către o mașină Turing. Reciproca
es
te
uș
or
de
de
mo
ns
tr
at
,
de
oar
ec
e
pro
gra
mu
l
un
ei
ma
și
ni
Tu
ri
ng
es
te
el
în
su
și
o
specificație a unei metode efective de calcul: fără a se folosi de ingeniozitate, un om
po
at
e
par
cu
rge
to
at
e
in
st
ruc
ți
uni
le
pr
ogr
am
ul
ui
și
să
ef
ec
tu
ez
e
ope
ra
ți
il
e
cer
ut
e.
Dificultatea validării tezei lui Turing stă in informalitatea conceptului de algoritm: nu
poate există o metodă formală de a descrie proprietățile clasei tuturor algoritmilor dacă
nu
ave
m
o
de
fi
ni
ți
e
fo
rm
al
ă
cl
ară
pe
nt
ru
no
ți
un
ea
de
al
go
ri
tm
.
De
și
nu
ex
is
tă
o
demonstrație riguroasă care să o susțină și este puternic dezbătută, teza lui Turing este în
general acceptată ca fiind un adevăr empiric.
Turing și-a formulat teza cu scopul de a argumenta că
Entscheidungsproblem,

o
problemă de decizie, nu poate a avea răspuns. Church ajunsese la același rezultat cu
câteva luni înainte, folosindu-se de conceptul de
λ
– definibilitate în locul calculului pe
mașini Turing. (O funcție de numere întregi pozitive se numește
λ
– definibilă dacă
val
oare
a
fun
cți
ei
poa
te
fi
cal
cul
at
pri
ntr
-un
proc
es
alc
ătu
it
din
sub
sti
tuț
ii
repe
tat
e.)
Rezultatele celor doi au fost descoperite independent unul fața de celălalt, însă conceptele
lor
s-au dovedit
a fi
echivalente.
10

Noțiunea de funcție
λ
– definibilă este rezultatul lucrărilor lui Church și Kleene
iar cel de funcție recursivă se datorează lui Gödel și Herbrand.
Teza lui Church:
Teza lui Church:
O funcție de numere întregi pozitive este efectiv calculabilă dacă este recursivă.
O funcție de numere întregi pozitive este efectiv calculabilă dacă este recursivă.
Kleene pare a fi cel care a introdus denumirea de „teza Church-Turing”. El a
ajuns la concluzia că cele două teze sunt echivalente și a sugerat ca ambele teze să fie
adresat
e sub
numel
e de
„tez
a
Church” sau „teza Church-Tur
ing” din moment ce
una din
lucrări tratează mașinile Turing. Copeland consideră că Kleene, în capitolele 12 și 13 din
lucrarea sa „
Introduction to Mathematics: Amsterdam North-Holland
” face una dintre
cele mai bune analize ale Tezei, și le rezumă astfel:
1)
Or
ic
a
r
e f
un
c
ț
i
e e
f
e
c
ti
v c
al
c
u
la
b
i
lă
c
e a f
o
st
c
e
r
c
et
a
t
ă s
–
a d
o
v
ed
i
t a f
i
calculabilă de către o mașină Turing.
2)
Toa
te
met
ode
le
cu
no
scu
te
pen
tru
obț
ine
rea
de
no
i
fun
cți
i
efe
ct
iv
cal
cu
lab
ile
fol
osi
nd
o
ser
ie
dat
ă
de
fu
ncț
ii
efe
cti
v
cal
cu
lab
ile
au
met
od
e
echivalente pentru construirea de noi mașini Turing plecând de la setul de mașini
Turing echivalent pentru funcțiile date.
3
)
T
o
a
t
e î
n
c
e
r
c
ă
r
i
l
e d
e a d
a o a
n
a
l
i
z
ă e
x
a
c
t
ă a n
o
ț
i
u
n
i
i i
n
t
u
i
t
i
v
e a u
n
e
i
funcții efectiv calculabile s-au dovedit a fi echivalente – în sensul că fiecare
analiză ce a fost prezentată s-a dovedit a fi descris aceeași clasă de funcții, și
anume clasa de funcții calculabile pe o mașină Turing.
Capitolul IV
Capitolul IV
Diverse interpretări
Diverse interpretări
ale Tezei :
ale Tezei :
11

Copeland pune accent pe definițiile pentru noțiunea de metodă
efectivă
sau
mecanică
și subliniază faptul că sensul pe care aceasta o are în cadrul tezei Church-Turing este
di
fe
ri
t
fa
ța
de
se
ns
ul
lo
r
pr
opr
iu
.
El
evi
de
nț
ia
ză
fa
pt
ul
că
ai
ci
se
cr
ee
az
ă
de
se
ori
interpretări greșite ale Tezei. (Definițiile lui pentru metodă efectivă și metodă mecanică –
pe care le consideră noțiuni echivalente – se găsesc la începutul Capitolului I)
Stannett, în lucrarea sa „
Computation and Hypercomputation – Minds and machines
”,
formulează teza Church-Turing astfel: „funcția numerică ce poate fi evaluată de (…) un
om (…) fără spirit intuitiv, fără conștiință de sine sau creativitate și fără nici înțelegere a
domeniului problemei (…) sunt exact acele funcții care pot fi evaluate de către calculator
(de exemplu o Mașină Turing Universală).”
Precum Copeland,
și Stannet este preocupat
d
e
m
o
d
u
l
î
n
c
a
r
e
s
e
de
f
in
es
c
no
ț
iu
ni
le
de
„
efectiv”
și „
mecanic”
. În
l
u
c
r
a
r
e
a
m
a
i
s
u
s
me
nț
io
na
tă
,
el
su
sț
in
e
id
ee
a
că
ab
il
it
at
ea
unu
i
om de a urma o serie de
i
n
s
t
r
u
c
ț
i
u
n
i
î
n
t
r
–
o
man
ier
ă
mec
ani
că
poa
te
fi caracterizată ca fiind un
c
o
m
p
o
r
t
a
m
e
n
t
u
m
a
n
e
f
e
c
t
i
v
ș
i
a
j
u
n
g
e
l
a
concluzia următoare (vezi
figura din dreapta):
„O
am
en
ii
,
în
pri
nc
ip
iu
,
p
ot
s
im
ul
a
‚g
ân
di
re
a’
unui calculator.”
Di
ane
Pro
udf
oo
t
ș
i
J
a
c
k
C
o
p
e
l
a
n
d
î
ș
i
d
e
s
c
r
i
u
m
o
d
u
l
d
e
12
Teza Church-Turing: adaptare din
Computation and
Hypercomputation – Minds and machines (2003)

înțelegere al tezei prin definirea noțiunilor de gândire trivială, algoritmică și algoritmic
calculabil:
•
Pașii unei proceduri sunt considerați a fi triviali dacă nu este necesară
înțelegerea subiectului, ingenuitate sau creativitate pen
tru a îi îndeplini.
•
O
pro
ce
dur
ă
pe
nt
ru
obț
in
ere
a
unu
i
anu
mi
t
re
zul
ta
t
es
te
co
ns
id
er
at
ă
algoritmică atunci când:
a.
Fie
care p
as di
n proc
edu
ră es
te un
ul t
riv
ial
b.
La sfâr
șit
ul fie
căru
i pas este tri
via
l de
ale
s următ
orul pas ce treb
uie
făcut (nu este nevoie de ingenuitate pentru a trece la următorul pas) și
c.
Procedu
ra garant
ează fa
ptul c
ă se va
ajunge
la rez
ultat
ul corec
t înt
r-un
număr finit de pași (presupunând că fiecare pas este efectuat corect)
•
Un sistem (real sau abstract) este algoritmic calculabil doar în cazul în
ca
re
ex
is
tă
un
al
go
ri
tm
–
cu
no
sc
ut
sa
u
ne
cu
no
sc
ut
–
pe
nt
ru
a-
i
pr
ez
ic
e
comportamentul. Cu alte cuvinte, sistemul este calculabil din punct de vedere
algoritmic dacă și numai dacă există un algoritm care să ofere o descriere corectă
a output-ului sistemului (incluzând răspunsul vid) cunoscând o descriere a input-
ului sistemului și o descriere a stării inițiale a sistemului, pentru toate input-urile
po
sib
ile
care
ret
urne
ază
un
out
put
.
(Anu
mit
e
inp
ut-u
ri
în
anu
mit
e
sis
tem
e
calculabile algoritmic nu produc output deoarece conduc sistemul într-un ciclu
infinit.)
Date aceste definiții, interpretarea lor a tezei Church-Turing sună astfel:
„
Orice sistem calculabil algoritmic poate fi simulat pe o mașină Turing.
În sensul că, o mașină Turing poate genera o descriere corectă a output-
ului unui sistem din descrierea input-ului primit de sistem și a stării
curente a sistemului, pentru toate datele de intrare posibile ce produc
output. Folosindu-ne de teza Church-Turing putem spune că nu există un
aparat care să efectueze calcule algoritmice mai puternic decât o mașină
Turing Universală
”
13

Interpretări greșite ale Tezei :
Interpretări greșite ale Tezei :
Este important să diferențiem dintre teza Church-Turing și diferitele enunțuri care
sugerează că orice poate fi calculat de către o mașină poate fi calculat de o mașină
Turing, sau că mașină Turing ar fi o limită înnăscută a puterii de calcul. Gandy (1980)
este unul dintre autorii care a diferențiat clar teza lui Turing de afirmația descrisă mai sus,
denumind-o pe cea din urmă „Teza M”
Teza M:
Teza M:
„Orice poate fi calculat de o mașină (ce lucrează pe o mulțime finită de date în
„Orice poate fi calculat de o mașină (ce lucrează pe o mulțime finită de date în
concordanța cu o serie finită de instrucțiuni) este calculabil de o mașină Turing.”
concordanța cu o serie finită de instrucțiuni) este calculabil de o mașină Turing.”
Tezei M. i se pot asocia două interpretări, după cum fraza „poate fi calculat de
către o mașină” poate fi interpretată în sens restrâns, adică „poate fi calculat de o mașină
care se conformează legilor fizicii ale lumii existente”, sau în sens larg, care face
abstracție de faptul că o astfel de mașină ar putea exista. Versiunea restrânsă a Tezei M
este o propoziție empirică a cărei valoare de adevăr este necunoscută. Speculații că ar
exista procese fizice, și deci potențiale operații mecanice, a căror comportament poate fi
folosit pentru a calcula funcții necalculabile de o mașină Turing, se întind pe ultimele
cinci decenii; Versiunea extinsă este însă falsă. Există o largă varietate de descrieri a unor
mașini teoretice capabile să calculeze funcții care nu sunt calculabile cu mașini Turing.
14

Bibliografie:
Bibliografie:
Copeland, J. B., ‘Turing, Wittgenstein and the Science of the Mind’
Proudfoot
D.
(1994).
<
http://www.hums.canterbury.ac.nz/phil/people/personal_pages/jack_copeland/pub/leibe
r.html
>
Peter J. DENNING, Jack B. DENNIS, Joseph E. QUALITZ:
Machines,
Languages and Computation
, Prentice Hall Inc. Englewood Cliffs, NJ, 1978
Eleni PAGANI:
The Physical and Philosophical Implications of the Church –
Turing Thesis
2004
<plato.stanford.edu>
<research.microsoft.com/en-us/um/people/gurevich/Opera/164.pdf>
<en.wikipedia.org>
<www.alanturing.net>
15