11
$\begingroup$

I am teaching Theory of Computation for the first time soon, and need a short introduction and justification to motivate students who have only Introductory Programming behind them. I am torn between:

(1) Emphasizing the limits of computation, i.e., there is no universal debugging program (Turing, Halting.)

(2) Emphasizing the practical value of searching webpages to gather data using regular expressions, leading to automata, coding, etc.

The choice is between emphasizing the negative—the ultimate limits on computation—or emphasizing the positive—what's achievable with proper understanding of the theory. Suggestions welcomed!

Improve this question
$\endgroup$
1
  • $\begingroup$ if you want students to get into programming, there is a website called code.org It is great for ages > 4 $\endgroup$
    – MissC
    Commented Oct 23, 2015 at 23:42

2 Answers 2

Reset to default
4
$\begingroup$

They need at least a passing acquaintance with both aspects. There are many practical uses (regular expressions for patterns, context free grammars revolutionized programming languages in ways that are hard to appreciate unless you learned classic BASIC or early FORTRAN and later saw Algol or Pascal for the first time) to highlight. The limits of computation aspects (and problems like P = NP, complexity theory in general) are in my opinion central in any deeper understanding of computing, and (particularly NP completeness) are required knowledge for any professional programmer.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thank you. I used your point re revolutionizing programming languages in a presentation. $\endgroup$
    – Joseph O'Rourke
    Commented Oct 26, 2015 at 18:27
2
$\begingroup$

(I should write this when I have more than a few minutes. Hopefully updates will follow.)

There are too many aspects to cover: big data, human computer interaction, computing using conventional architectures, computing using not-yet-realized architectures (nanocomputing, swarm- and cloud- and quantum-computing), computing with limited resources, complexity classes, privacy concerns, the list goes on.

In order to have a handle on any of these, one should have some acquaintance with the foundations of algorithms, philosophy of computing, mathematical logic, and basic theory on simple architectures. Even if your course is required to focus on one section, you can tie in to several others. A. K. Dewdney's "The New Turing Omnibus" is a must read for any mathematician/educator interested in classical computer science. I hope a new one comes out for the present generation so that I can understand some of current computer science before I miss out.

Gerhard "Not Ready To Be Old" Paseman, 2015.10.20

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the reminder of Dewdney's Omnibus, which I have mined in other courses. $\endgroup$
    – Joseph O'Rourke
    Commented Oct 20, 2015 at 21:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.