Giới thiệu máy Turing
Máy Turing là một thiết bị chấp nhận chấp nhận các ngôn ngữ (tập hợp có thể liệt kê một cách đệ quy) được tạo bởi các ngữ pháp loại 0. Nó được phát minh vào năm 1936 bởi Alan Turing.
Định nghĩa
Máy Turing (TM) là một mô hình toán học bao gồm một dải băng dài vô hạn được chia thành các ô mà đầu vào được đưa ra. Nó bao gồm một đầu đọc băng đầu vào. Thanh ghi trạng thái lưu trữ trạng thái của máy Turing. Sau khi đọc một ký hiệu đầu vào, nó được thay thế bằng một ký hiệu khác, trạng thái bên trong của nó bị thay đổi và nó di chuyển từ ô này sang phải hoặc trái. Nếu TM đạt đến trạng thái cuối cùng, chuỗi đầu vào được chấp nhận, nếu không sẽ bị từ chối.
Một TM có thể được mô tả chính thức là một bộ 7 (Q, X, ∑, δ, q 0 , B, F) trong đó -
Q là một tập hợp hữu hạn các trạng thái
X là bảng chữ cái băng
∑ là bảng chữ cái đầu vào
δlà một hàm chuyển tiếp; δ: Q × X → Q × X × {Left_shift, Right_shift}.
q0 là trạng thái ban đầu
B là biểu tượng trống
F là tập hợp các trạng thái cuối cùng
So sánh với automaton trước đó
Bảng sau đây cho thấy sự so sánh về cách một máy Turing khác với Finite Automaton và Pushdown Automaton.
| Máy móc | Cấu trúc dữ liệu ngăn xếp | Tính xác định? |
|---|---|---|
| Automaton hữu hạn | NA | Đúng |
| Pushdown Automaton | Cuối cùng trong lần xuất đầu tiên (LIFO) | Không |
| Máy turing | Băng vô hạn | Đúng |
Ví dụ về máy Turing
Máy turing M = (Q, X, ∑, δ, q 0 , B, F) với
- Q = {q 0 , q 1 , q 2 , q f }
- X = {a, b}
- ∑ = {1}
- q 0 = {q 0 }
- B = ký hiệu trống
- F = {q f }
δ được đưa ra bởi -
| Biểu tượng bảng chữ cái băng | Trạng thái hiện tại 'q 0 ' | Trạng thái hiện tại 'q 1 ' | Trạng thái hiện tại 'q 2 ' |
|---|---|---|---|
| a | 1Rq 1 | 1Lq 0 | 1Lq f |
| b | 1Lq 2 | 1Rq 1 | 1Rq f |
Ở đây quá trình chuyển đổi 1Rq 1 ngụ ý rằng ký hiệu ghi là 1, băng di chuyển sang phải, và trạng thái tiếp theo là q 1 . Tương tự, quá trình chuyển đổi 1Lq 2 ngụ ý rằng ký hiệu ghi là 1, băng di chuyển sang trái và trạng thái tiếp theo là q 2 .
Sự phức tạp về thời gian và không gian của một cỗ máy Turing
Đối với máy Turing, độ phức tạp thời gian đề cập đến số đo số lần băng di chuyển khi máy được khởi tạo cho một số ký hiệu đầu vào và độ phức tạp không gian là số ô của băng được viết.
Thời gian phức tạp tất cả các chức năng hợp lý -
T(n) = O(n log n)
Độ phức tạp không gian của TM -
S(n) = O(n)