Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Matematyczny świat języków: 5. Języki rozstrzygalne i dodatek

No description
by

Michał Korch

on 1 May 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Matematyczny świat języków: 5. Języki rozstrzygalne i dodatek


MIMUW
Matematyczny świat języków
Michał
Korch

Matematyka dla ciekawych świata
Cz. 5. Języki rozstrzygalne
Ograniczona maszyna Turinga
{a,b}
{A,B,#}
a>A
a>a
B>B
b<B
a<a
B<B
A>A
B>B
B>B
#<#
a a a b b b
#
#
a
A
a
a
a
a
b
B
a
a
a
a
A
A
a
A
a
a
B
B
b
B
B
B
a
a
A
A
a
A
B
B
B
B
b
B
B
B
B
B
A
A
B
B
B
B
B
B
#
#
Co może komputer?
#!/usr/bin/python

print "Hello world!"
#!/usr/bin/python
from math import pow

a = 6
znaleziono = 0
while znaleziono==0 :
for n in range(3,a-3):
for x in range(1,a-n-2):
for y in range(1,z-n-x-1):
z = a-n-x-y
if (pow(x,n)+pow(y,n)==pow(z,n)):
print "Hello world!"
znaleziono = 1
a++
Wielkie Twierdzenie Fermata
Dla n>2, nie istnieją liczby naturalne x,y,z>0, takie że:
"Cuius rei demonstrationem mirabilem sane detexi hanc marginis exiguitas non caperet."
Pierre de
1601-1665
Małe Twierdzenie Fermata
Liczby Fermata
Zasada Fermata
1995
Czy istnieje program komputerowy,
który stwierdza czy dany mu kod programu wypisze słowa "Hello world"?
Problem =
czy dane wyrażenie arytmetyczne daje wynik podzielny przez 3?
czy dane wyrażenie należy do języka słów będących wyrażeniami arytmetyczmymi dającymi wynik podzielny przez 3?
tylko te, co dają wynik podzielny przez 3
program = słowo nad alfabetem {a-z, , =, ...}
Czy komputer da radę sprawdzić, czy dany kod programu jest w

języku składającym się ze wszystkich programów, które wypisują "Hello world!"
?
Nie!
Załóżmy, że istnieje taki program.
program.py
HELLO
TESTER.py

tak/nie

IF
print "Super!"
T
N
print "Hello World!"
HELLOORNOTHELLO.py
HELLOORNOTHELLO.py
Co się stanie po odpaleniu HELLOORNOTHELLO.py?
wypisze
super
czyli HELLOTESTER mówi
tak
co znaczy, że HELLOORNOTHELLO wypisuje
Hello world!
sprzeczność!
wypisze
Hello world!
czyli HELLOTESTER mówi
nie
czyli HELLOORNOTHELLO wypisuje
super
sprzeczność!
nie!
język
nierozstrzygalny
#
#
#
#
#
...
...
nieskończona taśma
Czy jest potrzebna?
Język słów postaci
X$Y
, gdzie X i Y
to wyrażenia
regularne, które opisują
ten sam język regularny
(a+b)*$(a*.b*)*
{a,b,+,.,*,(,),$}
a..ab..bc..cd..d
n m k l
jeśli
nm=kl
a>a
b>b
b>b
c>c
c>c
d>d
d>d
#<#
d<d
c<c
b<b
a<a
#>#
a>A
a>a
b>B
b>b
c>c
d>d
X>X
#<X
X<X
d<d
c<c
b<b
B>B
c<c
B<b
a<a
A>A
b>b
b>b
c>C
c>c
d>D
d>d
Y>Y
X<Y
Y<Y
d<d
D>D
Y<Y
D<d
c<c
C>C
d>d
d>d
Y>Y
#>#
sprawdzenie struktury
mnożenie mn
mnożenie kl
sprawdzenie czy równe
#
a
b
A
B
#
a
b
c
d
D
d
d
d
#
X
#
#
#
#
#
B
X
b
b
A
X
X
B
B
C
D
D
D
Y
Y
Y
Y
Maszyna Turinga może też dać jakiś wynik obliczeń
0<0
#>=
0>0
1>1
#<#
A>A
B<B
System dwójkowy
101101
32 8 4 1
=45
1011
8 2 1
=11
Jest
10
rodzajów ludzi: ci, którzy znają system dwójkowy i ci, którzy go nie znają
1 0 1 1 0 1
1 0 1 1
+
0
0
0
1
1
1
32 16 8
=56
1<1
0
1
2
0<B
1<B
0<0
0<0
0<0
1<1
1<1
1<1
+<+
+<+
+<+
+<+
A<A
A<A
A<A
0<A
0<A
0<A
1<A
1<A
1<A
=<=
=<=
=<=
0
1
2
3
=<=
=<=
=<=
=<=
0<0
0<0
0<0
0<0
1<1
1<1
1<1
1<1
#>0
#>0
#>1
#>1
0>0
1>1
0>0
1>1
0<B
1<B
+<+
B<B
#<#
0>0
1>1
A>A
=>=
=>=
A>A
A>A
+>+
+>+
0>0
1>1
0>0
1>1
B>B
B<B
#
#
#
#
#
1
1
+
1
0
#
=
B
A
A<A
+<+
=<=
1<1
0<0
#>1
1
A
B
0
1
Co może więcej?
maszyna Turinga
komputer
=
Niedeterministyczne maszyny Turinga
a>A
a<B
a>A
np. rozwiązać skomplikowane
równanie
o którym skądinąd wiemy, że ma rozwiązanie będące liczbą naturalną
#<$
#<#
#>0
#>1
#>0
#>1
$>$
sprawdzamy, czy wygenerowana liczba spełnia równanie
Czy można maszyną niedeterministyczną zrobić coś więcej niż deterministyczną?
Nie!
Mając niedeterministyczną maszynę Turinga można zrobić deterministyczną maszynę, która robi to samo.
DANE
st
poz
st
poz
DANE
st
poz
DANE
DZNE
st
poz
DKNE
st
poz
DZNE
st
poz
DZNE
st
poz
DZNE
st
poz
jeśli gdzieś brakuje miejsca na dane to możemy rozsunąć rzeczy
nasza maszyna przechodzi do swojego stanu akceptującego, jeśli któryś wyliczony stan oryginalnej maszyny jest akceptujący
b
b
d
d
d
d
Język jest
y
Hierarchia języków
1912-1945
test Turinga
bomba Turinga
Noam Chomsky
ur. 1928
języki
regularne
języki bezkontekstowe
języki kontekstowe
języki rozstrzygalne
języki Turinga
jeśli istnieje mszyna Turinga, która zawsze się zatrzymuje i akceptuje dokładnie słowa z tego języka
zawsze się zatrzymuje
akceptuje dokładnie słowa z naszego języka
akceptuje dokładnie słowa z naszego języka
poza tym nie musi się zatrzymać
(rekurencyjne)
(przeliczalnie rekurencyjne)
ale jest to język
Turinga
język programów wypisujących Hello World
język par wyrażeń regularnych dających to samo
język z tyle samo a, b i c
język z tyle samo ab, aabb, ...
Język diagonalny
{0,1}
mogę ponumerować wszystkie słowa nad tym alfabetem
1
2
3
4
5
6
7
8
9
10
...
0
1
00
01
10
11
000
001
010
mogę zakodować zero-jedynkowo konkretne maszyny Turinga
5
3
1<0
11111
0
111
0
1
0
1
0
0
0
> 0
< 1
111
0
11
0
0
0
0
0
1
0
...
czyli kodowanie maszyny Turinga to jakieś słowo nad {0,1}
pierwszy stan jest początkowy
...
00
11
0
111
...
...
...
wszystkie słowa, które mają x na przekątnej w swoim wierszu
Dlaczego nie jest językiem Turinga?
załóżmy, że jest
sprzecznosć!
Język uniwersalny U
Język wszystkich słów postaci
M$w
gdzie M akceptuje słowo w
U jest językiem Turinga
U nie jest językiem rozstrzygalnym
wyobraźmy sobie następującą maszynę Turinga
kod M
w
stan M
pozycja M
...
symuluje działania M na podstawie jej kodu, zapisując sobie aktualne stan i pozycję M
może odsunąć w jeszcze dalej, jak potrzeba więcej miejsca
przechodzi do swojego stanu akceptującego, jeśli w miejscu stan M pojawi się numer stanu akceptującego M
Uniwersalna maszyna Turinga
Załóżmy, że jest inaczej i mamy
maszynę Turinga T
, która ma to do siebie, że
akceptuje tylko słowa z języka uniwersalnego
, ale ponadto
zawsze się zatrzymuje
.
Rozważmy następującą maszynę Turinga:
1. Na wejściu dostaje pewne słowo
w
. Wylicza jego numer w sensie naszego numerowania.
2. Wylicza kod maszyny Turinga
M
o takim numerze.
3. Symuluje działanie
T
na słowie
M$w
.
4. Jeśli symulacja zatrzyma się w stanie T nieakceptującym, to nasza maszyna przechodzi do stanu akceptującego.
5. Jeśli symulacja zatrzyma się w stanie T akceptującym, to nasza maszyna przechodzi do dowolnego stanu nieakceptującego i kończy pracę.
akceptuje dokładnie słowa z języka diagonalnego
język Turinga!
sprzeczność!
Zdyscyplinowany człowiek wyposażony w papier, ołówek i gumkę to w praktyce maszyna uniwersalna.
Alan Turing
jeszcze jedna uwaga...
automat nawet jeśli nie dojdzie do stanu akceptującego, to na pewno w pewnym momencie skończy swoją pracę
maszyna Turinga niekoniecznie...
Alana
język uniwersalny
Dodatek. Świat jest skomplikowany
Szybkie przypomnienie
Język jest

językiem Turinga
, jeśli istnieje maszyna Turinga, która mając na wejściu słowo z tego języka zatrzymuje się w stanie akceptującym, a wpp. nie zatrzymuje się wcale lub w stanie nie będącym stanem akceptującym.
Motywacja
Do tej pory znaleźliśmy jeden język, który
nie jest
językiem Turinga -- język diagonalny.
Ile jest takich "złych" języków?
Baaardzo dużo!
Hotel Hilberta
standardowy
skończenie wiele pokoi
może przyjąć tyle gości ile ma pokoi
jeśli wszystkie pokoje są zajęte, nie można zakwaterować nowego gościa
...
nieskończenie wiele pokoi
...
mimo tego, że wszystkie pokoje były zajęte, udało się zakwaterować nowego gościa
...
...
...
...
...
...
w jeden hotel Hilberta udało się zakwaterować tyle gości, ile zapełniłoby dwa hotele Hilberta!
hotel w wersji
1862-1943
przestrzeń Hilberta,
system Hilberta,
krzywa Hilberta...
problemy Hilberta
Międzynarodowy Kongres Matematyków, Paryż, 1900
Tyle samo elementów?
raz, dwa, trzy, cztery.
Cztery

raz, dwa, trzy, cztery.
Cztery

A co jeśli nie umielibyśmy liczyć do czterech?
Obserwacja: jeśli na sali balowej każdy tańczy w jakiejś parze, to jest tyle samo mężczyzn, co kobiet.
Wniosek (definicja):
powiemy, że dwa zbiory są równoliczne, jeśli ich elementy można ustawić w pary (ozn. |A|=|B|)
w przypadku hotelu Hilberta ustawialiśmy w pary gości i pokoje.
|N| = |N {-1}|
{0,1,2,3,4,5,6,...}
liczby naturalne
0 1 2 3 4 5 6 7 ...
-1 0 1 2 3 4 5 6 ...

|N| = |Z|
0 1 2 3 4 5 6 7 ...
0 1 -1 2 -2 3 -3 4 ...

liczby całkowite
{..., -3, -2, -1, 0, 1, 2, 3,...}
Wszystkie słowa nad alfabetem {0,1} też da się zakwaterować w hotelu Hilberta (jest ich tyle, co liczb naturalnych)
Już to zrobiliśmy!
Twierdzenie Cantora
Czy da się zakwaterować wszystkie nieskończone ciągi zer i jedynek?
Dowód nie wprost
Załóżmy przeciwnie:
0
1
2
3
4
...
spórzmy na przekątną
i zróbmy na złość.
0 0 1 1 1 0 0 0 ...
0 1 0 0 1 0 0 0 ...
1 1 1 0 0 0 1 0 ...
0 0 0 0 1 0 0 1 ...
1 1 0 1 0 0 0 0 ...
...
1 0 0 1 1 ...
w ten sposób na n-tym miejscu gwarantujemy, że nasz ciąg jest inny niż ten w n-tym miejscu!
Czyli nie ma go w tabelce!
Sprzeczność!
P(N)
zbiór wszystkich podzbiorów zbioru liczb naturalnych
{ , , }
A=
P(A)=
,{ }, { }, { },
{ , }, { , }, { , },
{ , , }
{ }
Każdy podzbiór liczb naturalnych można zakodować ciągiem zero-jedynkowym
{2, 3, 5, 7, 11, ...}
0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, ...
a zatem podzbiorów liczb naturalnych jest tyle, co nieskończonych ciągów zerojedynkowych.
|N|<|P(N)|
Niech A będzie dowolnym zbiorem.
|A|<|P(A)|
Nie!
Georga
1845-1918
przestrzeń Cantora,
twierdzenie Cantora, zbiór Cantora, funkcja Cantora
ojciec teorii mnogości
|N|=|Z|=|Q|=
|P(N)|=|R|=
<
Ile jest
wszystkich
języków?

Ile jest języków
Turinga
?

|słów| = |N|
język to podzbiór zbioru wszystkich słów
więc wszystkich języków jest tyle, co P(N)
continuum
przeliczalnie wiele
każdy język jest rozpoznawany przez jakąś maszynę Turinga
więc jest ich nie więcej niż możliwych maszyn Turinga
jest ich
tyle co liczb naturalnych
wniosek: zdecydowana większość języków jest bardzo skomplikowana (nie może być ogarnięta przez komputer)
Davida
Żadna nauka nie wzmacnia tak wiary w potęgę umysłu ludzkiego, jak matematyka.
H. Steinhaus
=|nieskończone ciągi zerojedynkowe|
=|słowa nad alfabetem {0,1}|
Full transcript