Comment by kcl | Hacker News Reader

Comment by kcl | Hacker News Reader

Parent Full thread

There are two competing definitions of Turing complete here.

1. The mathematical definition of Turing completeness: models which can simulate the computation of a hypothetical Turing machine. Idealized circuits are an example of this. Turing machines are an example of this. Programs with infinite memory are an example of this.

2. The colloquial definition of Turing completeness: this is naturally ill-defined, but it roughly means an automated, finite model that performs arbitrary computation. I would say that a robotic Lego Turing machine is Turing complete. C is certainly Turing complete in this sense. Basic HTML isn't. The set of regexes (e.g, unix wildcards) isn't.

However, if I can choose a large enough regex, I can construct a decider for a given finite language. How then are regexes less powerful than C? The answer is they are just as powerful in the finite case, unless we set reasonable limits on what we mean by 'finite' and 'automated.'

This HTML+CSS is not Turing complete. The idealized version of this HTML+CSS is not Turing complete (unless you strangely accept the idealization of a "hand pressing tab space"). This HTML+CSS is also not Turing complete in the colloquial sense: it doesn't live up to the generally accepted notion of automation. It isn't executed by the machine.

I'm still unsatisfied with your definitions because you're not separating the concept of the expression of a computation from the execution of that computation. A formalized process (read: language) is Turing complete if it can express the simulation of a Turing machine. Since we know a Turing machine can be used to compute anything that is computable, we then know our formalized process can compute all that is compute - it is Turing Complete.

Programs cannot be Turing complete. The concept does not apply, just as a basketball cannot be sad. Programming languages can be Turing complete. A robotic Lego "Turing machine" is not Turing complete, but not because it's not a realization of a Turing machine, but because it's not a formalized process. Robotic Legos, however, would be Turing complete, since that is the formal process used to simulate the Turing machine.

> However, if I can choose a large enough regex, I can construct a decider for a given finite language.

What do you mean by this? What is a "decider"? What do you mean by a finite language?

Language: http://en.wikipedia.org/wiki/Formal_language

Decision problem: http://en.wikipedia.org/wiki/Decision_problem

Decider: http://en.wikipedia.org/wiki/Machine_that_always_halts

These are fairly foundational concepts when talking about computational complexity.

> However, if I can choose a large enough regex, I can construct a decider for a given finite language. How then are regexes less powerful than C?

Ok so upon reflection I think I see what you are getting at. Practical computers are have limited memory and so are, in principle, equivalent to a finite state machine.

So anything a practical computer can do a, perhaps ridiculously large, regular expression can also do?

Is that close?

unless you strangely accept the idealization of a "hand pressing tab space"

Why is that stranger than my computer requiring electricity to run?

Our field is founded on the idea that mechanical computation is preferred to human computation.

So would HTML+CSS+two drinky birds tapping the keys a'la Homer Simpson count?

Heh, you should look up what "computers" meant from the 17th century right until World War II. Our field is founded on the idea that machines have the same power as humans working like machines, and that that power's the most a machine (or a human working like a machine) can have.

Reply on news.ycombinator.com