ALAN TURING - KHOA HỌC MÁY TÍNH tập 15 Alan Mathison Turing OBE FRS (23 tháng 6 năm 1912 – 7 tháng 6 năm 1954) là một nhà toán học, logic học và mật mã học người Anh, được xem là cha đẻ của ngành khoa học máy tính. Phép thử Turing (Turing test) là một trong những cống hiến của ông trong ngành trí tuệ nhân tạo: thử thách này đặt ra câu hỏi rằng máy móc có khi nào đạt được ý thức và có thể suy nghĩ được hay không. Ông đã hình thức hóa khái niệm thuật toán và tính toán với máy Turing, đồng thời đưa ra phiên bản của "Turing", mà ngày nay được đông đảo công chúng chấp nhận, về luận đề Church-Turing, một luận đề nói rằng tất cả những gì tính được bằng thuật toán đều có thể tính được bằng máy Turing.
Trong Chiến tranh thế giới thứ hai, Turing đã từng làm việc tại Bletchley Park, trung tâm giải mật mã của Anh, và một thời là người chỉ huy của Hut 8, một bộ phận của Anh có trách nhiệm giải mật mã của hải quân Đức. Ông đã sáng chế ra nhiều kỹ thuật phá mật mã của Đức, trong đó có phương pháp nối các máy giải mã lại với nhau thành một bộ bombe, một máy điện-cơ để tìm ra công thức cài đặt cho máy Enigma.
Sau chiến tranh, ông công tác tại Phòng thí nghiệm Vật lý Quốc gia (National Physical Laboratory), và đã tạo ra một trong những đồ án thiết kế đầu tiên của máy tính có khả năng lưu trữ chương trình (stored-program computer), nhưng nó không bao giờ được kiến tạo thành máy. Năm 1947 ông chuyển đến Đại học Victoria tại Manchester để làm việc, đa số trên phần mềm cho máy Manchester Mark I, lúc đó là một trong những máy tính hiện đại đầu tiên, và trở nên quan tâm tới sinh học toán học. Ông đã viết bài báo về cơ sở hóa học của sự tạo hình,[1] và ông cũng đã dự đoán được các phản ứng hóa học dao động chẳng hạn như phản ứng Belousov–Zhabotinsky, được quan sát thấy lần đầu tiên trong thập niên 1960.
Alan Turing Khoa học máy tính Tập 15
Chào mừng các bạn đã đến với khóa học khoa học máy tính của kênh Trí thức nhân loại.
Trong vài tập qua, chúng ta đã xây dựng sự hiểu biết của mình về các nguyên tắc cơ bản của khoa học máy tính, chẳng hạn như các hàm chức năng, thuật toán và cấu trúc dữ liệu.
Hôm nay, chúng ta sẽ lưu lại một bước để tìm hiểu về người đã hình thành nhiều khái niệm lý thuyết làm nền tảng cho tính toán hiện đại.
Đó chính là Alan Turing, người được xem là cha đẻ của ngành khoa học máy tính.
Alan Matheson Turing sinh năm 1912 tại London và thể hiện năng khiếu toán học và khoa học đáng kinh ngạc trong suốt quá trình giáo dục ban đầu của mình.
Bàn trải đầu tiên của ông về cái mà ngày nay chúng ta gọi là khoa học máy tính đến vào năm 1935 khi ông đang theo học thạc sĩ tại King's College ở Cambridge.
Ông tạo ra nó để giải một bài toán do nhà toán học người Đức David Hilbert đặt ra, được gọi là bài toán quyết định, decision problem, với câu hỏi như sau.
Liệu có một thuật toán lấy đầu vào là một câu lệnh được biết theo dạng logic và tạo ra câu trả lời có hoặc không luôn chính xác?
Nếu một thuật toán như vậy tồn tại, chúng ta có thể sử dụng nó để trả lời các câu hỏi như, có số nào lớn hơn tất cả các số hay không?
Câu trả lời tất nhiên là không có.
Chúng ta biết câu trả lời cho câu hỏi đó, nhưng có nhiều câu hỏi khác trong toán học mà chúng ta không biết câu trả lời.
Vì vậy, nếu thuật toán này tồn tại, chúng ta muốn biết nó.
Nhà toán học người Mỹ Alonzo Church lần đầu tiên đưa ra giải pháp cho vấn đề này vào năm 1935.
Ông đã phát triển một hệ thống biểu thức toán học gọi là giải tích lambda và chứng minh rằng không có thuật toán phổ quát nào có thể tồn tại.
Mặc dù giải tích lambda có khả năng biểu diễn bất kỳ phép tính nào, nhưng kỹ thuật toán học này rất khó áp dụng và khó hiểu.
Cùng lúc, ở bên kia Đại Tây Dương, Alan Turing đã đưa ra cách tiếp cận của riêng mình để giải quyết bài toán quyết định.
Ông đã đề xuất một máy tính toán giả định mà ngày nay chúng ta gọi là máy Turing.
Máy Turing đã cung cấp một mô hình tính toán đơn giản nhưng mạnh mẽ.
Mặc dù sử dụng toán học hoàn toàn khác, chúng tương đương về mặt chức năng với giải tích lambda về sức mạnh tính toán.
Tuy nhiên, sự đơn giản tương đối của chúng đã khiến chúng trở nên phổ biến hơn nhiều trong lĩnh vực khoa học máy tính đang phát triển.
Trên thực tế, chúng đơn giản đến mức tôi sẽ giải thích ngay bây giờ.
Máy Turing là một thiết bị tính toán lý thuyết được trang bị một băng nhớ dài vô hàng để lưu trữ các ký hiệu
và một thiết bị gọi là đầu đọc, ghi, có thể đọc và ghi hoặc sửa đổi các ký hiệu trên băng đó.
Ngoài ra, còn có một biến trạng thái mà trong đó chúng ta có thể chữa một phần thông tin về trạng thái hiện tại của máy
và một tập hợp các quy tắc mô tả những gì máy làm.
Với một trạng thái và ký hiệu hiện tại mà máy đang đọc, quy tắc có thể được viết một ký hiệu lên băng,
thay đổi trạng thái của máy, di chuyển đầu đọc, ghi sang trái hoặc phải theo một điểm hoặc bất kỳ sự kết hợp nào của những điều này.
Để dễ hình dung hơn, chúng ta hãy làm việc thông qua một ví dụ đơn giản.
Máy Turing đọc một chuỗi gồm những số 1 và kết thúc với số 0.
Nó có nhiệm vụ tính toán xem chuỗi số này có phải là một số chẳng hay không.
Nếu điều đó là đúng thì máy sẽ ghi số 1 vào băng, còn nếu sai thì nó sẽ ghi số 0 vào băng.
Đầu tiên, chúng ta cần xác định các quy tắc của máy Turing.
Nếu trạng thái là chẳng và ký hiệu hiện tại của băng là 1,
thì ta cập nhật trạng thái máy thành lẻ và di chuyển đầu đọc sang phải để đọc số tiếp theo.
Tình huống khác, nếu trạng thái đang là chẳng và ký hiệu hiện tại bằng 0,
có nghĩa là chúng ta đã đến vị trí cuối cùng của chuỗi ký tự.
Sau đó, chúng ta ghi 1 vào băng và thay đổi trạng thái của máy thành halt, dừng lại,
và máy Turing đã hoàn thành việc tính toán.
Chúng ta cũng cần các quy tắc khi máy Turing ở trạng thái lẻ.
Một quy tắc cho ký hiệu trên băng là số 0, và một quy tắc khác cho ký hiệu trên băng là 1.
Cuối cùng, chúng ta cần xác định trạng thái bắt đầu cho máy, giả sử chúng ta đặt là chẳng.
Bây giờ, chúng ta đã xác định các quy tắc trong trạng thái khởi động của máy Turing mà có thể so sánh với một chương trình máy tính.
Chúng ta có thể chạy nó trên một ví dụ cụ thể, với số đầu vào là 1, 1, 0 đã được lưu trữ trên băng.
Trạng thái đầu tiên của chúng ta là chẳng, và số đầu tiên chúng ta thấy là 1.
Điều đó phù hợp với quy tắc trên cùng trong bản.
Vì vậy, chúng ta thực hiện nguyên tắc này, đó là cập nhật trạng thái thành số lẻ và di chuyển đầu độc ghi sang bên phải một nất.
Ok, bây giờ chúng ta lại thấy một số 1 khác trên băng.
Nhưng lần này trạng thái đang là lẻ, và vì vậy chúng ta thực hiện quy tắc thứ 3 trong bản.
Đó là đặt trạng thái trở lại chẳng và di chuyển đầu độc ghi sang phải một nất.
Bây giờ, chúng ta thấy số 0 và trạng thái hiện tại của chúng ta là chẳng.
Vì vậy, chúng ta thực hiện quy tắc thứ 2 là viết số 1 vào băng để biểu thị câu trả lời là đúng.
Đó là một số chẳng, và cuối cùng máy tạm dừng.
Đó là cách mà máy Turing hoạt động.
Nó khá đơn giản phải không nào?
Vì vậy, bạn có thể tự hỏi tại sao người ta lại thân tượng cổ máy này như vậy?
Việc thân tượng nó cho thấy rằng cổ máy giả định đơn giản này có thể thực hiện bất kỳ phép tính nào nếu có đủ thời gian và bộ nhớ.
Nó là một máy tính đa năng.
Chương trình vừa rồi của chúng ta chỉ là một ví dụ đơn giản.
Nhưng với đủ trạng thái, quy tắc và băng, bạn có thể xây dựng bất cứ thứ gì.
Chẳng hạn như trình duyệt web, hoặc trò chơi điện tử Warcraft, hoặc bất cứ thứ gì.
Tất nhiên, nó sẽ không được hiệu quả lắm.
Nhưng về mặt lý thuyết thì có thể.
Và đó là lý do tại sao, với tư cách là một mô hình máy tính, đó là một ý tưởng mạnh mẽ.
Trên thực tế, xét về những gì nó có thể và không thể tính toán, thì không có máy tính nào mạnh hơn máy Turing.
Mọi hệ thống máy tính hiện đại, máy tính sách tay, điện thoại thông minh,
và thậm chí cả chiếc máy tính nhỏ bên trong lò vi sóng và bộ điều khiển nhiệt đều là máy Turing.
Để trả lời bài toán quyết định của Hilbert, Turing đã áp dụng những chiếc máy Turing mới này
vào một câu đố tính toán hấp dẫn có tên là Halting Problem.
Dịch nông na ra tiếng Việt là bài toán dừng.
Trong lý thuyết khả tính, bài toán dừng có thể diễn đạt như sau.
Cho trước một chương trình máy tính, quyết định xem chương trình đó có chạy mãi mãi hay không.
Thật không may, Alan Turing đã chứng minh rằng không tồn tại thuật toán nào giải quyết bài toán dừng cho mọi cặp chương trình và dữ liệu nào.
Bài toán dừng là không thể quyết định được trên máy Turing thông qua một mâu thuẫn logic thông minh.
Hãy nhớ rằng, Turing đã chứng minh rằng máy Turing có thể thực hiện bất kỳ pháp tính nào.
Vì vậy, giải pháp cho vấn đề tạm dừng này chứng minh rằng không phải tất cả các vấn đề đều có thể được giải quyết bằng tính toán.
Luận án Church và Turing đã chỉ ra rằng có những giới hạn đối với khả năng của máy tính.
Cho dù bạn có bao nhiêu thời gian hay bộ nhớ, thì vẫn có một số vấn đề không thể giải quyết được.
Vào thời điểm này năm 1936, Turing mới 24 tuổi và chỉ mới bắt đầu sự nghiệp của mình.
Từ năm 1936 đến năm 1938, ông hoàn thành chương trình tiến sĩ tại Đại học Princeton dưới sự hướng dẫn của Church.
Sau khi tốt nghiệp, ông trở lại Cambridge.
Không lâu sau, vào năm 1939, nước Anh bị lôi kéo vào thế chiến thứ hai.
Phẩm chất thiên tài của Turing nhanh chóng được áp dụng vào nỗ lực chiến tranh.
Trên thực tế, một năm trước khi chiến tranh bắt đầu, ông ấy đã làm việc bán thời gian tại trường của Chính phủ Anh và trường Cypher,
trong nhóm phá mã của Anh có trụ sở tại Bletchley Park.
Một trong những nỗ lực chính của ông là tìm ra cách giải mã các thông tin liên lạc của Đức,
đặc biệt là những thông tin đã được mã hóa bởi máy Enigma.
Những cổ máy này dùng để xáo trộn văn bản,
kiểu như bạn gõ các chữ cái H, E, L, L, O và các chữ cái X, W, D, B, G sẽ xuất hiện.
Quá trình này được gọi là mã hóa.
Sự mã hóa này không phải ngẫu nhiên.
Nguyên tắc mã hóa được xác định bởi một loạt các rotor có thể sắp xếp lại trên đỉnh của cổ máy Enigma.
Mỗi rotor có 26 vị trí quay.
Ngoài ra, còn có một bảng cắm ở phía trước máy cho phép hoán đổi các cặp chữ cái.
Tổng cộng có hàng tỷ cài đặt mã khóa khả thi đối với cổ máy này.
Nếu bạn có máy Enigma của riêng mình và bạn biết cài đặt các rotor và bảng cắm chính xác,
bạn có thể gõ X, W, D, B, G và từ Hello sẽ xuất hiện.
Nói cách khác, bạn đã giải mã thông điệp thành công.
Tất nhiên, quân đội Đức đã không chia sẻ cài đặt máy Enigma của họ trên mạng xã hội.
Vì vậy, quân đồng minh đã phải phá mã bằng hàng tỷ tổ hợp rotor và bảng cắm.
Không có cách nào để kiểm tra tất cả chúng bằng tay.
May mắn cho Turing, những cổ máy Enigma và những người vận hành chúng không hoàn hảo.
Giống như một lỗ hổng quan trọng là một chữ cái sẽ không bao giờ được mã hóa như chính nó.
Ví dụ như một chữ H không bao giờ được mã hóa dưới dạng là chữ H.
Turing, dựa trên công việc trước đó của những người phá mã Ba Lan,
đã thiết kế một hệ thống cơ điện tử cho mục đích đặc biệt.
Máy tính này được gọi là Bombis đã từng dùng lỗ hổng này.
Nó đã thử rất nhiều các kết hợp cài đặt của Enigma cho một thông điệp được mã hóa nhất định.
Nếu Bombis tìm thấy cài đặt dẫn đến một bức thư được mã hóa như chính nó,
mà chúng ta biết rằng máy Enigma không thể làm được.
Sự kết hợp đó đã bị loại bỏ. Sau đó, máy di chuyển để thử sự kết hợp khác.
Vì vậy, Bombis được sử dụng để thu hẹp đáng kể số lượng cài đặt bí ẩn có thể xảy ra.
Điều này cho phép các nhà phá mã thu hẹp về các giải pháp có thể xảy ra,
nhằm tìm kiếm những thứ như các từ tiếng Đức phổ biến trong các đoạn văn bản được giải mã.
Theo định kỳ, người Đức sẽ nghi ngờ ai đó đang giải mã thông tin liên lạc của họ và nâng cấp cổ máy Enigma.
Kiểu như họ sẽ thêm những rotor khác vào để tạo ra nhiều tổ hợp mã hóa khác.
Họ thậm chí còn xây dựng các máy mã hóa hoàn toàn mới.
Trong suốt cuộc chiến, Turing và các đồng nghiệp của ông tại công viên Bletchley đã làm việc không mệt mỏi để đánh bại các cơ chế này
và nói chung là thông tin tình báo thu được từ hệ thống liên lạc được giải mã của Đức.
Điều này đã tạo nên chiến thắng lịch sử cho các đồng minh.
Sau khi cuộc chiến kết thúc, Turing quay trở lại học viện và đóng góp nhiều vào nỗ lực xây dựng chiếc máy tính điện tử ban đầu như Manchester Mark I.
Đó là một máy tính có thể lưu trữ chương trình và có tầm ảnh hưởng rất lớn.
Tuy nhiên, đóng góp nổi tiếng nhất của Turing sau chiến tranh là về trí tuệ nhân tạo,
một lĩnh vực quá mới mẻ đến nỗi nó thậm chí còn không có tên đó cho đến năm 1956.
Đó là một chủ đề lớn, vì vậy chúng ta sẽ tiếp tục nó trong các tập sau.
Năm 1950, Turing có thể hình dung ra một tương lai mà máy tính đủ mạnh để thể hiện trí thông minh tương đương
hoặc ít nhất là không thể phân biệt được với trí thông minh của con người.
Turing công nhận rằng một máy tính xứng đáng được gọi là thông minh nếu nó có thể đánh lừa con người tin rằng đó là con người.
Điều này đã trở thành cơ sở của một bài kiểm tra đơn giản mà bây giờ được gọi là bài kiểm tra Turing.
Hãy tưởng tượng rằng bạn đang trò chuyện với hai người khác nhau mà không được nhìn thấy đối tượng và không thể nghe được giọng nói,
kiểu như đang nhắn tin bằng cách gửi qua lại các văn bản đã được đánh máy.
Bạn có thể hỏi bất kỳ câu hỏi nào bạn muốn và bạn sẽ nhận được câu trả lời.
Nhưng một trong hai người đó thực sự là một chiếc máy tính.
Nếu bạn không thể phân biệt cái nào là người và cái nào là máy tính thì máy tính sẽ vượt qua bài kiểm tra này.
Có một phiên bản hiện đại của thử nghiệm này được gọi là thử nghiệm Turing công khai hoàn toàn tự động
để phân biệt máy tính và con người hay gọi tắt là hình ảnh xác thực.
Những thứ này thường được sử dụng trên Internet để ngăn các hệ thống tự động làm những việc như đăng spam trên trang web.
Tôi phải thừa nhận là đôi khi tôi cũng không thể đọc những thứ ngoài ngoạc đó nói gì.
Điều đó liệu có đồng nghĩa tôi là một máy tính không nhỉ?
Alan Turing đã từ trần vào năm 1954 khi chỉ mới 41 tuổi.
Nhiều thứ đã được đặt tên để ghi nhận những đóng góp của Turing cho lý thuyết khoa học máy tính.
Nhưng có lẽ giành giá nhất trong số đó là giải thưởng Turing, giải thưởng cao quý nhất trong lĩnh vực khoa học máy tính,
tương đương với giải Nobel về vật lý, khoa học hoặc các ngành khoa học khác.
Mặc dù cuộc đời ngắn ngủi, Alan đã truyền cảm hứng cho thế hệ đầu tiên của các nhà khoa học máy tính
và đặt nền móng quan trọng cho chỉ nguyên chỉ thuật số mà chúng ta có thể tận hưởng ngày nay.
Tôi rất muốn được chia sẻ về nhiều kiến thức khác nhau.
Hãy nhấn vào các video xuất hiện trên màn hình hiện tại, và tôi sẽ gặp bạn ở đó.
Xin cảm ơn vì đã xem đoạn phim này, và nếu thấy thông tin hữu ích thì vui lòng nhấn thích và đăng ký ở bên dưới
nhằm khuyến khích kênh tạo thêm nhiều phim khác.