On 15 Feb 2014, at 00:15, meekerdb wrote:
On 2/14/2014 2:17 PM, LizR wrote:
On 15 February 2014 10:57, meekerdb <[email protected]> wrote:
On 2/14/2014 12:32 PM, 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, of course a real slide rule can't encode arbitrarily large
integers because it only has finitely many distinguisable locations
for the the cursor. But since a Turing machine is allowed an
infinite tape, suppose my slide rule (Sliding Machine?) is allowed
to expand the number of distinct positions arbitrarily?
So you don't think the analogue/digital thing matters? I suppose a
person using a slide rule could be trusted to correct for small
errors....or could they?
I think it matters because the power of arithmetic to encode proofs
depends on it having arbitrarily long strings of digits. But just
as Turing idealized infinite tapes, I can idealize arbitrarily large
slide rules to get arbitrarily high precision.
Not sure this works (despite my allusion to infinitely good
eyesight). You might need actual-infinite eye sight, because
arbitrary good eye sight might still ask you for an infinite
analogical task. You zoom and zoom and zoom ... and after each finite
of time, you still don't know if you get 1, or 1+
0.000000000000000000....1, for example, where digital program could,
for some reason, find the exact result.
You might keep in mind that astonishing truth (deducible from
Matiyasevitch):
- The polynomial on the reals are not Turing universal (you cannot
simulate an exponential with such polynomials)
- the polynomial on the integers are Turing universal, you can
simulate exponential, and indeed all Turing machine with them. You can
simulate the function sending the integers x on x^(x^(x^(x^...))) x
times with a integers polynomial of dgree four!, but you cannot with
any polynomials on the reals.
Bruno
Brent
--
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.
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.
