Making a "quiz" using Javascript

Lasse Reichstein Nielsen wrote:

Michael Wojcik <mwojcik (AT) newsguy (DOT) com> writes:

That's not exactly what "Turing-complete" means, but it's pretty
close. (In practice, real-world implementations of programming
languages are limited by real-world computers, which have finite
storage and execution time, so they're really equivalent to bounded
Turing machines, which are equivalent to push-down automata, which
are not Turing-complete. But we generally ignore that detail.)

Pedantry: Bounded turing machines (BTM) are more powerfull than
push-down automata (PDA). BTMs recognize the context sensitive
languages, whereas PDAs recognize the context free languages. An
example of a language recognized by a BTM but not a PDA is
{ ww | w in S* } (where S is the input alphabet).

Sorry; I meant finite TMs (finite in number of states and length of
tape, regardless of input size) are equivalent to PDAs.

"Bounded" TMs have space that's limited to the size of the input.
There are generalizations; for example, Linear Bounded TMs have space
that's a constant multiple of the input size, and Generalized Bounded
TMs have space that's some function of the input size.

As Lasse correctly points out, BTMs are more powerful than PDAs.
(LBTMs are less powerful than unbounded TMs. I think GBTMs are
equivalent to unbounded TMs, but it's been years since I did
computation theory.)

Real-world implementations of programming languages are equivalent to
finite TMs, since they can have input that's larger than the storage
available to them.

--
Michael Wojcik
Micro Focus
Rhetoric & Writing, Michigan State University