- BÀI 9: Các biến thể của máy Turing. - Máy Turing tùy chọn tại chỗ. - Máy Turing bán vô hạn. - Máy Turing đa băng. - Máy Turing không đơn định. - Có rất nhiều loại máy Turing khác nhau:. - Máy Turing có khả năng ở nguyên tại chỗ (Stay-option). - Máy Turing bán vô hạn (Semi-infinite). - Chứng minh các mô hình TM là tương đương. - Để chứng minh các mô hình là tương đương → Kỹ thuật mô phỏng Ví dụ:. - Máy Turing M1 (Dạng chuẩn). - Máy Turing M2 (Một biến thể nào đó). - Đầu đọc của máy Turing loại này có khả năng không di chuyển khi thực hiện 1 chuyển dịch ↔ Có khả năng giữ nguyên vị trí. - Ví dụ. - Sự tương đương với TM chuẩn. - Mọi máy Turing tùy chọn tại chỗ đều có một máy Turing chuẩn tương đương. - Chứng minh. - Máy Turing tùy chọn tại chỗ mô phỏng một TM chuẩn (CM:. - Bỏ qua các chuyển dịch tại chỗ). - TM dạng chuẩn mô phỏng một máy Turing tùy chọn tại chỗ. - Nếu là chuyển dịch sang trái hoặc phải thì thực hiện tương tự. - Nếu là chuyển dịch tại chỗ thì thay thế bởi cặp chuyển dịch trái, phải hoặc phải, trái. - Ví dụ chứng minh. - Máy Turing chuẩn. - Là máy Turing chỉ vô hạn 1 chiều bên phải → Làm sao để xác định đầu băng?. - Mọi máy Turing bán vô hạn đều có một máy Turing chuẩn tương đương. - TM chuẩn mô phỏng 1 TM bán vô hạn. - TM bán vô hạn mô phỏng một máy Turing chuẩn. - Chèn 1 ký hiệu đặc biệt để đánh dấu là đầu bên trái trên băng. - Thêm chuyển dịch lặp vào tất cả trạng thái (ngoại trừ trạng thái chỉ nhận chuyển dịch). - TM bán vô hạn mô phỏng một máy Turing chuẩn Ý TƯỞNG: Chia sự vô hạn 2 chiều thành 1 chiều. - Tách thành 2 phần bán vô hạn. - TM bán vô hạn. - Ví dụ (1). - Ví dụ (2). - Ví dụ (3). - Ví dụ (4). - Chuỗi đầu vào sẽ nằm trên băng thứ nhất. - Định nghĩa hình thức của máy Turing đa băng. - Γ: Bộ chữ được phép viết trên băng. - Ví dụ chuyển dịch trên TM đa băng. - Sau chuyển dịch Tape 1. - Mọi máy Turing đa băng đều có một máy Turing đơn băng tương đương. - Chứng minh: (Bằng cách xây dựng). - Cần chuyển đổi 1 chuyển dịch đa băng thành 1 chuyển dịch đơn. - Thêm dấu chấm vào ký hiệu trên băng để đánh dấu đầu đọc trên băng đó. - Để mô tả một chuyển dịch từ trạng thái Q đến R ta thực hiện - Đọc lần 1 qua tất cả các ô của TM đơn băng để xác định vị trí. - các đầu đọc ảo. - Đọc lần thứ 2 và thực hiện dịch chuyển tương ứng như mô tả của TM đa băng. - Nếu mỗi lần đầu đọc của TM đơn băng đọc ô chứa ký hiệu. - Máy Turing không đơn định: Là một máy Turing có nhiều hơn 1 lựa chọn tại mỗi trạng thái. - Hàm chuyển dịch của TM không đơn định có dạng:. - Cách hoạt động của TM không đơn định. - Máy Turing. - Sự tương đương với TM. - Mọi máy Turing không đơn định có một máy Turing đơn định tương đương. - Ý tưởng chứng minh:. - Tìm kiếm một nhánh chấp thuận trên cây hoạt động của TM không đơn định. - Xây dựng TM đơn định đó như thế nào?. - Chứng minh (1). - Ta sẽ xây dựng một TM có 3 băng như trên để mô phỏng TM không đơn định. - Băng mô phỏng: Mô phỏng tính toán của TM không đơn định trên một nhánh nào đó. - Băng địa chỉ: Lưu vị trí hoạt động của nhánh đó trên cây hoạt động của TM không đơn định. - Chứng minh (2). - Ta gán một địa chỉ cho mỗi nút của cây tính toán đối với TM không đơn định:. - Ví dụ: 2322. - Chứng minh (3). - Xét ký hiệu tiếp theo trên băng 3 để xác định sự lựa chọn theo hàm chuyển của TM không đơn định. - Nếu không còn ký hiệu nào trên băng 3 → Thực hiện bước 4
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt