Đang chuẩn bị liên kết để tải về tài liệu:
Lý thuyết ngôn ngữ hình thức và ôtômát - Chương 4

MÁY TURING Khi thiết kế và cài đặt một phần mềm tin học cho một vấn đề nào đó, ta cần phải đưa ra phương pháp giải quyết mà thực chất đó là thuật toán giải quyết vấn đề này. Rõ ràng rằng, nếu không tìm được một phương pháp giải quyết thì không thể lập trình được. Chính vì thế, thuật toán là khái niệm nền tảng của hầu hết các lĩnh vực của tin học. Ta có thể hiểu khái niệm thuật toán như sau. . | CHƯƠNG IV MÁY TURING Khi thiết kế và cài đặt một phần mềm tin học cho một vấn đề nào đó ta cần phải đưa ra phương pháp giải quyết mà thực chất đó là thuật toán giải quyết vấn đề này. Rõ ràng rằng nếu không tìm được một phương pháp giải quyết thì không thể lập trình được. Chính vì thế thuật toán là khái niệm nền tảng của hầu hết các lĩnh vực của tin học. Ta có thể hiểu khái niệm thuật toán như sau. Nếu cho trước một bài toán thì một cách giải bài toán được phân định ra thành một số hữu hạn bước có kết thúc cuối cùng và đạt được kết quả mong muốn gọi là thuật toán. Về mặt lịch sử trong những năm 30 của thế kỷ trước khi khoa học và công nghệ phát triển nhân loại đã nêu ra nhiều bài toán mà không tìm thấy lời giải. Có nghĩa là không tìm được thuật toán để giải chúng. Người ta đã phải tìm cách định nghĩa chính xác khái niệm thuật toán. Năm 1936 A. Turing đã đưa ra một công cụ rất tốt để mô tả thuật toán mà ngày nay người ta gọi là máy Turing. Để ghi nhớ công lao này Hội Tin học Mỹ ACM đã đặt ra giải thưởng Turing trong tin học. Cho đến nay giải thưởng Turing là giải thưởng tin học lớn nhất thế giới. Tiếp theo Turing một số nhà khoa học khác đã đưa ra các công cụ chính xác hoá khái niệm thuật toán. Đó là các khái niệm hàm đệ quy thuật toán Marcop văn phạm sinh của N. Chomsky. Những khái niệm này là cơ sở phát triển của việc nghiên cứu và ứng dụng thuật toán. Mặt khác chính nhờ các khái niệm này người ta cũng xác định được những bài toán không thể giải được bằng thuật toán. A. Turing đã đề xuất khái niệm máy Turing nhằm chính xác hoá khái niệm thuật toán. Thực tế đã chứng tỏ rằng máy Turing là một công cụ rất tốt để mô tả thuật toán. Trải qua nhiều thập niên lý thuyết về máy Turing đã phát triển không ngừng bởi sự đóng góp công sức của nhiều nhà khoa học trong đó có những công trình nền tảng của Hartmanis Lewis Stearns Minsky Blum Hopcroft Ullman. Thực chất máy Turing là một mô hình máy. Nó phân rã toàn bộ quá trình hoạt động ra thành các bước thao tác rất đơn giản. Bản .