On 14 Feb 2014, at 21:32, LizR wrote:
On 15 February 2014 09:12, meekerdb <[email protected]> wrote:
On 2/14/2014 8:14 AM, Bruno Marchal wrote:
With some definition of the abacus, it is Turing universal. With
others it is not.
The slide rules is not Turing universal. You can add and multiply
approximation of natural numbers only, or, if you want, you can
analogically add and multiply the real numbers, and that is not
Turing universal. (That is not entirely obvious).
That's an interesting point to me (I own a collection of circular
slide rules). Of course you can add and subtract on a slide rule as
well as multiply, divide, exponentiate, and compute the value of
other functions encoded on the rule (sin, tan), but the rule doesn't
do it by itself; you provide the sequence of operations consisting
of reading a cursor and moving the rule. So why would that not be
Turing universal?
I would guess because it isn't digital, but analogue? 'cause Turing
machines use discrete symbols, while slide rules use a continuous
scale?
Yes, you can sum up in that way.
Formally you can relate that to the fact that the first order theory
of the real is not Turing complete (indeed it is decidable).
In analysis, if you get a sequence like 0.9, 0.99, 0.999, ..., and you
know that it converge, but you don't know that it converge toward 1
(it might converge toward 0, 99999999...99999998), you still know that
your problem admits a solution (and indeed Newton or Sturm Liouville
provided algorithm to find those solutions when they exist). But the
digital world is more demanding, as it needs, not just better and
better approximations, but it needs exact solutions.
Bruno
http://iridia.ulb.ac.be/~marchal/
--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/groups/opt_out.
