Dennis,
Yes, I remember seeing proofs that a bare-bones Turing Machine with an
infinite bidirectional tape can solve anything done by a classical computer.
I also suggest that in many cases, such a device is a way to transform any
problem that can be solved decently into one that can now be solved in
indefinite and sometimes effectively infinite, time. I wrote my thesis on a
variant of such an automaton.
But many things that are theoretically doable remain far from practical.
There are often shortcuts both in hardware and software that allow simpler
solutions using finite resources for reasonable amounts of data processed.
I recall an example from a version of mathematical LISP that I will rewrite
in python for illustration:
def is_greater(left, right):
if left <= 0 : return False
if right <= 0 : return True
return is_greater(left - 1, right - 1)
That is a beautiful mathematical way of looking at it. Given two
non-negative numbers, keep subtracting one from both sides until one is 0 or
less. At that point, you know. The original version did not use subtraction
but rather an abstract function to return a predecessor. Nice and abstract.
Too abstract.
Yes, this does not handle equality well. Easy enough to amend. But the POINT
is that comparing a trillion to a quadrillion may take some time and without
tail recursion may exhaust the stack long before it completes.
Yet for an amazing number of case, a shorter solution is as simple as
placing left in register A and right in register B and issuing a command
that compares them bitwise or something and returns a True/False in register
A as a bit, or whatever the details. Or, for big numbers, many other
techniques that are still simple and fast enough can be done such as
converting the number into a long string of decimals and comparing one at a
time till they diverge.
So for practical matters, Turing machines are no more than a debating point.
Yes, a language without exponentiation can solve a large set of problems
using repeated multiplication but how easily with it raise the
transcendental number e to the [product of the transcendental number pi
times the odd square root of -1] and get a result of -1?
Heck, who needs multiplication? Repeated addition might do, to a point?
Or, go back to the Turing machine where you, well, why bother?
In the real world, the path to progress in the PRESENT often uses
improvements that let you program at increasing levels of abstraction and
allows underlying details to be handled for you with some confidence. So
even though many programming constructs do an implicit goto when viewed at
machine language levels, they are usually somewhat hidden when viewed as
loops or exception handling. Heck, we now often hide loops.
-----Original Message-----
From: Python-list <python-list-bounces+avigross=verizon....@python.org> On
Behalf Of Dennis Lee Bieber
Sent: Saturday, January 5, 2019 1:46 PM
To: python-list@python.org
Subject: Re: the python name
On Fri, 4 Jan 2019 22:59:40 -0500, "Avi Gross" <avigr...@verizon.net>
declaimed the following:
>was badly named when it was among the first to do such things. I am
>saying that in retrospect, almost any language can do a basic subset of
>arithmetic operations. And there is nothing in principle that
>necessarily stops any
CF: https://en.wikipedia.org/wiki/Turing_completeness
Pretty much ANY computer language can be used to do any computation -- it
may be more difficult in some, but it won't be impossible. The hypothetical
Turing machine would, in one way, be the ultimate in symbolic manipulation
given the basics consist of test/move/store...
--
Wulfraed Dennis Lee Bieber AF6VN
wlfr...@ix.netcom.com HTTP://wlfraed.home.netcom.com/
--
https://mail.python.org/mailman/listinfo/python-list
--
https://mail.python.org/mailman/listinfo/python-list
