Tiểu luận Automat

Bây giờ chúng ta quay lại sự quan tâm chính, đó là nghiên cứu về ngôn ngữ hình thức. Mục đích trực tiếp của chúng ta là sẽ khảo sát ngôn ngữ liên hợp với máy Turing và một vài giới hạn của chúng. Bởi vì máy Turing có thể thực hiện một vài loại thuật toán tính toán nên chúng ta hy vọng tìm ra một họ ngôn ngữ kết hợp với chúng là khá rộng. Nó không chỉ bao gồm ngôn ngữ chính quy và phi ngữ cảnh mà còn nhiều loại khác như ví dụ chúng ta đã gặp ở ngoài những họ này. Câu hỏi đặt ra là liệu có một vài ngôn ngữ không được chấp nhận bởi một máy Turing. Ta sẽ trả lời câu hỏi này bằng sự chỉ ra rằng có nhiều ngôn ngữ hơn máy Turing, vì vậy sẽ có một vài ngôn ngữ mà không có máy Turing đoán nhận. Bằng chứng đưa ra là ngắn gọn và đơn giản nhưng không có cấu trúc và ít đi sâu vào bên trong của vấn đề. Đối với lý do này chúng ta sẽ thiết lập sự tồn tại của ngôn ngữ không được đoán nhận bởi máy Turing. Một con đường khác của người nghiên cứu sẽ là nhìn vào mối quan hệ giữa máy Turing và một loại nào đó của văn phạm và thiết lập một sự liên quan giữa những văn phạm này và ngôn ngữ chính quy và ngôn ngữ phi ngữ cảnh. Điều này dẫn đến tạo ra một hệ thống ngôn ngữ và qua đó dẫn đến một phương thức để phân loại họ ngôn ngữ. Một tập biểu đồ minh họa mối liên hệ giữa họ ngôn ngữ khác nhau một cách rõ ràng. Nhiều thảo luận trong chương này là chỉ đúng cho ngôn ngữ không bao gồm xâu rỗng. Hạn chế này xuất phát từ sự việc máy Turing, như chúng ta đã định nghĩa chúng, không thể chấp nhận xâu rỗng. Để tránh phải diễn đạt lại định nghĩa ta ngầm giả định rằng ngôn ngữ đã thảo luận ở trong chương này không chứa đựng ở. Nó là một vấn đề bình thường để nêu lại rõ ràng mọi thứ vì vậy ở là được gộp vào nhưng chúng ta sẽ để lại điều này cho đọc giả.