on the relations of traditional CS theory to modern programming practice
Mark Tarver
'On the Strange Weakness of Graphical User Programming Languages' -
threads that link up to other essays I've written.
Really I think the problem is that programming has outstripped CS
theory for a long time. We have these theories of computability
dating back to the 1930s developed by people who didn't even have
access to a computer. Elsewhere I noted in 'Lisp for the C21' (L21)
www.lambdassociates.org/lC21.htm
that there is this vaguer but equally important idea of computational
adequacy. When I wrote that piece I didn't see how important it was
to be able to define that concept in a clear and elegant way to get
clear and elegant solutions to modern systems programming problems.
I do now.
The truth is that our formal 1930s theory has long been left behind by
the pace of development of commercial software. Its odd really that
this has not been a focus at university level for longer or that
university CS has not made a bigger issue out of it. I think that part
of the problem is that universities have gone into decline at the same
time that this explosion in innovation has taken place.
http://www.lambdassociates.org/blog/decline.htm
Professors in CS were too busy rushing to think this through and come
up with an organised response. The whole point of universities was to
create an environment where people were free to think unconstrained by
the horizons of deadlines and filling out paper. By commercialising
the universities, putting people under the same pressure to produce
that you would find in a software house, we collapsed their horizons
and introduced the same kind of short-term thinking that characterises
much of the software industry.
The problem now is that we have a generation of computer tools based
on 'lets stick things together and see how it flies' that are at least
good enough for most people to want to stick with and patch as
needed. They are powerful for doing certain things and powerful
enough so that the Right Thing will have a hard time getting
established.
What I think is that this situation will continue for the current
generation of computer tools until later in this century. At that
point our ambitions will exceed the power of our tools to deliver and
we'll probably have to develop those missing theories and take them
seriously. I think in particular the rather sinister PAL demoed in
the thread
http://www.radar.cs.cmu.edu/image.jsp?eid=75
will require planning technology and concise formal models of what I
dimly term computational adequacy. What we have got now will not
deliver PAL.
Of far less importance, but important to me is my own response to this
and L21. I think for me, speaking purely personally and not for
anybody else, this is the end of the road in CS. I stepped out of the
rat race and lived unemployed in order to reacquire the peace of mind
necessary to solve the problems implicit in Qi. In a decent
university system it would not have been necessary to do this, but
what we have in the UK is far from that. Qi is, for me, the Right
Thing. But doing the Right Thing beyond Qi requires a scale of
resource that I simply do not have. It was however a great privilege
to have been on this ride for so long.
Mark
philip....@gmail.com
> The truth is that our formal 1930s theory has long been left behind by
> the pace of development of commercial software. Its odd really that
> this has not been a focus at university level for longer or that
> university CS has not made a bigger issue out of it. I think that part
> of the problem is that universities have gone into decline at the same
> time that this explosion in innovation has taken place.
>
> http://www.lambdassociates.org/blog/decline.htm
One thing I have noticed, especially with cross-posted messages
between c.l.l and c.l.f, is that it tends to provoke "real world vs.
academic" arguments which rather supports your view that nothing will
change.
For example, I find it hard to listen to academics at conferences
telling me how I should be writing software when they've never written
a real program for end users before.
Similarly I find it infuriating listening to industry programmers
telling me how amazing these 'new' anonymous functions are in C#.
Maybe large corporations are not the best placed to be bringing
improved techniques to the attention of the working programmer. But I
don't have a suggestion for an alternative, especially given the bleak
picture you paint of academia in your essays.
--
Phil
http://phil.nullable.eu/
C Y
> Maybe large corporations are not the best placed to be bringing
> improved techniques to the attention of the working programmer. But I
> don't have a suggestion for an alternative, especially given the bleak
> picture you paint of academia in your essays.
Indeed - I too have long been troubled by the increasing trend of
commercialization in higher education, though I have experience only
with the student side of the picture.
In simplest terms, a proper university research system can exist only
when there exist funding sources that are not constrained by practical
results achieved. The constraint must be quality of work performed,
which is a very different metric. You don't want poor researchers,
but you DO want researchers free to pursue directions that have no
apparent hope of return on investment. Only in that fashion can
really NEW directions be found. Knowledge must first be valued in and
of itself, as an end. Oftentimes it becomes a means as well, but at
the university research level that should not be assumed or even
desired. That's what the commercial world is for.
The trend of universities patenting inventions as a source of income
is an example of where things are going off course - that's not the
point of a university. Patents are a monopoly, a short term control
of the use of knowledge, which runs counter to every pure academic
instinct I ever encountered. When you want to LEARN, a patent is
nothing but a roadblock. Indeed, I always thought the freely released
knowledge from universities was a healthy counter to the commercial
behavior (understandable in a commercial setting) of securing
advantage via patents. The erosion of this system is deeply
troubling.
Maybe this is a deeper reflection of where society is headed - with
more and more people on the planet and constant competitive pressure
in a global economy, resource constraints become more severe with
time. In that environment all non-essentials must be trimmed to
survive, with "non-essential" being roughly defined as anything that
does not immediately and profitably support the short term goal.
There are no long term goals - focus is narrowed to survival. Perhaps
this is why the focus of universities is shifting - larger pressures
(i.e. funding sources) are forcing them to assume a form that is
immediately useful or face starvation, as a consequence of the
pressure they themselves are feeling.
Mark Tarver
Not really comp stuff but ....
I think that actually part of the problem came from a certain style of
management that may have originated in the US. This style advocates
quantitative measuring of performance, targets and performance
feedback.
It all sounds very rational but it has been a complete balls up in
every field of public activity that it has been applied to in the UK.
A total shambles.
The analogy I would use is that of placing software probes within a
program to measure functionality and performance. This is sound
practice, however programmers don't generally release programs
containing 1000 probes as an end-user product. Simply in such a case
the program loses umpteen cycles monitoring its own performance. With
enough such probes the program will barely work at all.
Performance monitoring of this obsessive kind cuts into productivity
cycles by forcing people to obsessively monitor themselves and each
other instead of doing the job. The result is that the monitoring
becomes a virus, degrading and destroying what it is supposed to
enhance. In academia, this has led to obsessive form filling. Also
in our police who have to fill out 30 pages of forms per arrest and in
our NHS which despite being pumped to the gills with money is losing
patients to medieval squalor caused by lack of basic hygiene while
doctors fill out forms.
The other aspect is the obsession with measuring or trying to measure
things that cannot really be measured. Measuring academic excellence
by volume of papers warps the behaviour of the system you are trying
to measure. A nice version of the observer effect - that trying to
measure something can change the properties of what you are trying to
observe.
This school of management is really suited only to assembly line
manufacturing and business (perhaps). It should not have been
brought into universities. It is the combination of these methods
with the drive to widen university access on the cheap which has done
the damage.
Mark
Raffael Cavallaro
> Really I think the problem is that programming has outstripped CS
> theory for a long time.
Are you familiar with the work of Peter Wegner and his co-authors along
these lines?
<http://www.cse.uconn.edu/~dqg/papers/cie05.pdf>
<http://www.cse.uconn.edu/~dqg/papers/turing04.pdf>
(especially section 3)
David B. Benson
> Are you familiar with the work of Peter Wegner and ...
Also see
Dina Golden et al. (eds.)
Interactive COmputation: The New Paradigm
Springer, 2006
which begins with an opening address by Robin Milner.
Matthias Blume
<raffaelcavallaro@pas-d'espam-s'il-vous-plait-mac.com> writes:
When reading the above, I think it is useful to keep in mind the
commentary that others in the scientific community have to offer on
this stuff. In particular, see Lance Fortnow's opinion and the ensuing
discussion here:
http://weblog.fortnow.com/2006/07/principles-of-problem-solving-tcs.html
Raffael Cavallaro
> Also see
>
> Dina Golden et al. (eds.)
> Interactive COmputation: The New Paradigm
> Springer, 2006
for
those with deep pockets
Tim X
Hi Mark,
I agree with your assessment of the issues ini Universities re: research,
funding and performance/productivity assessment and am concerned on the
impact this has, particularly with respect to innovation and research into
areas which don't have an obvious commercial application. I also think the
concept of computational adequacy is potentially useful. However, I'm not
as convinced that this is a sign we have out stripped CS theory. If
anything, our failure has been in not focusing enough on developing these
theories or resolving the limitations that have been identified (again,
highlighting problems in the University and research sectors). Most of the
advances in the last 30 years have not been based on improved theoretical
understanding, but rather on increased computational power.
As an example, consider planning. A significant problem in this domain is
the 'frame problem', which was identified and described in the late
60s. Since that time, advances in this area have been largely due to
improved processing speed and cheaper storage/memory. This improvement in
pomputational power has enabled some 'solutions' that were identified in
the 60s and 70s to be applied. Initially, these were impracticle because of
the time/power/storage required. They are now more practicle, but they are
really quite crude work arounds rather than efficient
solutions. Essentially, we have not progressed much of the theory past
where it was at the start of the 70s and have been relying on improvements
in technology to make previously inefficient work arounds
feasible. However, we are now beginning to run up against those same
limitations again as the technological improvements begin to slow down.
In the areas of programming, much of the advances have really been about
hardware allowing higher level programming languages with larger libraries
and a reduction in the need to be as concerned about efficiency. We are
able to handle greater complexity as a result, but essentially, we are
doing the same stuff we were doing 30 years ago - its just more complex and
there is more of it. The advances that have occured have mainly focused on
dealing with the complexities and managing larger code bases i.e. OOP, AOP,
TDD, etc).
The other factor which I think is often overlooked, particularly when your
talking about systems such as PAL, is that fundamentally, it requires some
workable theory of intelligence. I think one of the main reasons for the AI
winter was a combination of Sci-Fi hype combined with a lack of any clear
theory regarding what intelligence really is. Without the underlying
theory, we have nothing to develop the computational theories relating to
reasoning, belief and knowledge representation that are necessary to get
the sort of intelligent systems depicted in that little movie.
A prerequisite to developing these theories is the existence of a research
framework where researchers are free to pursue topics that are free from
practicle/commercial interests and in an environment that actually
facilitates providing the time and resources necessary and isn't
constrained by meeting just commercially focused outcomes or require
constant justification/reporting or endless funding
proposals. unfortunately, current attitudes actually force researchers into
having to put together things like that little film, which make rather
grand promises regarding the benefits in 'hot areas' such as fighting the
evils of terrorism, in order to get funding. Unfortunately, this only works
int he short term. If real commercial advances are not achieved within a
relatively short period, funding is withdrawn and we have yet more
partially completed research and undoubtably only partially completed
theories.
We have not out stripped the traditional CS theory, but we have failed to
develop and extend it or resolve the core limitations identified by these
traditional theories. In the last 30 years, we have focused on the
application and relied on technical improvement to work around theoretical
constraints. What we need is a renewed effort in extending and developing
our theory further.
Tim
--
tcross (at) rapttech dot com dot au
Mark Tarver
vous-plait-mac.com> wrote:
> On 2007-10-15 06:23:48 -0400, Mark Tarver <dr.mtar...@ukonline.co.uk> said:
>
> > Really I think the problem is that programming has outstripped CS
> > theory for a long time.
>
> Are you familiar with the work of Peter Wegner and his co-authors along
> these lines?
>
> <http://www.cse.uconn.edu/~dqg/papers/cie05.pdf>
>
> <http://www.cse.uconn.edu/~dqg/papers/turing04.pdf>
> (especially section 3)
Thankyou - very interesting. Yes, the authors are right that the
Turing machine model is not sufficient for modelling computational
processes. Some of their examples are a bit dodgy and I think that
the main point may have been lost (or buried somewhere). As is usual
the authors spend too long coming to the point.
The main point is this: the conceptual difference between a Turing
machine and a computer is not the TM vs. the computer *but the person
sitting in front of the computer*. This creates a situation where
unpredictable and computation-influencing events can come from an
operator sitting outside the current computation and change the flow
of computation. Such deus ex machina behaviour does not belong to the
closed world of the TM.
Mark
Mark H.
> Really I think the problem is that programming has outstripped CS
> theory for a long time.
Well... that depends on what you call "CS theory." I don't think
it's
fair to lump quantum cryptographers and complexity-theory analysts
into
the same group as people who design programming languages and tools
for
programmers. I've seen talks here at UC Berkeley, for example, about
"CS theory" tools that have found previously undiscovered security
holes
in the Linux kernel.
I get the impression that thinking at a higher level about
programming
language ideas and tools generally gets you further in any kind of
programming work or research. These are the leading-edge people in my
field at least, that reason about code transformations, semantics of
operations, and mapping from vague "design patterns" to _code_
patterns
and faster, more general algorithms.
mfh
George Neuner
>The trend of universities patenting inventions as a source of income
>is an example of where things are going off course - that's not the
>point of a university. Patents are a monopoly, a short term control
>of the use of knowledge, which runs counter to every pure academic
>instinct I ever encountered. When you want to LEARN, a patent is
>nothing but a roadblock.
Actually the whole point of patents is to teach others to make or to
use the invention[*]. Control over commercialization for a time is
the reward for not keeping the invention a secret.
Not defending the use of patents ... as a CS and a professional
software developer, I personally have many issues with the patent
system as it stands. I just correcting what appears to be a
misconception about them.
[*] At least that was the intent. My father is a patent lawyer and I
worked through college as a paralegal writing and evaluating them.
The system has buckled under the crush of filings in the last decade -
the current examination wait is measured in years and examiners can
afford to spend only hours on each patent (not nearly enough time to
properly evaluate it). Plus, many lawyers are practicing IP law
without proper backgrounds. Patent lawyers are theoretically required
to have science or engineering backgrounds (my dad is MSCE + 10 years
in industry before becoming a lawyer), but that requirement made
patent law a narrow specialty with few practitioners. 20 years ago
there were fewer than 2000 patent lawyers in the US, today there are
over 30,000. Over-burdened law firms have pressed liberal arts majors
into practice and the result has been a glut of junk patents and
patents so poorly written (in the technical sense) that one can't
easily learn anything from them.
>Indeed, I always thought the freely released
>knowledge from universities was a healthy counter to the commercial
>behavior (understandable in a commercial setting) of securing
>advantage via patents. The erosion of this system is deeply
>troubling.
Agreed.
George
--
for email reply remove "/" from address
Mark Tarver
There is no current substitute for the universities, and I have no
idea of how to get them back on track after nearly 15 years of going
down the wrong track.
Open Source and Distance Learning seems to me the best bet but suffer
at the moment from lack of effective funding. Many of the grant-
making bodies are still tied into the universities and the money is
not accessible to free lance developers.
This really is wrong because Open Source is producing some of the most
innovative stuff (BitTorrent etc.) whilst the unis are engaged in this
futile brownie point exercise. So maybe instead of continuing to prop
up the universities we should be thinking of how to finance our best
minds which are by no means confined now to the universities.
Mark
Chris F Clark
> Actually the whole point of patents is to teach others to make or to
> use the invention[*]. Control over commercialization for a time is
> the reward for not keeping the invention a secret.
Of course, in the fast-paced world of today, the patent lifetime can
be close to the lifetime of a product, so a patent is a virtual
monopoly. I'm not certain all of the "junk" patents are necessarily
the result of expanding the patent attourney class to include liberal
arts majors.
At my day job we invent stuff and file disclosure forms that hopefully
get turned into patents. However, the patent lawyers rewrite these
into appropriate "patent speak". One of the goals is to use the
appropriate jargon, but a secondary goal is to obfuscate the patent so
that as little about the "real" invention is revealed as possible,
while still protecting the essential ideas as broadly as possible.
Even when rereading patents of devices we have invented, it feels like
we are English peasants trying to decipher high-church Latin. The
words might as well be magical incantations that we simply repeat
wrote for all the knowledge they impart.
Gloria patri, pax vobiscum....
Raffael Cavallaro
> The main point is this: the conceptual difference between a Turing
> machine and a computer is not the TM vs. the computer *but the person
> sitting in front of the computer*. This creates a situation where
> unpredictable and computation-influencing events can come from an
> operator sitting outside the current computation and change the flow
> of computation.
Or, more broadly, interaction with any open ended environment (e.g.,
autonomous robots navigating a real world landscape), hence the title
of their edited volume -- _Interactive Computing: The New Paradigm_
George Neuner
<c...@shell01.TheWorld.com> wrote:
>George Neuner <gneuner2/@/comcast.net> writes:
>
>> Actually the whole point of patents is to teach others to make or to
>> use the invention[*]. Control over commercialization for a time is
>> the reward for not keeping the invention a secret.
>
>Of course, in the fast-paced world of today, the patent lifetime can
>be close to the lifetime of a product, so a patent is a virtual
>monopoly. I'm not certain all of the "junk" patents are necessarily
>the result of expanding the patent attourney class to include liberal
>arts majors.
You are correct. Some of the blame for frivolous "junk" patents falls
on the PTO for procedurally allowing patents in contradiction of law
(many software and "business process" patents fall into this category)
and on examiners who haven't the time to locate and/or sufficiently
evaluate prior art.
However, patent attorneys have a duty to the law as well as to their
clients - they are supposed to recognize junk and not submit it in the
first place. The problem with patent attorneys not having technical
backgrounds is that they have to just accept a client's claim of
originality because they have no basis to evaluate it themselves.
Even with a technical background it can be difficult to evaluate
claims in different areas. Ideally an electro-mechanical patent would
be handled by a lawyer who was an ME or EE and who could consult a
counterpart of the other discipline when necessary. That doesn't
happen in real life. My father is a CE but he handles patents in all
areas: mechanical, electrical, chemical, biological, software,
business, etc. He is always learning new things - which is great, but
it is impossible to be aware of state of the art in all things.
>At my day job we invent stuff and file disclosure forms that hopefully
>get turned into patents. However, the patent lawyers rewrite these
>into appropriate "patent speak". One of the goals is to use the
>appropriate jargon, but a secondary goal is to obfuscate the patent so
>that as little about the "real" invention is revealed as possible,
>while still protecting the essential ideas as broadly as possible.
Which, technically, is illegal. By law, a patent *must* reveal
sufficient detail to allow replication of the invention and full
understanding of its intended use.
I'd be willing to bet that 80% of patents fall short of that ideal.
But things won't improve (and in fact will get worse) until the PTO
expands the corps of examiners by at least an order of magnitude and
gives them enough time to properly evaluate the applications.
>Even when rereading patents of devices we have invented, it feels like
>we are English peasants trying to decipher high-church Latin. The
>words might as well be magical incantations that we simply repeat
>wrote for all the knowledge they impart.
>
>Gloria patri, pax vobiscum....
Quoque vobis.
Ulf Wiger
> On Wed, 17 Oct 2007 10:31:16 -0400, Chris F Clark
> <c...@shell01.TheWorld.com> wrote:
>
>> At my day job we invent stuff and file disclosure forms that hopefully
>> get turned into patents. However, the patent lawyers rewrite these
>> into appropriate "patent speak". One of the goals is to use the
>> appropriate jargon, but a secondary goal is to obfuscate the patent so
>> that as little about the "real" invention is revealed as possible,
>> while still protecting the essential ideas as broadly as possible.
>
> Which, technically, is illegal. By law, a patent *must* reveal
> sufficient detail to allow replication of the invention and full
> understanding of its intended use.
>
> I'd be willing to bet that 80% of patents fall short of that ideal.
> But things won't improve (and in fact will get worse) until the PTO
> expands the corps of examiners by at least an order of magnitude and
> gives them enough time to properly evaluate the applications.
Of course, most of the patents filed today are by large corporations,
and to some extent, it's evolved into a balance of power, where power
is measured in number of patents. With a huge patent portfolio, you
can be reasonably sure that you will have some kind of hold on any
competitor who might threaten to sue. It is not necessarily counter-
productive, from this perspective, if many such patents are vague
enough that the issue would have to be settled in court. Most
companies would think twice before challenging the lawyers of
Microsoft, IBM, Ericsson et al in court.
I've thought much about the idea of "reverse patent search", since
this becomes an obvious prerequisite for releasing source code
(assuming your company is a likely target for IPR attacks). Since
software patents can protect both ideas and specific expressions
of an idea, figuring out whether a non-trivial piece of software
infringes on a patent becomes about as difficult as figuring out
whether any existing novel has either used (and patented) the same
plot ingredients, character descriptions, or dialog as you intend
to use.
The only recourse today is basically to try to file your
own patents, but this would be ineffective, even if it didn't
take years before you knew the results. The process could be
compared to conducting pin-prick testing of your own code, by
trying to imagine what bugs might lurk in there - except that
with testing, the feedback loop usually takes seconds or
minutes to complete. Even so, it is considered a primitive and
ineffective way to find bugs (esp. perhaps among readers of
comp.lang.functional).
Not only would the patent office need to process patent applications
much quicker than today (and with much more domain knowledge). They
should also be able to assist in answering the question: does this
program infringe on any existing (or pending) patents?
If the patent examiners would consider this task impossible, it is
even more so for the poor programmer, who is not versed in patent
speak and cannot be expected to monitor the patent application process
in all parts of the world where her code might be used (my employer
does business in 150 countries). The only reasonable conclusion then
would be that the patent process (at least as regards software) _by
its nature_ stifles the sharing of ideas, rather than encourage it.
<disclaimer>
These thoughts are my own, and do not represent the
opinion of my employer. If I were personally the potential target
of IPR attacks and risked losing millions of dollars, I might have
a different outlook than I do today. As it is, I can affort to be
a bit idealistic. (:
</disclaimer>
BR,
Ulf W
Vesa Karvonen
[...]
> Actually the whole point of patents is to teach others to make or to
> [*] At least that was the intent. [...]
I'm not really interested in debating patents (I consider it waste of
my time), but, the thing is, as a programmer, professional and
otherwise, I've *never* searched a patent database (and have no plans
to do so) or read even a single patent with the intention to learn how
to make or use inventions. Further, I've never met or heard about
anyone (programmer or otherwise) that would have done that or, more
interestingly, would do that regularly. (Yes, such people may exist
and it might be interesting to hear about them.) What I do (besides
figuring things out by myself), and I've seen a few (a small fraction
of programmers) programmers do, is read articles and books to learn
about new inventions.
-Vesa Karvonen
Daniel C. Wang
{stuff deleted}
> I've *never* searched a patent database (and have no plans
> to do so) or read even a single patent with the intention to learn how
> to make or use inventions.
Most corporations specifically advise developers *not* to read patent
databases. Since if the company is found to be in violation of a patent,
and their is evidence developers may have known about the patent and
still infringed can result in treble damages if they lose the suit.
Chris F Clark
> Most corporations specifically advise developers *not* to read patent
> databases.
I've been instructed both to look and not look at patents over my
career (never instructed to do a search, but instructed to look at
specific patents).
In the case, where I was instructed not to look at a patent, I was
working on some software that was a competitor to a specific piece of
software that had parts of it patented. To make sure we were not
infringing, we used a cleanroom approach. We had someone who read the
patent and whose job was specifically to tell me *not* to do certain
things. My job was to do the required tasks without doing any of the
forbidden items.
In the reverse case, we were building some hardware and I was
instructed to look at a software patent to see if it had any useful
ideas that we could build hardware assists for. In that case, the
ideas were interesting but suggested nothing (to me) that I could say
we should build such and such a device to make it work better.
------------------------------------------------------------------------
Bringing this back to the University level, the company I work for
gives out grants to researchers, part of which is to stimulate work in
areas we find interesting. However, mostly what we want are two
things: research that finds novel uses for our products and students
who are trained in the areas that we want who we can hire as interns.
An example that makes this clear is I championed three grants last
winter to interesting researchers. Of those three grants, one
resulted in us finding a very well-qualified intern, one resulted in a
device that the professor patented (and wanted to license to us), and
one has produced no interesting fruits yet. The one which resulted in
us getting an intern will definitely get another grant (and when the
intern graduates, she will get a job offer). The one which resulted
in patented IP will be hard for me to champion again. The one which
produced no fruit, well we are still waiting to decide.
The point of the above is that I think the Universities which are
trying to build up IP portfolio's are not doing themselves the service
they think they are. Sure a few researchers do make significant
strides and create true wealth. However, most researchers don't and
by trying to sell mediocre results to industry, they are alienating
the source of their grants. Producing good work that is unencumbered
is far more interesting to their client community.
Reinforcing what someone else said, while I have never searched a
patent database, I often do literature searches. And, those
literature searches have lead me to contact the various researchers
and collaborate with them.
Matthia...@gmail.com
s'il-vous-plait-mac.com> wrote:
If there is anything wrong with academic publishing, then the Wegner/
Goldin
papers as well as subsequent papers involving other authors such as
Eberbach
are perfect examples as to why. For a thorough
debunking of their claim of having found a computational model that is
more powerful than the Turing Machine, see e.g., the following
rebuttal
by Cockshott and Michaelson to a more recent paper by Wegner and
Eberbach:
@article{1229962,
author = {Paul Cockshott and Greg Michaelson},
title = {Are There New Models of Computation? Reply to Wegner and
Eberbach},
journal = {Comput. J.},
volume = {50},
number = {2},
year = {2007},
issn = {0010-4620},
pages = {232--247},
doi = {http://dx.doi.org/10.1093/comjnl/bxl062},
publisher = {Oxford University Press},
address = {Oxford, UK},
}
You can find it on the Oxford Journals web site:
http://comjnl.oxfordjournals.org/cgi/reprint/50/2/232.pdf
>From their summary:
"In Section 2.5, we enunciated the criteria that we think must be met
for the Church-Turing thesis to be displaced. In general, we require a
demonstration that all terms in C-T systems should have equivalent
terms in the new system but there should be terms in the new system
which do not have equivalents in C-T systems. In particular, the new
system should be able to solve decision problems that are semi-
decidable or undecidable in C-T systems. Finally, we require that a
new system be physically realisable. We think that, under these
criteria, Wegner and Eberbach's claims that interaction machines, the
(pi)-calculus and the $-calculus are super-Turing, are not
substantiated.
...
Wegner and Eberbach make bold claims in their paper. But extraordinary
claims require extraordinary evidence. The work of Turing has served
as a foundation for computability theory for 70 years. To displace it
would have required them to bring forward very strong evidence. We
have discussed the criteria by which such claims could be assessed,
and we have discussed the systems that they have exhibited as
potentially surpassing the TM model of computation. We consider that
in all three cases, interaction machines, the (pi)-calculus and the $-
calculus, we have shown their claims to be invalid."
I couldn't have said it any better (and definitely not more politely).
Kind regards,
Matthias
Pascal Costanza
> Wegner and Eberbach make bold claims in their paper. But extraordinary
> claims require extraordinary evidence. The work of Turing has served
> as a foundation for computability theory for 70 years. To displace it
> would have required them to bring forward very strong evidence. We
> have discussed the criteria by which such claims could be assessed,
> and we have discussed the systems that they have exhibited as
> potentially surpassing the TM model of computation. We consider that
> in all three cases, interaction machines, the (pi)-calculus and the $-
> calculus, we have shown their claims to be invalid."
From http://en.wikipedia.org/wiki/Paul_Feyerabend
'One of the criteria for evaluating scientific theories that Feyerabend
attacks is the consistency criterion. He points out that to insist that
new theories be consistent with old theories gives an unreasonable
advantage to the older theory. He makes the logical point that being
compatible with a defunct older theory does not increase the validity or
truth of a new theory over an alternative covering the same content.
That is, if one had to choose between two theories of equal explanatory
power, to choose the one that is compatible with an older, falsified
theory is to make an aesthetic, rather than a rational choice. The
familiarity of such a theory might also make it more appealing to
scientists, since they will not have to disregard as many cherished
prejudices. Hence, that theory can be said to have "an unfair advantage".'
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
Raffael Cavallaro
> The familiarity of such a theory might also make it more appealing to
> scientists, since they will not have to disregard as many cherished
> prejudices. Hence, that theory can be said to have "an unfair
> advantage".'
"A new scientific truth does not triumph by convincing its opponents
and making them see the light, but rather because its opponents
eventually die, and a new generation grows up that is familiar with
it." -Max Planck
Matthia...@gmail.com
> Matthias.Bl...@gmail.com wrote:
> > Wegner and Eberbach make bold claims in their paper. But extraordinary
> > claims require extraordinary evidence. The work of Turing has served
> > as a foundation for computability theory for 70 years. To displace it
> > would have required them to bring forward very strong evidence. We
> > have discussed the criteria by which such claims could be assessed,
> > and we have discussed the systems that they have exhibited as
> > potentially surpassing the TM model of computation. We consider that
> > in all three cases, interaction machines, the (pi)-calculus and the $-
> > calculus, we have shown their claims to be invalid."
>
> "...That is, if one had to choose between two theories of equal explanatory
> power, to choose the one that is compatible with an older, falsified
Red herring.
We are not dealing with two competing theories here. We don't have an
"older, falsified theory".
The TM is a mathematical construct. It has certain mathematical
properties that are undisputable (and hopefully undisputed). The C-T
hypothesis says that no physically realizable notion of computation
can be more powerful than that defined by the TM. Notice that this is
a HYPOTHESIS, not a "theory" or some such. Nobody claims to have
proved it. We merely have observed that every attempt of defining
another model of physically realizable computations has produced
something of equal or lesser power. (There are plenty of more
powerful but non-realizable models of computation. Just take your
favorite undecidable predicate and throw it in as a primitive.)
Now, Wegner, Goldin, and Eberbach claim they have actually discovered
a more powerful concept of physically realizable computation. This is
a pretty bold claim, but for all we truly know it could be true.
However, to show that it is true, they have to prove it. Doing so
should be fairly straightforward: Just demonstrate a decision
procedure (under the new model) for a predicate that is undecidable
(or merely semi-decidable) for TMs. Then also argue convincingly
that your model actually is--at least in principle--physically
realizable. The problem is -- and that's what Cockshott and
Michaelson explain in quite some detail -- that they haven't done so.
In fact, not only have they not done so, there is also very good
reason to believe that they won't be able to do so for the calculi
they have brought forward so far.
Anyway, your quote by Paul Feyerabend has absolutely nothing to do
with this discussion.
Matthia...@gmail.com
"A new unscientific fallacy does not go away by convincing its
proponets and making them see the light, but rather beceause its
proponents eventually die, and a new generation grows up that has a
good laugh at them." -- Kcnalp Xam
(I wish this were actually true, but unfortunately it isn't. Most
fallacies tend to come back again and again, sometimes almost
unchanged, more often in disguise.)
Tim X
Well said. I agree totally. You have expressed far more succinctly what I
tried to state. We don't actually gain anything from a new formalism that
appears to have better expressive power if the model it defines cannot be
realised. This is the strength of Church-Turing thesis and the Turing
Machine. Possibly the issue isn't that the existing theory has failed, but
rather it is unweildly or lacking in elegance when applied to the more
complex systems that are now possible. While a new theory based on a more
powerful expressive model that makes it easier to represent these more
complex interactions would be welcomed, it has to prove it has at least the
same expressive power and that the model it defines can be realised.
Raffael Cavallaro
> Anyway, your quote by Paul Feyerabend has absolutely nothing to do
> with this discussion.
Goldin and Wegner obviously think it's very relevant since they devote
the first quarter of their chapter of _Interactive Computation_ to the
philosophy of science and epistemology by way of explaining the "strong
resistance," (to use their words) their views have encountered.
To be completely clear, Goldin and Wegner consider the Strong
Church-Turing thesis to be an "older, falsified theory," superseded by
Persistent Turing Machines.
Raffael Cavallaro
> On Oct 18, 6:41 pm, Raffael Cavallaro <raffaelcavallaro@pas-d'espam-
> s'il-vous-plait-mac.com> wrote:
>>
>> "A new scientific truth does not triumph by convincing its opponents
>> and making them see the light, but rather because its opponents
>> eventually die, and a new generation grows up that is familiar with
>> it." -Max Planck
>
> "A new unscientific fallacy does not go away by convincing its
> proponets and making them see the light, but rather beceause its
> proponents eventually die, and a new generation grows up that has a
> good laugh at them." -- Kcnalp Xam
This is the most elaborate version of "I know you are, but what am I?"
I've ever come across.
You can keep your fictional quote, I'll go with Planck, thanks.
Matthia...@gmail.com
s'il-vous-plait-mac.com> wrote:
> On 2007-10-18 21:05:51 -0400, Matthias.Bl...@gmail.com said:
>
> > Anyway, your quote by Paul Feyerabend has absolutely nothing to do
> > with this discussion.
>
> Goldin and Wegner obviously think it's very relevant since they devote
> the first quarter of their chapter of _Interactive Computation_ to the
> philosophy of science and epistemology by way of explaining the "strong
> resistance," (to use their words) their views have encountered.
In other words, they trot out the same Red Herring...
> To be completely clear, Goldin and Wegner consider the Strong
> Church-Turing thesis to be an "older, falsified theory," superseded by
> Persistent Turing Machines.
As I said: The C-T thesis is not a theory at all. It is a conjecture
which could be wrong, but which so far has not been falsified. If
Goldin and Wegner claim it has been falsified, then they will have to
prove that. But so far they have not done so.
Matthia...@gmail.com
s'il-vous-plait-mac.com> wrote:
I'm sorry to hear you didn't appreciate the joke. So I'll say it non-
jokingly:
You are using Planck's quote incorrectly. Just because opponents of a
new claim don't go away does not make that claim a truth. In fact,
when opponents don't go away it is more likely that the reason is not
that these opponents don't want to see the light but that they
actually have seen the light already.
Kind regards,
Matthias
Pascal Costanza
The C-T thesis makes a strong assumption about what computers can and
cannot do for us. But computers can obviously do much more for us that
execute algorithms. For example, a plain Turing machine could never
compute the contents of Wikipedia by using an algorithm (unless it has
the contents of Wikipedia as an input in the first place, but that's
lame). Hence, the C-T thesis is inappropriate as a basis for computer
science.
The problem is not that the C-T thesis may be wrong, the problem is that
the C-T thesis steers us in the wrong direction.
See also http://www.dreamsongs.com/Feyerabend/Feyerabend.html -
especially Sussman's statement at the bottom of that page.
Lauri Alanko
Pascal Costanza <p...@p-cos.net> wrote:
> The C-T thesis makes a strong assumption about what computers can and
> cannot do for us. But computers can obviously do much more for us that
> execute algorithms. For example, a plain Turing machine could never
> compute the contents of Wikipedia by using an algorithm (unless it has
> the contents of Wikipedia as an input in the first place, but that's
> lame).
A bit less than that: http://prize.hutter1.net/
Or alternatively you could give the contents of the observable
universe as an input, which is essentially what humans get. Why do you
claim that a plain Turing machine couldn't generate a Wikipedia from
that?
Lauri
Raffael Cavallaro
> Just because opponents of a
> new claim don't go away does not make that claim a truth.
Clearly. The point of Planck's quote is that if such a claim is true,
we're not likely to know for a generation.
Raffael Cavallaro
> Or alternatively you could give the contents of the observable
> universe as an input, which is essentially what humans get. Why do you
> claim that a plain Turing machine couldn't generate a Wikipedia from
> that?
Because Wikipedia, by its nature, is interactive. What you see is the
result of a constant back and forth among agents - scholars,
advertising spammers, politcal hacks etc. To claim that this could be
precisely forseen in toto by some algorithm with sufficient data is a
claim of complete determinism.
Joachim Durchholz
> "A new scientific truth does not triumph by convincing its opponents and
> making them see the light, but rather because its opponents eventually
> die, and a new generation grows up that is familiar with it." -Max Planck
This is - at best - a description of the life cycle of a fraction of all
theories.
In sciences where falsification is easy (mathematics, physics, CS), old
theories die very fast. The proponents of falsified theories either drop
them really quickly, or they become irrelevant.
In sciences where falsification is difficult (palaeoanthropology, social
sciences, ergonomy of programming), Planck may even have been too
optimistic.
But then that shouldn't come as a surprise: scientific progress is far,
far easier and quicker if you can test the hypotheses with ease.
I think Planck's quote is more out of personal frustration rather than
scientific research on the way the sciences progress.
Regards,
Jo
Joachim Durchholz
> Possibly the issue isn't that the existing theory has failed, but
> rather it is unweildly or lacking in elegance when applied to the more
> complex systems that are now possible.
If you want to express that the Turing Machine is unwieldy: its virtue
is not in elegance but in primitivity. It's the most restricted model of
computation that people have come up with, and its quality isn't that it
is useful for programming, but that all other formalisms devised for
expressing algorithms have been shown to be equivalent to it.
If you want ergonomy, try the lambda calculus. Preferrably in a version
that supports information hiding.
> While a new theory based on a more
> powerful expressive model that makes it easier to represent these more
> complex interactions would be welcomed, it has to prove it has at least the
> same expressive power and that the model it defines can be realised.
"Expressive power" is a part of ergonomy.
That's not the kind of question that Turing Machines were devised to answer.
Oh, and since it's ergonomy, you can't expect a theory that's as nice as
that of computability.
Regards,
Jo
Joachim Durchholz
> For example, a plain Turing machine could never
> compute the contents of Wikipedia by using an algorithm (unless it has
> the contents of Wikipedia as an input in the first place, but that's
> lame).
That's not lame, that's the point exactly.
The algorithm behind Wikipedia is the transformation of wiki markup to
HTML. Plus outputting edit, login and logout dialogs on request.
The contents of Wikipedia was produced by humans, not by a computer
algorithm, so you can't take the contents as an example of what a
computer can but but not a TM-equivalent algorithm.
> Hence, the C-T thesis is inappropriate as a basis for computer
> science.
It is just one of the many bases for CS.
Recursion theory is another.
Boolean logic yet another (and other logics are used as well).
Lambda calculus.
Then various theories about ergonomics for programmers (or
maintainability if you wish): information hiding, modularity, design by
contract, etc.
Finally, theories about ergonomics for end users (conventions about the
placement of Abort buttons etc.)
> The problem is not that the C-T thesis may be wrong, the problem is that
> the C-T thesis steers us in the wrong direction.
For the problems at hand, this is simply a non-issue.
Imagine a situation where the C-T thesis is proven wrong, by providing a
stronger model of computation.
Will that change the discussion about maintenance? About the relative
qualities of Perl, PHP, Python, and Ruby? Or Lisp vs. Haskell vs. C++?
I agree that proving the C-T hypothesis wrong would be very interesting,
but I don't think it would change much. It *might* produce different
computers in a decade or two - *if* the stronger algorithms (a) can
adress new classes of problems that are practically relevant *and* (b)
the new computers needed to run these algorithms can be produced as
cheaply as current-day computers.
In my eyes, quantum computing is nearer to changing the way we're
writing programs. It doesn't go beyond the C-T thesis, but it radically
alters efficiency classes of algorithms.
Regards,
Jo
Pascal Costanza
> Raffael Cavallaro schrieb:
>> "A new scientific truth does not triumph by convincing its opponents
>> and making them see the light, but rather because its opponents
>> eventually die, and a new generation grows up that is familiar with
>> it." -Max Planck
>
> This is - at best - a description of the life cycle of a fraction of all
> theories.
>
> In sciences where falsification is easy (mathematics, physics, CS), old
> theories die very fast. The proponents of falsified theories either drop
> them really quickly, or they become irrelevant.
> In sciences where falsification is difficult (palaeoanthropology, social
> sciences, ergonomy of programming), Planck may even have been too
> optimistic.
In CS, falsification is not easy.
Joshua Taylor
> For example, a plain Turing machine could never
> compute the contents of Wikipedia by using an algorithm (unless it has
> the contents of Wikipedia as an input in the first place, but that's
> lame). Hence, the C-T thesis is inappropriate as a basis for computer
> science.
The point being made is good; no one will ever construct such a
machine. But, while we're discussing the C-T thesis, let's be very
sure that the kind of computation it references is out in the open.
If we were to cut off Wikipedia at any particular point in time (or to
assume that Wikipedia will eventually end), then the states of
Wikipedia form a finite sequence of constant values (alternatively,
the whole sequence is a single constant value). In either case, that
means that the Wikipedia that we see today (and properly terminated
sometime in the future) is Turing computable.
I strongly doubt we'll ever have the machine that could produce
Wikipedia. (And I doubt evenmoreso that that Turing machine could be
all that much smaller than Wikipedia (yes, text compression can do a
lot, but we probably won't have the 'compression' that can read two
articles and enhance a third with insight from the first two).
This disconnect serves to illustrate one issue that some people have
with C-T, namely that we've got no idea of meaningful ways to compute
many provably (effectively) computable functions.
So, while we haven't found any good examples of functions which are
effectively computable that a Turing Machine (or equivalent model)
can't compute, but many of the functions which are computable by
Turing Machine aren't what we might like to think of as computable.
The answer to P == NP, for instance, is computed by exactly one of two
(very small) Turing Machines, one of which always prints "YES", the
other which always prints "NO". We'd probably prefer one which
generated a sensible proof though.
I'm not sure if we mean it in the same way, but this was a very good
summary:
> The problem is not that the C-T thesis may be wrong,
> the problem is that the C-T thesis steers us in the
> wrong direction.
//J
Matthia...@gmail.com
s'il-vous-plait-mac.com> wrote:
> On 2007-10-19 00:43:22 -0400, Matthias.Bl...@gmail.com said:
>
> > Just because opponents of a
> > new claim don't go away does not make that claim a truth.
>
> Clearly. The point of Planck's quote is that if such a claim is true,
> we're not likely to know for a generation.
Actually, no. Planck was clearly exaggerating somewhat, and -- most
importantly -- what he says applies to science but not to math. If
Persistent TMs (or whatever else) falsifies the C-T thesis, then this
fact must have a solid mathematical proof. Once such a proof has been
demonstrated, there won't be any more opposition. The problem here is
that such a proof has not been demonstrated so far. Worse, there can
be no such proof (if we believe that our reasoning is internally
consistent). See below.
A proof would have to demonstrate a decision problem D, show that no
ordinary TM can solve D, and then give a PTM that does solve D (along
with a proof for this, of course). The problem, of course, is that if
such a PTM exists (i.e., one that after a finite amount of steps --
which means after having iterated a finite amount of time and having
seen a finite amount of total input over all iterations), then there
trivially exists an ordinary TM that -- given the same total amount of
(finite) input on its single tape -- gives the same answer. Now,
formalizing this -- which I am not going to do here (I'll leave it as
an exercise to the reader) -- constitutes a proof of PTMs not being
more powerful than ordinary TMs.
Raffael Cavallaro
> That's not lame, that's the point exactly.
> The algorithm behind Wikipedia is the transformation of wiki markup to
> HTML. Plus outputting edit, login and logout dialogs on request.
I think you're missing the point here.
The Strong Church-Turing thesis (SCT) posits that, begining at time T0
and given enough input (including the state of Wikipedia at T0), a TM
could compute the state of Wikipedia at any arbitrary future time Tn
*without further inputs*. Computing the state of Wikipedia at some
arbitrary Tn given the state at Tn itself as input is trivial (we call
it 'copying') - no one doubts that a TM could do this, and it is not
what we're discussing here. That's what Pascal characterized as "lame."
According to Goldin and Wegner (and followers) there exist a class of
computations which cannot be done by a TM no matter what *inital* input
at time T0 it is given. That is, additional input(s) at Tn, Tn+m etc.
are needed to perform the computation, as is *memory* of previous
inputs, outputs and internal computations. They term this model, with
dynamic streams and persistence, a Persistent Turing Machine (PTM).
Pascal and I are saying that starting at T0, the state of Wikipedia at
an arbitrary future Tn is one such computation that can be done by a
PTM (or some other equivalent interactive formalism), but not an
ordinary TM. It is interactive by nature - it requires further inputs
at future times between T0 and Tn (excluding the trivial "lame" case of
having as input the state at Tn itself as discussed above).
Claiming, as the SCT does, that no further inputs are required amounts
to a claim that the future inputs by human contributors are
*completely* predictable given the right algorithm and the right
initial state at T0. This amounts to a claim of complete determinism -
that the right algorithm and initial state could predict anything in
the future universe in complete and accurate detail, including, among
other things, every action of every human Wikipedia contributor.
This determinism is why Goldin and Wegner argue that SCT is incorrect.
They think that the universe is not practially deterministic, that
empirical observation of (i.e., interaction with) the larger
environment is required for certain kinds of computations. They point
to nonlinear systems as evidence of the failure of Determinism -
prediction is only possible in such systems if *precise* initial
conditions are known, and this is a practical impossibility. Others
have argued that QM demonstrates that the Universe is *inherently*
non-deterministic.
Thus they characterize SCT supporters as Rationalists and themselves as
Empiricists, and see this whole argument as just another chapter in the
long standing debate between these two philosophical schools.
Matthia...@gmail.com
> Joachim Durchholz wrote:
> > Raffael Cavallaro schrieb:
> >> "A new scientific truth does not triumph by convincing its opponents
> >> and making them see the light, but rather because its opponents
> >> eventually die, and a new generation grows up that is familiar with
> >> it." -Max Planck
>
> > This is - at best - a description of the life cycle of a fraction of all
> > theories.
>
> > In sciences where falsification is easy (mathematics, physics, CS), old
> > theories die very fast. The proponents of falsified theories either drop
> > them really quickly, or they become irrelevant.
> > In sciences where falsification is difficult (palaeoanthropology, social
> > sciences, ergonomy of programming), Planck may even have been too
> > optimistic.
>
> In CS, falsification is not easy.
You have to be careful. At least in the theoretical part of CS,
falsification is just as easy as it is in pure math (because
theoretical CS is essentially a part of math). If C-T is actually
falsifiable, then the procedure for indisputably doing so is quite
clear. If you actually do it, then there won't be any dispute (at
least not coming from reasonable people). Of course, coming up with
an actual falsification can be very hard, but that's not the point of
Planck's quote, which refers to the situation where you actually have
a new truth while others are unwilling to accept it. In math this
rarely if ever happens.
Matthia...@gmail.com
> Matthias.Bl...@gmail.com wrote:
> > On Oct 18, 10:53 pm, Raffael Cavallaro <raffaelcavallaro@pas-d'espam-
> > s'il-vous-plait-mac.com> wrote:
> >> On 2007-10-18 21:05:51 -0400, Matthias.Bl...@gmail.com said:
>
> >>> Anyway, your quote by Paul Feyerabend has absolutely nothing to do
> >>> with this discussion.
> >> Goldin and Wegner obviously think it's very relevant since they devote
> >> the first quarter of their chapter of _Interactive Computation_ to the
> >> philosophy of science and epistemology by way of explaining the "strong
> >> resistance," (to use their words) their views have encountered.
>
> > In other words, they trot out the same Red Herring...
>
> >> To be completely clear, Goldin and Wegner consider the Strong
> >> Church-Turing thesis to be an "older, falsified theory," superseded by
> >> Persistent Turing Machines.
>
> > As I said: The C-T thesis is not a theory at all. It is a conjecture
> > which could be wrong, but which so far has not been falsified. If
> > Goldin and Wegner claim it has been falsified, then they will have to
> > prove that. But so far they have not done so.
>
> The C-T thesis makes a strong assumption about what computers can and
> cannot do for us. But computers can obviously do much more for us that
> execute algorithms.
Of course. A TM is not meant to be a model of a real computer, it is
a model of computation. Let me give you an example. (Since someone
in Lance Fortnow's blog brought up hairdryers, let me use that same
picture...):
Suppose there is a science of how electricity is transformed into
heat. Suppose the leading abstract model is that of a current flowing
through a resistor. Perhaps there is a conjecture that says that no
other means of electricity->heat transformation is more effective.
Now along comes someone who invented a hairblower. He says: Look, I
found a much more powerful model of electricity->heat transformation.
It is clearly superior, because in addition to producing heat from
electricity it also dries hair. It even has attachments for styling
hair into curls and whatnot. Since the previously leading model does
not handle these, the new model is more expressive and ought to
replace the old, falsified one.
Of course, when you open the hairdryer and look for how it actually
transforms electricity into heat, you'll find an electric current
flowing through an resistor...
> For example, a plain Turing machine could never
> compute the contents of Wikipedia by using an algorithm (unless it has
> the contents of Wikipedia as an input in the first place, but that's
> lame).
Why is that lame? No real computer computes the contents of Wikipedia
either but merely relies on having it part of its input. (Besides, as
someone else has already explained, if you take any snapshot of
Wikipedia, you don't have to have it in your input but can make it
part of your program.)
Since the interactive aspect is just the same as a persistent TM, the
same explanation as the one I just gave in another reply applies.
> Hence, the C-T thesis is inappropriate as a basis for computer
> science.
This is seriously confused. The C-T thesis is not a basis for
computer science at all. The TM is a model of computation which we
often draw upon in CS. There are other models, including more
powerful ones either in terms of what they can compute or in terms of
how efficiently they compute. So far nobody has come up with a model
that can compute more than a TM and also be physically realizable. It
is important to keep in mind that the TM is an abstraction.
> See alsohttp://www.dreamsongs.com/Feyerabend/Feyerabend.html-
> especially Sussman's statement at the bottom of that page.
I agree with many points here but fail to see what it has to do with C-
T.
Matthias
Paul Wallich
> On Oct 19, 2:00 am, Raffael Cavallaro <raffaelcavallaro@pas-d'espam-
> s'il-vous-plait-mac.com> wrote:
>> On 2007-10-19 00:43:22 -0400, Matthias.Bl...@gmail.com said:
>>
>>> Just because opponents of a
>>> new claim don't go away does not make that claim a truth.
>> Clearly. The point of Planck's quote is that if such a claim is true,
>> we're not likely to know for a generation.
>
> Actually, no. Planck was clearly exaggerating somewhat, and -- most
> importantly -- what he says applies to science but not to math. If
> Persistent TMs (or whatever else) falsifies the C-T thesis, then this
> fact must have a solid mathematical proof. Once such a proof has been
> demonstrated, there won't be any more opposition. The problem here is
> that such a proof has not been demonstrated so far. Worse, there can
> be no such proof (if we believe that our reasoning is internally
> consistent). See below.
Unfortunately, proofs themselves are social as well as mathematical
things. You need reputable people to take the time to go through a proof
and agree with it (or find holes that can be plugged). You need the
terminology and symbols specific to a particular proof to be unpacked
for the community at large, and you need the techniques used in the
proof to be accepted.
One of the clearest examples of this kind of process was the time it
took for the proof of the four-color theorem to be fully accepted. That
was essentially as long as it took for the last tenured professors who
didn't believe that computerized enumeration of cases not doable in
reasonable time by humans constituted proof to die or retire.
paul
Paul Wallich
> On 2007-10-19 05:47:16 -0400, Joachim Durchholz <j...@durchholz.org> said:
>
>> That's not lame, that's the point exactly.
>> The algorithm behind Wikipedia is the transformation of wiki markup to
>> HTML. Plus outputting edit, login and logout dialogs on request.
>
> I think you're missing the point here.
>
> The Strong Church-Turing thesis (SCT) posits that, begining at time T0
> and given enough input (including the state of Wikipedia at T0), a TM
> could compute the state of Wikipedia at any arbitrary future time Tn
> *without further inputs*.
No, it really doesn't. That would be true if the state of Wikipedia at
some future point were defined as a computable function of its state at
TO. But no one is making that claim. It's like claiming that the exact
time of decay of the next radium atom in a sample can be computed from
everything known at T0.
paul
Thant Tessman
[...]
> Unfortunately, proofs themselves are social as well as mathematical
> things. [...]
> One of the clearest examples of this kind of process was the time it
> took for the proof of the four-color theorem to be fully accepted. That
> was essentially as long as it took for the last tenured professors who
> didn't believe that computerized enumeration of cases not doable in
> reasonable time by humans constituted proof to die or retire.
Do you honestly believe the fact that there were tenured professors
around who didn't believe computerized enumeration constituted proof
should have had a positive influence on other people's ability to
disprove the four-color theorem by counter example?
-thant
Lauri Alanko
Raffael Cavallaro <raffaelcavallaro@pas-d'espam-s'il-vous-plait-mac.com> wrote:
> Because Wikipedia, by its nature, is interactive. What you see is the
> result of a constant back and forth among agents - scholars,
> advertising spammers, politcal hacks etc. To claim that this could be
> precisely forseen in toto by some algorithm with sufficient data is a
> claim of complete determinism.
That is indeed what the Church-Turing thesis (or at least one variant
of it) entails: all physically realizable computation (which surely
includes all cognitive actions by physical humans) can be also be
computed with a (deterministic) Turing machine. This is a
controversial claim, for sure, but although it hasn't been proven, it
also hasn't been falsified, though Pascal's statement made it sound
like it was obviously false.
Now, if all the interacting agents _are_ computable, then it is in
principle possible to create a single Turing machine that simulates
the interactions of all the agents. And even if humans (or some other
external entities that a computer communicates with) aren't
computable, it merely means that the problem "what does the machine
get as input after producing certain output" is undecidable. We can
still model the situation with a Turing machine that has an oracle for
that problem. Oracles are hardly a new breakthrough, they have been
part of computability theory for ages.
Lauri
Joachim Durchholz
> On 2007-10-19 05:47:16 -0400, Joachim Durchholz <j...@durchholz.org> said:
>
>> That's not lame, that's the point exactly.
>> The algorithm behind Wikipedia is the transformation of wiki markup to
>> HTML. Plus outputting edit, login and logout dialogs on request.
>
> I think you're missing the point here.
>
> The Strong Church-Turing thesis (SCT) posits that, begining at time T0
> and given enough input (including the state of Wikipedia at T0), a TM
> could compute the state of Wikipedia at any arbitrary future time Tn
> *without further inputs*.
Assuming the Wikipedia's future content is defined by an algorithm.
Which it isn't (at least not a known one).
So the question whether Wikipedia's content can be predicted using a
computer program is unrelated to whether the CT hypothesis (*not*
"thesis"...) holds or not: the situation does not fulfil the
preconditions of the thesis.
> Computing the state of Wikipedia at some
> arbitrary Tn given the state at Tn itself as input is trivial (we call
> it 'copying') - no one doubts that a TM could do this, and it is not
> what we're discussing here. That's what Pascal characterized as "lame."
Sure, that algorithm is rather trivial (at least from a CS standpoint).
But it's the only algorithm involved in Wikipedia. There is no algorithm
that will predict Wikipedia's content at T(n+1). (No known algorithm, to
the least. We don't know whether there's an algorithm that describes
physical reality or human thought.)
> According to Goldin and Wegner (and followers) there exist a class of
> computations which cannot be done by a TM no matter what *inital* input
> at time T0 it is given.
I have understood that.
My point is that Wikipedia's future is determined not by an algorithm,
so the CT hypothesis does not apply.
> That is, additional input(s) at Tn, Tn+m etc.
> are needed to perform the computation, as is *memory* of previous
> inputs, outputs and internal computations. They term this model, with
> dynamic streams and persistence, a Persistent Turing Machine (PTM).
If stated that way, PTMs are "more powerful than TMs" only by inclusion
of a external effects (physical reality, human thought) that aren't
well-understood.
Doesn't sound like that's going to produce much in terms of valuable
insights, IMNSHO.
> Claiming, as the SCT does, that no further inputs are required amounts
> to a claim that the future inputs by human contributors are *completely*
> predictable given the right algorithm and the right initial state at T0.
> This amounts to a claim of complete determinism - that the right
> algorithm and initial state could predict anything in the future
> universe in complete and accurate detail, including, among other things,
> every action of every human Wikipedia contributor.
Yes, but the future evolution of the content of Wikipedia isn't a
subject of the CT thesis. There's no algorithm.
So the assumption falls down, and with it the rest.
... OK, I looked up the original claim, as quoted in
http://lambda-the-ultimate.org/node/1038 . It essentially says that "the
CT thesis is generally misrepresented to assume that everything that a
computer does is algorithmic, and that's wrong when external interaction
comes into play".
Well, big deal. That's not shaking the foundations of computer science,
it's picking nits with the way an aspect of it is taught. (It was
*always* understood, at least for me, that all the decidability issues
hold only for the computations *between* the inputs.)
> This determinism is why Goldin and Wegner argue that SCT is incorrect.
I think SCT is either a strawman or just an aberration in the way CS is
taught in the US.
> They think that the universe is not practially deterministic, that
> empirical observation of (i.e., interaction with) the larger environment
> is required for certain kinds of computations. They point to nonlinear
> systems as evidence of the failure of Determinism - prediction is only
> possible in such systems if *precise* initial conditions are known, and
> this is a practical impossibility.
Yes.
> Others have argued that QM
> demonstrates that the Universe is *inherently* non-deterministic.
Agreed. (Assuming quantum interaction is really nondeterministic. I
never learnt enough about QM to really create my own judgement on the
issue.)
> Thus they characterize SCT supporters as Rationalists and themselves as
> Empiricists, and see this whole argument as just another chapter in the
> long standing debate between these two philosophical schools.
Well, I think they're overrating their contribution.
CS isn't about reality, it's about what can and cannot be done using
mechanical devices. For that, CT is enough.
SCT (at least as represented by them) goes over the top.
Regards,
Jo
George Neuner
Many false or badly supported theories have developed a kind of
psuedo-religious orthodoxy that keeps them going in the face of
contradictory evidence.
George
--
for email reply remove "/" from address
Neelakantan Krishnaswami
Paul Wallich <p...@panix.com> wrote:
>
> One of the clearest examples of this kind of process was the time it
> took for the proof of the four-color theorem to be fully
> accepted. That was essentially as long as it took for the last
> tenured professors who didn't believe that computerized enumeration
> of cases not doable in reasonable time by humans constituted proof
> to die or retire.
Actually, I didn't believe the original proof of the four color
theorem, and in fact I still don't believe it. That's because there
were no formal correctness proofs of the programs used to enumerate
the cases. (The programs were actually extremely low level hand-coded
assembly, so verification is essentially hopeless.)
I do, however, believe Gonthier's mechanized proof of it in Coq, since
he did prove the correctness of his enumeration program.
--
Neel R. Krishnaswami
ne...@cs.cmu.edu
Raffael Cavallaro
> A proof would have to demonstrate a decision problem D, show that no
> ordinary TM can solve D, and then give a PTM that does solve D (along
> with a proof for this, of course). The problem, of course, is that if
> such a PTM exists (i.e., one that after a finite amount of steps --
> which means after having iterated a finite amount of time and having
> seen a finite amount of total input over all iterations), then there
> trivially exists an ordinary TM that -- given the same total amount of
> (finite) input on its single tape -- gives the same answer. Now,
> formalizing this -- which I am not going to do here (I'll leave it as
> an exercise to the reader) -- constitutes a proof of PTMs not being
> more powerful than ordinary TMs.
Decision problems miss the whole point since they exlude time. Decision
problems deal only with a single question on infinite inputs, without
regard for the time at which those inputs are available.
The class of computations that a PTM can do and a TM can't are those
that must be computed now, interactively, not after the fact. This is
what Pascal means when he says that the C-T thesis "steers us in the
wrong direction."
If both the TM and PTM both start at the same time, T0, and the PTM
receives inputs after it starts that are not predictable from any
possible input available at time T0, then there is no way when the TM
starts at time T0, short of time travel, to supply the TM with this
"same total amount of (finite) input on its single tape".
If you say that you will simply start the TM at some future time Tn
when such inputs *are* available, I will say that you are not doing the
same computation, because the whole point of this computation is to do
it before Tn.
For example, Driving Home From Work Starting At 3:00pm Today And
Arriving By 3:15 is a computation that must be solved at 3:00 - there's
no point to a "solution" that's specified at 3:15. To provide a
solution after the fact using, for example, a video of the route from
3:00 to 3:15 today is not doing the same computation. A PTM can Drive
Home From Work because it can get additional inputs as it drives. A TM
cannot becuase it cannot have those additional inputs until after the
PTM has already arrived.
If you believe that any possible input after T0 is predictable at time
T0, then you are a Determinist. Goldin and Wegner are not. This is what
they believe is the whole crux of the argument.
Raffael Cavallaro
> That is indeed what the Church-Turing thesis (or at least one variant
> of it) entails: all physically realizable computation (which surely
> includes all cognitive actions by physical humans) can be also be
> computed with a (deterministic) Turing machine. This is a
> controversial claim, for sure, but although it hasn't been proven, it
> also hasn't been falsified, though Pascal's statement made it sound
> like it was obviously false.
That variant is the *Strong* C-T thesis.
C-T = any algorithm for a *mathematical function* can be done by a TM
(or the lambda calculus)
SC-T = *any computation* that any real computer can do can be done by a TM.
The reason that Goldin and Wegner deny the latter is that the SC-T must
hold that everything in the universe (including, as you say "all
cognitive actions by physical humans") is reducible to a mathematical
function. This is Determinism.
Those who deny SC-T believe that there are things that a computer can
compute that are not reducible to a mathematical function. That is,
that there are inherently unpredictable aspects of the universe such
that certain computations that a machine (PTM) with access to later
*interactive* inputs in addition to initial inputs can do, that a
machine that only has access to initial inputs (a TM) cannot. Goldin
and Wegner are saying that there are computations that a PTM can do
interactively that a TM cannot do if constrained to start at the *same
time*.
The issue here is twofold:
1. Ignoring time in saying that the real world is characterizable by a
mathematical function. Indeed anything can be trivially characterized
by a mathematical function if we wait to 'compute' it till after it has
already occurred. The whole point is to specify an algorithm to do the
computation *beforehand*, either with no further inputs (TM) or with a
dynamic stream of inputs and memory (PTM).
2. The Deterministic belief that, given the right initial conditions
and algorithm, the entire course of the universe from the Big Bang on
can be computed.
#1 is just a matter of people misunderstanding each other and talking
at cross purposes. No one denies that a TM could specify the course
taken by an interactive machine *after the fact*. The PTM advocates
simply state that this is not the same computation, since an inherent
part of a computation is *when* it is performed.
#2 is just the long standing argument between Determinists/Rationalists
on the one hand, and Indeterminists/Empiricists on the other. Clearly,
Goldin and Wegner are Empiricists and Indeterminists.
Raffael Cavallaro
> If we were to cut off Wikipedia at any particular point in time (or to
> assume that Wikipedia will eventually end), then the states of
> Wikipedia form a finite sequence of constant values (alternatively,
> the whole sequence is a single constant value). In either case, that
> means that the Wikipedia that we see today (and properly terminated
> sometime in the future) is Turing computable.
Only if we 'compute' it *after the fact*. The whole point of the
interactionists is that there are lots of useful computations that can
be done in real time, before the fact if we allow additional dynamic
input streams, such as, for example, constructing and using Wikipedia
*now*, not having to wait until some hypothetical end point.
Raffael Cavallaro
> That would be true if the state of Wikipedia at some future point were
> defined as a computable function of its state at TO. But no one is
> making that claim. It's like claiming that the exact time of decay of
> the next radium atom in a sample can be computed from everything known
> at T0.
Determinists make precisely this claim. For example, hidden variable theory.
Matthia...@gmail.com
s'il-vous-plait-mac.com> wrote:
> On 2007-10-19 05:47:16 -0400, Joachim Durchholz <j...@durchholz.org> said:
>
> > That's not lame, that's the point exactly.
> > The algorithm behind Wikipedia is the transformation of wiki markup to
> > HTML. Plus outputting edit, login and logout dialogs on request.
>
> I think you're missing the point here.
>
> The Strong Church-Turing thesis (SCT) posits that, begining at time T0
> and given enough input (including the state of Wikipedia at T0), a TM
> could compute the state of Wikipedia at any arbitrary future time Tn
> *without further inputs*. Computing the state of Wikipedia at some
> arbitrary Tn given the state at Tn itself as input is trivial (we call
> it 'copying') - no one doubts that a TM could do this, and it is not
> what we're discussing here. That's what Pascal characterized as "lame."
However, that is precisely what the actualy Wikipedia does: at any
given time Tn it copies the input that it has received until Tn.
There is really no non-trivial computation going on here at all, not
to mention anything that a TM couldn't do.
> Pascal and I are saying that starting at T0, the state of Wikipedia at
> an arbitrary future Tn is one such computation that can be done by a
> PTM (or some other equivalent interactive formalism), but not an
> ordinary TM.
No, it cannot. Either machine needs to see the future input before it
can compute the future output.
> It is interactive by nature - it requires further inputs
> at future times between T0 and Tn (excluding the trivial "lame" case of
> having as input the state at Tn itself as discussed above).
But excluding that "trivial" "lame" case excludes the PTM as well...
> Claiming, as the SCT does, that no further inputs are required amounts
> to a claim that the future inputs by human contributors are
> *completely* predictable given the right algorithm and the right
> initial state at T0.
You are putting up a strawman here. Nobody claims that the future
state of Wikipedia can be predicted by the T0 input alone. No TM and
no PTM can do that. Either machine needs to see the other input as
well before it can give the answer.
You have to remember that the TM is an abstraction. There is no
notion of time, so it does not make sense to speak of "when" the input
is actually given. All that matters is that the input is on a given
input position by the time the read head advances to that position.
You can simulate the behavior of a PTM using a TM by making the
specification more strict: Divide the input into "sections" and
require the output to be partioned into corresponding "sections" with
the additional requirements that by the time (i.e., the step count) at
which output section i is produced the read head must not yet have
ventured into input section j for any j > i. It is as simple as that,
and it actually shows that if anything the PTM can never compute more
than a regular TM since a PTM can be simulated by a TM where an
additional restriction has been imposed.
Matthia...@gmail.com
s'il-vous-plait-mac.com> wrote:
Again, you are missing the whole point of the TM abstraction. A TM
does not have a notion of time. There is no such thing as T0 or
3:00pm etc. The tape itself is also an abstraction. The machine does
not "need" its input to physically exist until it advances its head to
that position. Everything else follows from there. See my other
reply to you for a explanation of how a TM can faithfully simulate a
PTM and therefore model an interactive computation.
Matthias
Raffael Cavallaro
> So far nobody has come up with a model
> that can compute more than a TM and also be physically realizable.
I think that the PTM model does both - if you don't ignore time.
> It
> is important to keep in mind that the TM is an abstraction.
Yes, but it's not a particularly useful abstraction for interactive
computation since it abstracts away time (i.e., it can get its "inputs"
after the fact), and hence, it abstracts away interaction with
non-deterministic inputs, the whole domain we're trying to characterize.
Matthia...@gmail.com
s'il-vous-plait-mac.com> wrote:
Not so. As I have tried to explain, one can code the notion of time
into the problem itself. It does not have to be built into the
machine model.
Lauri Alanko
<Matthia...@gmail.com> wrote:
> You can simulate the behavior of a PTM using a TM by making the
> specification more strict: Divide the input into "sections" and
> require the output to be partioned into corresponding "sections" with
> the additional requirements that by the time (i.e., the step count) at
> which output section i is produced the read head must not yet have
> ventured into input section j for any j > i.
Note that this simulation implies that at any given time, the machine
has only a finite amount of tape available, and hence can only do a
finite amount of work before the next input arrives. So you're not
only simulating interactivity, you're simulating real-timeness! :)
How about just using a multi-tape TM with one tape as a "workspace"
and one tape as "input"? Output could be defined in a number of ways.
Maybe the neatest way (for synchronous communication, anyway) would be
to require that each symbol that has been read from the input tape
must be overwritten exactly once before reading the next symbol. Then
we can envision a circular tape that passes through both the TM and
the mysterious external world, each reading what the other has written
and overwriting it with a response...
Incidentally, since this is comp.lang.functional, we should maybe
rather be discussing how on earth pure mathematical functions could
model interactive computation. The above solution pretty much
corresponds to Miranda's stream-based I/O, one form of which can still
be found in modern Haskell:
interact :: (String -> String) -> IO ()
Of course nowadays we have more convenient ways of defining
interacting processes as lambda-computable (and hence
Turing-computable) functions...
Lauri
Raffael Cavallaro
> How about just using a multi-tape TM with one tape as a "workspace"
> and one tape as "input"? Output could be defined in a number of ways.
This is precisely the specification of a PTM if output is a third tape.
Raffael Cavallaro
> Again, you are missing the whole point of the TM abstraction. A TM
> does not have a notion of time.
Which is precisely why it is a poor model of interactive computation
across time.
The PTM formalism is more expressive of ongoing interactive
computation. That's all.
I don't consider this earth shattering, but I do find the resistance to
it very telling. I think it irks the functional crowd because it makes
explicit the importance of dynamic inputs at run-time rather than
treating all computation as functions from static input to output.
Raffael Cavallaro
> As I have tried to explain, one can code the notion of time
> into the problem itself.
You canot code the notion of time into the problem itself unless you
abstract away time in any meaningful sense. Partitioning inputs into
'sections' is not equivalent to dynamic inputs because all of those
'sections' representing future inputs have to be already on the tape
when the TM starts, whether the transition function has the head read
them yet or not. This amounts to prescience (or time travel) on the
part of the TM's programmer.
Simply put, once a TM starts, nothing but the TM itself can write to
it's tape. This makes it incapable of receiving dynamic inputs.
Note that, as someone else in the thread has suggested, an
oracle-machine could do what a PTM does. Such an oracle machine would
function by taking as input all possible permutations of dynamic
inputs, work tape states, and dynamic outputs of the corresponding PTM.
At each step the oracle simply directs the machine to that portion of
the tape that corresponds to the actual tape states of the
corresponding PTM.
Since such an oracle-machine is just a trivial itemization of every
possible state of the corresponding PTM, the PTM is a much more natural
and expressive (not to mention more parsimonious) formalization of the
corresponding interactive computation.
Again, I don't see a PTM as some sort of revelation, just a better
formalism for interactive computation. Again, I see the resistance to
it as a reaction to the fact that it's advocates are making explicit
the importance of treating dynamic inputs as central to interactive
computation, rather than trying to characterize interactive computation
as computation of functions from static input.
Paul Wallich
First, they're wrong. And second, they don't make that claim at all
unless they claim that the hidden variables can in fact be known. And
the ones I've read (mostly Bohm) tend to avoid that claim like the plague.
It sounds as if this argument is more a social one -- i.e. about what
matters -- than about the underlying facts. Even the most diehard
determinists would likely be willing to agree that you could use less
computing power to compute a system's evolution if you had an oracle
about some set of future states.
paul
Paul Wallich
Huh? At that point the mathematicians were long beyond believing that a
five-color flat map would be found. But there's a big difference between
something being true and something having a proof. Four-color was on the
edge, because given enough time and expendable graduate students you
could in fact check the enumeration during a single career. And the code
was relatively simple. More complex enumerations since then have gone
into the range that you couldn't check even if you had an entire planet
worth of spare graduate students and millennia of time.
Those ones make it a little clearer that you're trusting the people who
do the work to have done it right and reported it ditto.
paul
Raffael Cavallaro
> It sounds as if this argument is more a social one -- i.e. about what matters
Agreed entirely. The Empiricists think that dynamic inputs at runtime
are more important and Rationalists think that computing functions on
static inputs is more important. Which is precisely why advocates of
dynamic languages like me are on the Empiricist side, and advocates of
static compilation, like Matthias, are on the Rationalist side.
Matthia...@gmail.com
s'il-vous-plait-mac.com> wrote:
> On 2007-10-19 17:03:56 -0400, Matthias.Bl...@gmail.com said:
>
> > As I have tried to explain, one can code the notion of time
> > into the problem itself.
>
> You canot code the notion of time into the problem itself unless you
> abstract away time in any meaningful sense. Partitioning inputs into
> 'sections' is not equivalent to dynamic inputs because all of those
> 'sections' representing future inputs have to be already on the tape
> when the TM starts, whether the transition function has the head read
> them yet or not. This amounts to prescience (or time travel) on the
> part of the TM's programmer.
Sigh. Have you tried to understand what I was saying? There is no
"from the beginning" since there is no built-in notion of time. The
tape is an abstraction.
> Simply put, once a TM starts, nothing but the TM itself can write to
> it's tape. This makes it incapable of receiving dynamic inputs.
Again, there is no built-in notion of time. The tape is not a
physical paper tape.
> Again, I don't see a PTM as some sort of revelation, just a better
> formalism for interactive computation.
That may very well be. But the claim was added computational power
(compared with an ordinary TM). That is not so, and that is all I am
arguing. C-T is still safe for now.
> Again, I see the resistance
There is no resistance (from my side) to PTMs, just to the claim that
they have more computational power than ordinary TMs. Yes, they may
be more natural for expressing certain things. But no, these things
are not impossible to encode with ordinary TMs.
Matthia...@gmail.com
Raffael, could you, please, refrain from putting people like myself
into boxes like "Rationalist"? I am certainly not a rationalist in
the sense you describe. Moreover, bringing in dynamic vs. static is
yet another Red Herring. The claim that PTMs have more computational
power than TMs is plainly false in a very strong mathematical sense.
This fact has nothing to do with social issues.
So, before this gets further out of hand, I'll leave this discussion.
Please, use a good introductory book or course on computability theory
for further reference. Thank you.
Matthias
Raffael Cavallaro
> The claim that PTMs have more computational
> power than TMs is plainly false in a very strong mathematical sense.
> This fact has nothing to do with social issues.
And yet computer scientists such as Wegner disagree with you. Obviously
not as "plainly false" as you think it is.
>
> So, before this gets further out of hand, I'll leave this discussion.
> Please, use a good introductory book or course on computability theory
> for further reference. Thank you.
This is merely condescending and I honestly think, beneath you.
Raffael Cavallaro
> Have you tried to understand what I was saying? There is no
> "from the beginning" since there is no built-in notion of time. The
> tape is an abstraction.
Have you tried to understand what I'm saying? Since there is no
built-in notion of time, it is a poor abstraction for computation over
time with dynamic inputs.
Matthia...@gmail.com
s'il-vous-plait-mac.com> wrote:
> On 2007-10-19 21:52:06 -0400, Matthias.Bl...@gmail.com said:
>
> > The claim that PTMs have more computational
> > power than TMs is plainly false in a very strong mathematical sense.
> > This fact has nothing to do with social issues.
>
> And yet computer scientists such as Wegner disagree with you. Obviously
> not as "plainly false" as you think it is.
Yes, it is as plainly false as it gets. I'm frankly shocked that
Wegner disagrees with me (and many others) and that he wastes his time
debunking what he perceives as "myths." We are not in the business of
doing proof by authority here, and I don't have to get intimidated in
my view by the existence of someone who disagrees with me. He has
failed to back his claim with solid proofs, and I'm not the only one
pointing this out.
This is basic stuff, and an introductory course on computability
should cover it. The one I took certainly did. Hence my comment that
you found "condescending."
Goldin and Wegner (and whoever brought out that Planck quote and later
Feyrabend) are the ones who are condescending, because their thinly
veiled argument basically is: "Well, we are geniuses who are ahead --
if not of our time then certainly of YOU. If you disagree with us
then you are an old-timer, or a 'rationalist', or some other kind of
fool who perhaps likes static compilation, so you don't 'get' it.
We'll wait until you're dead, because trying to convince you is
hopeless." Frankly, I found THAT rather offensive.
And, to avoid having to reply to two messages every time, let me
answer your other charge here:
> Have you tried to understand what I'm saying? Since there is no
> built-in notion of time, it is a poor abstraction for computation over
> time with dynamic inputs.
Yes, I have tried to understand what you are saying. I concluded that
you are wrong. Just because time is not built in does not mean that
you cannot encode it. In fact, I have explained one particular way of
encoding it. But let me try one more time:
The TM tape is an abstraction, and its initial contents does not have
to be mapped to the input of a real computer at one particular given
moment of physical time. The only thing a TM relies upon is this:
Once the head has visited a particular square, it will find the value
in that square unchanged when it visits it the next time. However,
there is nothing to stop us from thinking of the first visit to any
given square as producing the initial contents "on demand". Thus, the
fact that the TM abstraction assumes an initial tape that does not
change during the run of the machine (other than those changes made by
the machine itself) can still account for time and interaction --
except the concept of time has to be explicitly coded into the machine
itself since it does not come with the model.
To put it another way: On a real computer, any input that you see in
the future can be thought of has having sat there from the beginning
and merely not having been inspected by the program at an earlier
point in time. The existence or non-existence of a particular input
is completely irrelevant to the program until it tries to actually
inspect it. Therefore, as far as the computing power of the machine
is concerned, nothing changes if you assume all input to exist from
the start. And that's why an ordinary TM is a perfectly fine fit when
modeling the computational power of such a system, be it interactive
or not.
Raffael Cavallaro
> Yes, it is as plainly false as it gets.
I think you misunderstand the word 'plainly.' For something to be
'plainly false' it has to be generally agreed upon that it is false,
and there is no such general agreement.
> On a real computer, any input that you see in
> the future can be thought of has having sat there from the beginning
> and merely not having been inspected by the program at an earlier
> point in time. The existence or non-existence of a particular input
> is completely irrelevant to the program until it tries to actually
> inspect it.
Not if you are required to load this future input *before* the program
starts running. IOW, your 'encoding' of time allows for time travel, so
I'm not buying it.
Matthia...@gmail.com
s'il-vous-plait-mac.com> wrote:
> On 2007-10-19 23:30:27 -0400, Matthias.Bl...@gmail.com said:
>
> > Yes, it is as plainly false as it gets.
>
> I think you misunderstand the word 'plainly.' For something to be
> 'plainly false' it has to be generally agreed upon that it is false,
> and there is no such general agreement.
I don't think that this is the official definition of "plainly", but
so be it. The claim is still false, and provably so. That's all I
meant to say.
> > On a real computer, any input that you see in
> > the future can be thought of has having sat there from the beginning
> > and merely not having been inspected by the program at an earlier
> > point in time. The existence or non-existence of a particular input
> > is completely irrelevant to the program until it tries to actually
> > inspect it.
>
> Not if you are required to load this future input *before* the program
> starts running.
I tried to explain that: The TM is not a real computer, and the tape
is not a real tape that needs to be "loaded" in a physical sense. All
that matters is that the TMs head finds the input in a given square
*when it gets there*. If we label certain squares with time readings,
and if we disallow any machine that visits these labeled squares out
of sequential order(*), then the initial visits to these squares can
be seen as a model of time.
> IOW, your 'encoding' of time allows for time travel, so I'm not buying it.
The encoding does not allow for time travel. See the (*) remark
above. It does not matter that there may exist TMs that violate the
restriction since any PTM can be translated into a TM using the above
encoding in such a way that (*) is satisfied.
If you don't like the (*) restriction, then you can use this
alternative model of time: If the current time is T0 and you visit a
square labeled T1, then the new current time is going to be
MAX(T0,T1). This way it is guaranteed that time never runs backwards.
Lauri Alanko
All right, then, a PTM is a multi-tape TM. As everyone knows, a
multi-tape TM can be simulated with a single-tape TM. Hence PTMs have
no more computational power than any other TMs. Case solved! Nice to
see we could reach agreement!
Lauri
Joachim Durchholz
> On 2007-10-19 16:29:22 -0400, Matthia...@gmail.com said:
>
>> Again, you are missing the whole point of the TM abstraction. A TM
>> does not have a notion of time.
>
> Which is precisely why it is a poor model of interactive computation
> across time.
That's not what a TM is constructed for.
> The PTM formalism is more expressive of ongoing interactive computation.
> That's all.
"More expressive" in what sense?
If it's about being closer to what programmers need: there are even
better formalisms.
If it's about being computationally more powerful in a computational
sense: the PTM is strictly equivalent to the TM, it isn't more powerful.
The additional inputs are just recoded as part of the input on the tape.
(Yes, the results of doing so will be gruesome and unreadable to humans.
However, the TM isn't about having something to express algorithms
easily, it's about easily reasoning about its behaviour, and having a
mapping - however complicated and gruesome - from other formalisms to it.)
> I don't consider this earth shattering, but I do find the resistance to
> it very telling. I think it irks the functional crowd because it makes
> explicit the importance of dynamic inputs at run-time rather than
> treating all computation as functions from static input to output.
You're mistaken.
Dynamic inputs have long been accounted for. Actually there are several
approaches available.
The resistance is more of the "so what?" kind: the claim that PTMs are
more powerful than TMs is simply bogus.
It's also of the "you're working off the wrong assumptions" kind:
AFAICT, the PTM is "more powerful" only if you use a different model of
computational power than the one that the CT thesis is based on. (A
rather cheap shot in my eyes.)
Regards,
Jo
Lauri Alanko
> abstract away time in any meaningful sense. Partitioning inputs into
> 'sections' is not equivalent to dynamic inputs because all of those
> 'sections' representing future inputs have to be already on the tape
> when the TM starts, whether the transition function has the head read
> them yet or not. This amounts to prescience (or time travel) on the
> part of the TM's programmer.
>
> Simply put, once a TM starts, nothing but the TM itself can write to
> it's tape. This makes it incapable of receiving dynamic inputs.
This is _you_ imposing a notion of time on a concept that doesn't
inherently have it.
Again, I suggest considering the more functional example of the same
issue. In Haskell, any interactive command-line application that takes
textual input and produces textual output can be specified with a
function of type String -> String. It takes a list of characters as
input, and produces a list of characters as output.
Now, your objection amounts to saying "That isn't enough for
interactive applications! You have to have the entire input available
before you can produce any output!" And that simply isn't true in
Haskell. It's a strictness condition that _you're_ imposing.
Lauri
Mark Tarver
What you have here on this thread, IMO, are two classical theories of
time meeting in opposition.
The TM is designed to represent a timeless domain of computable
functions. Matthias's solution to the challenge of dynamic
computation is to represent time as another dimension, in a manner
analogous
to Minkowski's space-time in which events are frozen so to speak in an
ice-block - or, as here, recorded on a tape. Now if you represent
things this way then the TM works fine. McTaggart called this B-
series time.
The other great classical model is time as becoming, which is how we
experience time as human observers. Events in the future are not
there in any meaningful sense until they transpire and become actual
by happening. This is Raffael's view. McTaggart called this A-series
time.
The question is which is more appropriate for modelling the computer?
Fascinating that this philosophical duality should emerge here.
Mark
Joachim Durchholz
> Matthias's solution to the challenge of dynamic computation is to
> represent time as another dimension, in a manner analogous to
> Minkowski's space-time in which events are frozen so to speak in an
> ice-block - or, as here, recorded on a tape. Now if you represent
> things this way then the TM works fine. McTaggart called this B-
> series time.
>
> The other great classical model is time as becoming, which is how we
> experience time as human observers. Events in the future are not
> there in any meaningful sense until they transpire and become actual
> by happening. This is Raffael's view. McTaggart called this A-series
> time.
>
> The question is which is more appropriate for modelling the computer?
I think you're misunderstanding Matthias' model.
He isn't using B-series time, he's constructing PTM-equivalent TMs so
that they don't access the cells before they're filled by the external
entities, so the outcome of the TM doesn't depend on whether you have
A-series time or B-series time. (A beautiful construction IMHO.)
Regards,
Jo
Chris F Clark
question. Is it possible to prove that a machine which visits the
tape only in sequential order is as powerful as a machine that can
visit the tape non-sequentially, perhaps by appealing to multi-tape
TMs in the argument?
The reason I ask has to do with the computational power argument. A
PTM with a separate "infinite" tape that it can process between
receiving inputs on the sequential coded tape is effectively a
computational model of Oracle. It can compute the closure of any
infinite series in an "instant" and thus deal with true "real
numbers". Whereas a sequential machine can only compute a finite
series at any instant. My knowledge of math may not be that firm in
those areas, but I seem to recall that the ability to interchange
arbitrary limits suggests something strictly more powerful (in the
same way there are more reals than integers).
This question has real implications if one is contemplating a
Wolfram-style universe of communicating cellular automata. If each
element is restricted to a simple finite calculation, then the result
is simply a TM. If each element can compute an infinite series and
the resulting real number, then isn't the result non-computable?
Asked another way, are there series of computable numbers, such that
the entire series is non-computable? If so, if the tape given to a TM
contains as input a non-computable series, is not the machine which
reads and processes that tape capable of producing results that a TM
with only a tape containing a computable input could not produce?
Again, the reason I ask has to do with the perceived nature of the
universe. From what I've read there seem to be some aspects of the
universe that appear to require infinite series to be calculated
precisely and instantaneously, i.e. if one assumed that a rational
approximation was used, the universe wouldn't behave quite right;
there would be little artifacts appearing as a result of the
approximation being used (and being slightly above or below the
correct value).
Or perhaps these artifacts do appear and are the source of
non-deterministic randomness (the experimental error) in the universe
as we perceive it, and the universe is some machine computing an
infinite series using a function that does not converge strictly from
one side, and thus sometimes makes corrections to lower its currently
computed value and other times makes corrections to raise it, and more
importantly might adjust the individual digits (cells) in a seemingly
unpredicatble fashion. Unpredictable, because our finite
approximation to the real value does not give us knowledge of the
complete series (as it is not finite), but only to the next step (and
the computation of the next step increments "time"). How does one ask
whether such artifacts exist?
My apologies for wandering too far afield. Hopefully, the more
concrete questions near the beginning are coherent, and the ramblings
interjected don't deter their being answered. I guess I need to read
Chaitin's book. I'm just not sure it would clear the soup in my head.
Raffael Cavallaro
> The resistance is more of the "so what?" kind: the claim that PTMs are
> more powerful than TMs is simply bogus.
PTMs are a simple extension to TMs that allow for dynamic inputs during
computation. Very straightforward. The resistance is more of the "I
don't want to acknowledge that an interactive formalism (PTM) is more
appropriate for interactive computing than a batch formalism (TM),"
kind.
Raffael Cavallaro
> As everyone knows, a
> multi-tape TM can be simulated with a single-tape TM.
If one of those tapes represents *dynamic inputs* the the TM can only
simulate the PTM *after* the PTM is done. Having to treat interaction
as a batch computation is the why the TM is less powerful - it can only
do what the PTM does post hoc. This is the whole discussion about time
in the thread with Matthias.
Raffael Cavallaro
> The question is which is more appropriate for modelling the computer?
> Fascinating that this philosophical duality should emerge here.
I think my point here has been that the sequential view of time is more
appropriate for modelling *interactive* computation.
Raffael Cavallaro
> This is _you_ imposing a notion of time on a concept that doesn't
> inherently have it.
It inherently has a notion of temporal *sequence*, before and after.
Input must be available *before* the machine begins execution or there
will be nothing to operate on.
The machine depends for its operation on the consistent temporal
ordering of operations. - it matters at each step whether it writes
first then moves or moves first then writes. If it had no notion of
temporal sequence whatsoever it would not make any difference if at
each step, it either did or did not reverse the order.
The machine must visit the initial state *before* any other.
In short, you can't invoke temporal ordering in the operations of the
machine, and then claim that the machine is immune to notions of
temporal ordering. The idea that one can have inputs from some point in
the sequence which originate *after* the machine starts at the same
time that the machine starts violates the temporal ordering which *is*
necessary for a TM.
Any model that treats all the inputs to a PTM as a single set of inputs
to a TM therefore succeeds only in modeling the PTM computation *after
the fact*.
If you can only model an interactive computation after the fact, it
more or less defeats the whole purpose of having a formalism for
*interactive* computing.
Neelakantan Krishnaswami
Chris F Clark <c...@shell01.TheWorld.com> wrote:
> Although I hate to participate in this thread, I have a simple
> question. Is it possible to prove that a machine which visits the
> tape only in sequential order is as powerful as a machine that can
> visit the tape non-sequentially, perhaps by appealing to multi-tape
> TMs in the argument?
RAM machines are exactly as powerful as Turing machines in terms of
the set of functions they can compute. This is because you can
simulate random access on a tape cell N places away by stepping
forward N steps. Intuitively, this is like simulating an array with a
linked list. However, note that RAM machines can compute some
functions more quickly than TMs can, basically because arrays have
O(1) access to their memory and linked lists are O(n).
> Asked another way, are there series of computable numbers, such that
> the entire series is non-computable?
I don't properly understand what you mean by "entire series". If you
mean "the limit of the series is non-computable", the answer is
certainly yes.
For example, consider the following series of functions. Each function
takes in a program as an argument, and returns true or false, such
that the N-th function in the series will correctly report whether its
argument halts in N steps or less.
Clearly, for any fixed K, you can write a program to test this -- you
can write a program that runs its argument program for K steps, and
report true if it halts in that time and false if not. However, the
limit of this series is not computable, because the limit function is
the solution to the Halting problem.
So you can have chains of computable functions, whose limit is non-
computable. This fact is of considerable importance in denotational
semantics.
--
Neel R. Krishnaswami
ne...@cs.cmu.edu
Marc Gluch
characteristics of computation -- according to Dina Goldin herself
(http://citeseer.ist.psu.edu/cache/papers/cs/17885/http:zSzzSzwww.cs.umb.eduzSz~dqgzSzpaperszSzptm2.pdf/goldin99behavior.pdf)
Thant Tessman
> [...] But there's a big difference between
> something being true and something having a proof. [...]
Of course, but that's not what you said. You said: "Unfortunately,
proofs themselves are social as well as mathematical things."
How much stock you decide to put into someone else's claim that they got
a proof right is a social thing of course, but the proof itself (or lack
thereof) isn't.
"Reality is that which, when you stop believing in it, doesn't go away."
-- Philip K. Dick
-thant
Mark Tarver
OK, I'm skimming a lot of material in this thread because I'm busy so
maybe this is helpful or not.
There are several ways in which you can criticise traditional CS
theory as not supportive of programming practice. One is the actual
distance of these traditional models from the environments in which
programmers actually work.You don't have to be fixated on the idea
that there are machines more powerful than the TM to accept this
position . If we had a convincing model of our actual machines that
was not essentially linked to proprietory hardware or software then we
could sharpen this vague idea of computational adequacy. A good
virtual machine would provide a virtual machine instruction set for
implementing and porting many of our current languages. The WAM for
instance, liberated Prolog from the specifics of the DEC-10 and
provided an industry standard.
This has nothing to do with the power of TMs of course. That is a
seperate story.
Regarding the work of Wegner et al., I've no axes to grind either
way. But a Turing machine, as traditionally conceived, starts off
with a configuration of symbols S and a program P and its final
configuration (if any) is perfectly predictable. If however you allow
symbols to appear on the tape from some outside source during the
computation then the final configuration is not predictable. With
suitable restrictions, you can perhaps say that the final
configuration will fall within some interval but the system as a whole
is radically non-deterministic. This is exactly what happens when you
hook up a computer to some chaotic peripheral like a
human being. I take it that is part of what Raffael is saying.
In other words computers then come to display the sorts of behaviour
characteristic of physical processes and you end up like most
forecasters saying what may happen (light rain in Tunbridge Wells) and
what may not (hurricanes will not happen) rather than what must
happen.
The stronger thesis that therefore there are machines more powerful
than TMs (what does 'more powerful' mean here?) does not follow. The
TM may be quite adequate at processing these events. The point is not
to trash TMs, but rather to study them in a different context from the
classical one. 1930s computer theory was not into embedded systems.
The only way that I can see to try to forestall this is to adopt a B-
series model of time whereby the events are already laid out in a time
line and hence the symbol configuration is already fixed. But this
really doesn't help us much because our experience of time is A-
series.
Mark
Neelakantan Krishnaswami
Thant Tessman <a...@standarddeviance.com> wrote:
> Paul Wallich wrote:
>
>> [...] But there's a big difference between
>> something being true and something having a proof. [...]
>
> Of course, but that's not what you said. You said: "Unfortunately,
> proofs themselves are social as well as mathematical things."
>
> How much stock you decide to put into someone else's claim that they got
> a proof right is a social thing of course, but the proof itself (or lack
> thereof) isn't.
No, he's absolutely correct. Every rule of inference in logic is a
social fact -- it's something that trained people agree is a
truth-conserving argument. This goes all the way down to the simplest
of rules, like the three rules for conjunction:
A true B true (A and B) true (A and B) true
---------------- -------------- --------------
(A and B) true A true B true
And in fact, mathematicians are not in full agreement about what
constitutes a legitimate proof -- for example, constructivists reject
the principle of the excluded middle, and relevant logicians reject
the principle of weakening (ie, that A entails (B implies A)).
So whether an argument is a proof or not is fundamentally a /social/
process, because whether the rules of inference I am using are
justified is judged relative to the community of mathematicians I am
working in.
However, at the same time, it's also the case that properly machine
checked proofs are more credible than solely human-checked proofs. The
reason is that it's easy to write a small proof-checking program,
which many people can easily verify is correct. Then, you can feed it
a proof of arbitrary complexity -- whose correctness very few people
can potentially understand -- and get a result from the checker.
Your confidence in this proof is proportional to your confidence in
the checker, and not in the proof itself. (This, incidentally,
invalidates the central claim of De Millo, Lipton and Perlis's famous
paper "Social Processes and Proofs of Theorems and Programs".)
The original proof of the four-color theorem is an improperly machine
checked proof, because there was no easily-checkable proof that the
program that did the enumeration of cases was correct. Gonthier's
proof, OTOH, does satisfy this criterion, because he gave a machine-
checkable correctness proof for his program that enumerates cases.
Tayssir John Gabbour
> How much stock you decide to put into someone else's claim that they got
> a proof right is a social thing of course, but the proof itself (or lack
> thereof) isn't.
>
> "Reality is that which, when you stop believing in it, doesn't go away."
> -- Philip K. Dick
My understanding is that a proof is an argument which convinces
mathematically-expert peers. What sort of argument is accepted (and by
whom) is a function of social relations.
The best discussion I know of the social nature of mathematical
arguments is in Davis and Hersh's books, like _The Mathematical
Experience_. That book mentions the ebb and flow of what constitutes
an acceptable proof, given social relations among mathematicians. (And
even external political constraints, like the danger people faced when
challenging Euclidean geometry.)
(Though keep in mind I'm not a mathematician.)
Tayssir
Thant Tessman
[...]
> My understanding is that a proof is an argument which convinces
> mathematically-expert peers. What sort of argument is accepted (and by
> whom) is a function of social relations.
If this is all that a proof really was, then proofs would never actually
be *about* anything.
> The best discussion I know of the social nature of mathematical
> arguments is in Davis and Hersh's books, like _The Mathematical
> Experience_. [...]
This is actually sitting on my bookshelf, but I haven't read it yet.
-thant
Raffael Cavallaro
> Raffael Cavallaro wrote:
>> Have you tried to understand what I'm saying? Since there is no
>> built-in notion of time, it is a poor abstraction for computation over
>> time with dynamic inputs.
>>
> PTMs share with TMs the inability to express temporal or non-discrete
> characteristics of computation -- according to Dina Goldin herself
> (http://citeseer.ist.psu.edu/cache/papers/cs/17885/http:zSzzSzwww.cs.umb.eduzSz~dqgzSzpaperszSzptm2.pdf/goldin99behavior.pdf)
From
>
the paper you link above.
"Persistent Turing Machines (PTMs) are multitape machines
with a persistent work tape preserved between successive
interactions; they are a minimal extension of Turing machines (TMs)
that express interactive behavior [GW].
They model services over time provided by
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
embedded, object-oriented, or reactive systems
that cannot be expressed by computable functions [MP, We2, WG]."
I said "computation over time with dynamic inputs." Not seeing any
claim of non-discrete in either.
Matthias Buelow
> The truth is that our formal 1930s theory has long been left behind by
> the pace of development of commercial software.
Sadly...
People with a strong theoretical background (McCarthy, Ken Thompson,
Donald Knuth) have created a lot better software than the
buzzword-infested junk we often see today.
I think if you've broken in your brain on Turing machines or other
minimal abstractions, so to say, you have a different approach at
problem solving than just glueing together illmatched, badly thought out
buzzwordy libraries, which is what most programming is about today.
Tayssir John Gabbour
> Tayssir John Gabbour wrote:
> > My understanding is that a proof is an argument which convinces
> > mathematically-expert peers. What sort of argument is accepted (and by
> > whom) is a function of social relations.
>
> If this is all that a proof really was, then proofs would never actually
> be *about* anything.
The arguments we're advancing are far less rigorous than the ones
mathematicians employ -- yet I think your arguments are intelligible.
(Maybe the jury's still out on mine...)
I'm reminded of Hersh's response to Martin Gardner's (the mathematical
recreations guy) negative review of his book:
Gardner, like all Platonists (realists) insists that math
is real. But it's not physical or mental, so what is it?
Sometimes he thinks it's a real part of the physical world,
which would eliminate most of set theory and higher-dimensional
geometry among many other kinds of non-physical math. Then
he thinks its real because it's a formal logical system,
which would say math was first invented in the late 19th
century--not true! He is oblivious to the inconsistency of
these two stories. And like all Platonists he ignores
the radical difficulty of explaining how a realm of
pure abstraction interacts with the flesh and blood
realm of real mathematical practise.
-- http://cs.nyu.edu/pipermail/fom/1997-November/000128.html
Tayssir
Don Geddis
> The idea that one can have inputs from some point in the sequence which
> originate *after* the machine starts at the same time that the machine
> starts violates the temporal ordering which *is* necessary for a TM.
Why is it necessary? Simply because it was originally defined that way?
Would there be _any_ problem if you simply made the minimal change in the
definition of a Turing Machine, no longer required the input tape to be fully
specified before the TM began executing (although still required that any given
input square be specified before the TM's head attempts to read it)?
This seems a meaningless restriction. Simply dispense with it, and no proof
or theorem about regular Turing Machines changes. Meanwhile, you can now
"suddenly" model interactive computation.
-- Don
_______________________________________________________________________________
Don Geddis http://don.geddis.org/ d...@geddis.org
The only difference between me and a madman is that I am not mad.
-- Salvador Dali
Rob Warnock
| Although I hate to participate in this thread, I have a simple
| question. Is it possible to prove that a machine which visits the
| tape only in sequential order is as powerful as a machine that can
| visit the tape non-sequentially, perhaps by appealing to multi-tape
| TMs in the argument?
I don't think so. In fact, I think I can present a rather trivial
counterexample:
Let M be a multi-tape TM with N internal states and R rules
for which each of T tapes can only be visited in sequential
order [e.g., the forward direction]. Then it is not possible
for M to compute [that is, write onto (one or more of) the
tape(s) being used as the "output device"] a result which is
greater than N*R*T (and the actual limit might be much, much
smaller -- I'm just picking a "safe" value). For example, if
each of the T tapes starts out with a number of 1's representing
unary integers followed by infinite 0's, then it is not possible
for M to compute the product of those numbers if that result
would be greater than N*R*T [or whatever the actual limit is].
Whereas if as few as *one* of tapes is writable and reversable
[can both read & write and step both forwards & backwards],
then a TM with a fixed finite number of states & rules can
compute the product of the numbers on the tapes [or the square
of the number, say, if there's only one tape] no matter *how*
big that product might be!!
-Rob
-----
Rob Warnock <rp...@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Barb Knox
> Asked another way, are there series of computable numbers, such that
> the entire series is non-computable? If so, if the tape given to a TM
> contains as input a non-computable series, is not the machine which
> reads and processes that tape capable of producing results that a TM
> with only a tape containing a computable input could not produce?
One conceptually simple example is that no sequence of all the
computable real numbers is itself computable. That is, the computable
reals are not recursively enumerable. If they were then you could
diagonalise to compute another real that is provably nowhere in the
sequence.
--
---------------------------
| BBB b \ Barbara at LivingHistory stop co stop uk
| B B aa rrr b |
| BBB a a r bbb | Quidquid latine dictum sit,
| B B a a r b b | altum viditur.
| BBB aa a r bbb |
-----------------------------
Matthia...@gmail.com
No, you are misrepresenting the so-called "resistance". My point is
taht TM do not have to correspond to a "batch formalism". With a bit
of encoding they can also be viewed as corresponding to interactive
computing. (Having to encode things is nothing new in the TM world:
almost anything has to be encoded somehow when you show that it
corresponds to a TM.)
Matthia...@gmail.com
Again, you don't have to "treat interaction as a batch computation"
because the TM abstraction does not inherently correspond to batch
computation.
Matthia...@gmail.com
s'il-vous-plait-mac.com> wrote:
> On 2007-10-20 05:27:13 -0400, Mark Tarver <dr.mtar...@ukonline.co.uk> said:
>
> > The question is which is more appropriate for modelling the computer?
> > Fascinating that this philosophical duality should emerge here.
>
> I think my point here has been that the sequential view of time is more
> appropriate for modelling *interactive* computation.
Obviously, a sequential (or at least somehow ordered) view of time is
*necessary* for modelling interactive computations. Fortunately, such
a view of time can be part of the encoding of an algorithm as a TM.
Matthia...@gmail.com
s'il-vous-plait-mac.com> wrote:
> On 2007-10-20 04:49:38 -0400, Lauri Alanko <l...@iki.fi> said:
>
> > This is _you_ imposing a notion of time on a concept that doesn't
> > inherently have it.
>
> It inherently has a notion of temporal *sequence*, before and after.
Sigh. You are still confusing the step count of a TM with physical
time. As I have explained, if you insist in taking a physical view of
the TM tape, then this still does not mean all input has to exist at
step 0. What's on a particular square before the read head first
observes it is irrelevant. Input does not have to physically exist
until the head tries to read it.
> Input must be available *before* the machine begins execution or there
> will be nothing to operate on.
See above.
> The machine depends for its operation on the consistent temporal
> ordering of operations. - it matters at each step whether it writes
> first then moves or moves first then writes. If it had no notion of
> temporal sequence whatsoever it would not make any difference if at
> each step, it either did or did not reverse the order.
Again, the machine only observes one square at a time. There are no
requirements on temporal sequencing of inputs the machine has not yet
observed.
> The machine must visit the initial state *before* any other.
But it only "sees" one square at that time. The other squares are
still unconstrained.
> In short, you can't invoke temporal ordering in the operations of the
> machine, and then claim that the machine is immune to notions of
> temporal ordering.
Indeed, there is *some* notion of temporal ordering -- namely that
after the machine has observed a field's contents one time that
contents must remain consistent wrt. future visits to the same
square. But there are no other temporal ordering constraints.
> The idea that one can have inputs from some point in
> the sequence which originate *after* the machine starts at the same
> time that the machine starts violates the temporal ordering which *is*
> necessary for a TM.
No.
Marc Gluch
I'm not sure that Chris used the phase "a machine which visits the tape
only in sequential order" to mean a machine that can move its head in
one direction only, i.e. to visit/read each cell on the tape only once.
Such machine would have no purpose for the *write* operation. Thus, I
suspect he wanted to compare capabilities of machines with sequential
(left/right) vs. "random" access to their memories (and these two kinds
are Turing-equivalent).