Máy Turing xử lý gì trên một dải băng?
Một máy Turing là một mô hình toán học của một máy tính nói chung. Nó là một thiết bị lý thuyết thao tác các biểu tượng chứa trên một dải băng. Máy Turing không nhằm mục đích như một công nghệ tính toán thực tế, mà là một thí nghiệm tư duy đại diện cho một máy tính-bất cứ điều gì từ một siêu máy tính tiên tiến để một nhà toán học với một cây bút chì và giấy. Người ta tin rằng nếu một vấn đề có thể được giải quyết bằng một thuật toán, có tồn tại một máy Turing giải quyết vấn đề. Thật vậy, đây là tuyên bố của luận án Church-Turing. Hơn nữa, người ta biết rằng tất cả mọi thứ có thể được tính toán trên các mô hình tính toán khác mà chúng ta biết ngày nay, chẳng hạn như máy RAM, Trò chơi cuộc sống của Conway, automata di động hoặc bất kỳ ngôn ngữ lập trình nào có thể được tính toán trên máy Turing. Vì máy Turing dễ phân tích về mặt toán học và được cho là mạnh mẽ như bất kỳ mô hình tính toán nào khác, máy Turing là mô hình được sử dụng phổ biến nhất trong lý thuyết độ phức tạp.
biểu tượng