CSC 341 (Fall 2021)

Reading: Introduction to Turing Machines

Introduction to Turing Machines

In our exploration of computational models, we’ve moved from relatively limited models—regular languages—to more expressive models—context-free languages. You might wonder if there is a model that captures exactly what a modern computer can do. This model is our terminal point in the study of fundamental computational models: the Turing machine. Over the next few days, we’ll learn about this model of computation and analyze it in depth because it is the foundation on which we will build our study of complexity theory.

Reading


Reading Problem (Once More, With Turing)

Give a implementation-level diagram of a Turing machine that decides the language \(L = \{\, 0^n 1^n \mid n \geq 0 \,\}\).