\\ Kolumny Gazety Uniwersytetu w São Paulo
Piękno matematyki
Cláudio Possani, Flávio Ulhoa CoelhoiMarcelo Fingerprofesorzy z Instytutu Matematyki, Statystyki i Informatyki USP
Bohaterem tej historii jest taki Alan Turing, który był już postacią filmu w Hollywood,Gra Imitacjii posiada nagrodę naukową w dziedzinie informatyki o nazwie Turinga, przyznawaną corocznie wybranemu naukowcowi, który wyróżnił się w danej dziedzinie. W 1937 roku wykazał matematycznie, że istnieją problemy, które nie mogą być rozwiązane przez komputer. Aby to zrobić, musiał zdefiniować, co oznacza "być obliczalnym", a w tym procesie stworzył maszyny Turinga. Są to abstrakcyjne koncepcje matematyczne, które formalizują pojęcie obliczeń, a ważny wynik matematyczny, który odkrył, pokazuje, że istnieje specjalna maszyna, zwana uniwersalną maszyną Turinga, która odgrywa centralną rolę w Teorii Obliczeń. Ta uniwersalna maszyna Turinga stanowi podstawę dla budowy komputerów, jakie znamy dzisiaj.
Początkowy artykuł Turinga zawiera kilka rzeczy, które przyciągają uwagę i które są obecne w samym tytule artykułu, przetłumaczonego tutaj na język polski:O liczbach obliczalnych i zastosowanie w problemie decyzyjnymJak to jest, liczby obliczalne? Czy chodzi o to, że istnieją liczby nieobliczalne?
Tak, i nie jest to aż tak trudne do zrozumienia. Ale najpierw wrócmy na chwilę w czasie, ponieważ początki informatyki są ściśle związane z nieskończonością. W 1874 roku niemiecki matematyk Georg Cantor opublikował artykuł, w którym wykazał, że istnieje więcej niż jeden rodzaj nieskończoności. W szczególności wykazał, że nieskończoność liczb naturalnych 0,1,2,3... jest mniejsza niż nieskończoność liczb rzeczywistych. Może już zauważyłeś to, patrząc na prosty rysunek. Nieskończoność liczb rzeczywistych odpowiada ciągłemu lini (ten zbiór nazywany jest ciągiem), a na tej linii, w sposób regularny, możemy umieścić liczby naturalne lub liczby całkowite (rozmiar nieskończoności tych innych nazywany jest licznością). Korzystając z bardzo innowacyjnej strategii, Cantor wykazał, że nie można ułożyć elementów ciągu jeden po drugim z elementami licznością, zawsze pozostanie jakiś element, który nie zostanie ułożony. W ten sposób wykazał, że ciąg jest ściśle większy niż liczność.
Wtedy Turing pokazuje, że istnieją liczby rzeczywiste nieobliczalne. Liczby nieobliczalne są zawsze elementami Kontynuuma. Z definicji, liczba rzeczywista jest obliczalna, jeśli istnieje program lub, w oryginalnej wersji, maszyna Turinga, która nieskończenie wypisuje jej cyfry. Ale każdy program i każda maszyna Turinga ma skończoną wielkość i jest przechowywana w pliku. Plik to nic innego, jak liczba naturalna, która może być bardzo duża. Zatem maksymalna liczba programów to nieskończona liczba, która nie może być wystarczająca, aby wypisać wszystkie liczby rzeczywiste. Wiele liczb rzeczywistych nie może być wypisanych przez żaden program, a te są liczbami rzeczywistymi nieobliczalnymi. I teraz wiemy, że większość liczb rzeczywistych nie jest obliczalna, tylko niewielka część z nich może być wypisana przez program lub przez maszynę Turinga.
Mała plotka tutaj. Kiedy Turing napisał swój artykuł w 1936 roku, bez jego wiedzy, inny sławny matematyk, o imieniu Alonzo Church, już wykazał istnienie liczb nieobliczalnych, używając zupełnie innych technik. Dlatego redaktorzy czasopisma byli wątpliwi, czy artykuł Turinga jest naprawdę oryginalny. Artykuł leżał na stole, aż ktoś miał pomysł, aby pokazać ten artykuł samemu Churchowi, który był tak pod wrażeniem pomysłu Turinga, że zaprosił go do zostania jego uczniem na studiach doktoranckich w Stanach Zjednoczonych. W związku z tym opóźnieniem, artykuł został opublikowany dopiero w 1937 roku. Turing ukończył studia doktoranckie w ciągu roku i wrócił do Anglii, kiedy wybuchła II wojna światowa. To tutaj zaczyna się historia filmu.Gra naśladowaniapo tym, jak Turing już wniósł znaczący wkład w historię współczesnej informatyki.
Wracając do liczb, pierwszą reakcją ludzi, kiedy dowiadują się, że istnieją liczby nieobliczalne, jest następująca: "Proszę, pokaż mi przykład liczby nieobliczalnej". A ja, z przyjemnością, odpowiadam: "Nie mogę. Jeśli pokażę liczbę, to właśnie ją obliczyłem. A liczba nieobliczalna nie może być obliczona. Czyż nie jest oczywiste? No dobrze, jeśli to nie jest oczywiste, przyzwyczaj się do idei, że nigdy nie będziesz mógł zobaczyć liczby nieobliczalnej, ponieważ ona po prostu nie jest obliczalna".
Ale, jeśli liczba nie jest obliczalna, to jak się od niej odnosisz? Dobrze, musimy używać pośrednich sposobów definiowania liczby, bez wykonywania jakichkolwiek obliczeń. Przykładem jest bardzo znana fraza "prawdopodobieństwo zatrzymania się programu komputerowego". Ta fraza w cudzysłowach jest definicją liczby. Udowodniono, że jest to liczba nieobliczalna, z której nie możemy poznać prawie żadnej właściwości. Nie możemy stwierdzić, czy ta liczba jest mniejsza niż 0,5, czy większa niż 0,00000001. Wszystkie te pytania również są nieobliczalne.
A to prowadzi nas z powrotem do artykułu Alberta Turina. Pokazał, że istnieją problemy nieobliczalne, czyli takie, które nie mogą być rozwiązane przez żadną maszynę Turinga, w tym ten tak znany Problem Decyzji (z logiki pierwszego rzędu), który był w tytule jego artykułu.
I tak narodziła się współczesna informatyka, pokazując, że informatyka ma granice. Istnieją rzeczy, które nigdy nie będą obliczalne, a my musimy żyć w granicach tego, co jest możliwe do zrobienia z maszyną obliczeniową. Twierdzenie Turinga nie zależy od żadnego języka programowania ani żadnego typu komputera. Dlatego problemy nieobliczalne pozostają nieobliczalne, niezależnie od jak najnowocześniejszej sztucznej inteligencji lub technologii, które zostaną wynalezione za ponad sto lat.
________________(Opinie wyrażone w artykułach opublikowanych wGazecie USPca totalmente odpowiedzialność ich autorów i nie odzwierciedlają opinii publikacji ani stanowisk instytucjonalnych Uniwersytetu w São Paulo. Otwórz tutaj naszeparametry redakcyjne dla artykułów opinii.)
