Máy Turing

Các Khái Niệm trong Khoa Học Máy Tính

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Từ Ôtômát đến Máy Turing

  • Ôtômát hữu hạn: Bộ nhớ hạn chế, xử lý ngôn ngữ chính quy.
  • Ôtômát đẩy xuống: Bộ nhớ ngăn xếp, xử lý ngôn ngữ phi ngữ cảnh.
  • Máy Turing: Bộ nhớ không giới hạn (băng vô hạn), giải mọi bài toán tính được.

Minh họa Alan Turing

Các Khái Niệm trong Khoa Học Máy Tính

Máy Turing là gì?

Sơ đồ cách Máy Turing hoạt động

Máy Turing

  • Máy trừu tượng với băng vô hạn.
  • Đọc và ghi ký hiệu.
  • Có thể mô phỏng mọi thuật toán.
Các Khái Niệm trong Khoa Học Máy Tính

Máy Turing qua phép loại suy

Minh họa căn bếp với đầu bếp làm theo công thức như phép loại suy cho Máy Turing

Bếp & Đầu bếp như Máy Turing

  • Mặt bếp là băng.
  • Các ô trên mặt bếp là ô nhớ.
  • Nguyên liệu là ký hiệu.
  • Đầu bếp là đầu đọc/ghi.
  • Sách công thức là chương trình điều khiển toàn bộ.
Các Khái Niệm trong Khoa Học Máy Tính

Vì sao Máy Turing quan trọng?

Máy Turing & Tính toán được

  • Có thể mô phỏng mọi thuật toán
  • Xác định ranh giới những gì máy tính giải được
  • Giới thiệu bài toán không quyết định (ví dụ: Bài toán dừng)
  • Đặt nền tảng cho lý thuyết tính toán hiện đại
Các Khái Niệm trong Khoa Học Máy Tính

Bài toán dừng

  • Câu hỏi: Ta có dự đoán được chương trình sẽ dừng hay chạy mãi với một đầu vào cụ thể không?
  • Nhận định của Turing: Không tồn tại thuật toán chung cho mọi chương trình.
  • Kết luận: Bài toán dừng là không quyết định; có bài toán không có lời giải thuật toán.
  • Hệ quả: Giới hạn tính toán ảnh hưởng mật mã & AI

Một sơ đồ minh họa Bài toán dừng

Các Khái Niệm trong Khoa Học Máy Tính

Ayo berlatih!

Các Khái Niệm trong Khoa Học Máy Tính

Preparing Video For Download...