Ở đây chúng ta sẽ xem cách tạo một máy Turing cho ngôn ngữ L ={WW | W thuộc về {0, 1}}. Vì vậy, điều này đại diện cho một loại ngôn ngữ mà chúng ta sẽ chỉ sử dụng hai ký tự 0 và 1. W là một chuỗi. Vì vậy, nếu w =10110, do đó máy Turing sẽ chấp nhận chuỗi z =1011010110.
Để giải quyết vấn đề này, chúng tôi sẽ sử dụng cách tiếp cận này. Việc đầu tiên là tìm điểm giữa của chuỗi, chúng ta sẽ chuyển a 0 thành x và 1 thành y. Sau khi liên tục làm điều đó, một điểm sẽ đạt được khi tất cả các số 0 và 1 đã được chuyển thành x và x tương ứng. Bây giờ, chúng ta đang ở điểm giữa của chuỗi. Vì vậy, mục tiêu đầu tiên của chúng tôi đã hoàn thành.
Bây giờ, chuyển đổi tất cả x và y ở bên trái điểm giữa thành 0 và 1. Bây giờ nửa đầu của chuỗi có dạng 0 và 1. Nửa sau của chuỗi có dạng x và y.
Bây giờ, hãy bắt đầu lại từ đầu chuỗi. Nếu bạn có số 0 thì hãy chuyển nó thành x và chuyển sang phải cho đến khi đến nửa sau, ở đây nếu chúng ta tìm thấy x thì hãy chuyển nó thành ô trống (B). Sau đó quay ngược lại cho đến khi tìm được x hoặc x. Chúng tôi chuyển đổi số 0 hoặc số 1 ở bên phải của nó thành x hoặc y tương ứng và tương ứng, chuyển đổi x hoặc y của nó ở nửa sau của chuỗi thành khoảng trống (B).
Tiếp tục làm điều này cho đến khi chuyển đổi tất cả các ký hiệu ở phần bên trái của chuỗi thành x và y và tất cả các ký hiệu ở bên phải của chuỗi thành khoảng trống. Khi một phần được chuyển đổi hoàn toàn nhưng một số ký hiệu ở nửa còn lại được giữ nguyên thì chuỗi đó sẽ không được chấp nhận. Nếu chúng ta không tìm thấy x hoặc y trong nửa sau thì tương ứng với 0 hoặc 1 tương ứng trong nửa đầu. Sau đó, chuỗi cũng sẽ không được chấp nhận.
Sơ đồ chuyển đổi trạng thái
