- BÀI 8: Máy Turing. - Ngôn ngữ của TM. - Máy Turing = Turing Machine (TM). - Cấu trúc dữ liệu của TM. - Đầu đọc có thể di chuyển sang trái hoặc phải. - Những trạng thái đặc biệt cho việc bác bỏ và chấp thuận có hiệu lực tức thì. - Thành phần của TM. - Ký hiệu dấu trắng ␣ là một ký hiệu đặc biệt và. - Cấu hình ban đầu chỉ có xâu vào và phần còn lại là ký hiệu. - Tại mỗi bước tính toán:. - Đọc ký hiệu của ô hiện tại trên băng mà con trỏ trỏ tới. - Có thể cập nhật ký hiệu trên ô đang được trỏ tới đó. - a là ký hiệu được đọc, thuộc ô hiện tại trên băng - b là ký hiệu sẽ được ghi vào ô hiện tại trên băng - R là chiều dịch chuyển (L: left, R: right). - Thao tác chỉ đọc ký hiệu. - Tam dừng và chấp thuận (Halt and accept): Nếu đạt được trạng thái chấp thuận thì dừng ngay lập tức. - Tạm dừng và bác bỏ (Halt and reject): Nếu đạt được trạng thái bác bỏ thì dừng ngay lập tức. - TM sau đoán nhận ngôn ngữ L = 01*0. - Đưa ra TM đoán nhận ngôn ngữ L = 0 n 1 n Thuật toán để xây dựng TM cho ngôn ngữ trên. - Nếu không gặp số 1 nào → Chuyển sang trạng thái Reject. - Lịch sử tính toán (Computation history):. - Máy Turing ≡ bộ 7 (hay 7 chiều). - Q: Tập trạng thái (hữu hạn. - q 0 ∈ Q: Trạng thái bắt đầu. - q accept ∈ Q: Là tập các trạng thái chấp thuận. - q reject ∈ Q: Là tập các trạng thái bác bỏ, q accept 6= q reject. - Cấu hình của TM có ý nghĩa:. - Tập hợp các xâu được TM đoán nhận = ngôn ngữ của TM. - Ngôn ngữ quyết định được (Decidable): Khi đọc một xâu đầu vào. - TM sẽ luôn luôn đạt được trạng thái dừng. - TM sẽ chấp thuận xâu đó khi nó ∈ ngôn ngữ của TM - TM sẽ bác bỏ xâu đó khi nó 6∈ ngôn ngữ của TM. - Ngôn ngữ được đoán nhận bởi máy Turing (Recursivly Enumerable):. - TM sẽ luôn dừng và chấp thuận (halt and accept) một xâu ∈ ngôn ngữ của TM. - Nếu xâu đó 6∈ ngôn ngữ của TM, thì máy sẽ rơi vào trạng thái dừng và bác bỏ hoặc lặp. - Gọi một ngôn ngữ là có thể được đoán nhận bởi máy Turing (TRL) nếu tồn tại một máy Turing đoán nhận ngôn ngữ đó Định nghĩa 2. - Gọi một ngôn ngữ là Turing-có thể quyết định được hay đơn giản có thể quyết định nếu tồn tại một máy Turing quyết định ngôn ngữ đó. - Tất cả ngôn ngữ có thể quyết định đều là Turing có thể đoán nhận. - Tập ngôn ngữ. - Mô tả máy Turing M quyết định ngôn ngữ A = {0 2 n | n ≥ 0}. - Thuật toán của TM quyết định A:. - Đảo từ trái qua phải dọc theo băng, xóa đi tất cả các ký hiệu 0. - Nếu ở bước 1, băng chỉ chứa 1 ký hiệu 0 thì chấp thuận 3. - Nếu ở bước 1, băng chứa nhiều hơn 1 ký hiệu 0 và số lượng. - ký hiệu 0 là 1 số lẻ thì bác bỏ. - Biểu đồ trạng thái. - δ Minh họa như trên biểu đồ trạng thái. - Lịch sử tính toán
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt