Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!iuvax!uxc.cso.uiuc.edu!uxc.cso.uiuc.edu!ux1.cso.uiuc.edu!kolmogorov!ari
From: ari@kolmogorov.physics.uiuc.edu
Newsgroups: comp.ai
Subject: Re: Turing Machines
Message-ID: <11400002@kolmogorov>
Date: 5 Aug 89 03:00:00 GMT
References: <862@ciss.Dayton.NCR.COM>
Lines: 25
Nf-ID: #R:ciss.Dayton.NCR.COM:862:kolmogorov:11400002:000:1260
Nf-From: kolmogorov.physics.uiuc.edu!ari    Aug  4 22:00:00 1989


Turing machines are minimal machines.  It was axiomatized in the simplest
way to determine the properties of computation.  Turing machines are
asymptotically equivalent to any known serial computer.  You wouldn't want to
program or use such a machine, but its simple properties make
it possible to prove certain problems "effectively uncomputable".
If a problem is effectively uncomputable for a Turing machine, it
is also true for most of our modern computers as they currently are.
Some of these ideas have extended to understanding what is provable
and unprovable, and equivalenced to Godel incompleteness Theorem.
There are problems or decision problems which cannot be effectively
computed. This is ultimately connected with the idea that consistent axiomatic
systems are not complete (Cannot prove all true statments).

A good book in this field seems to be "Computability and Unsolvability"
by Martin Davis. (A Dover Text).  It has been a while since I read this
material, and I am not sure how much of it is considered "current" in
AI, but the theorems and ideas in the text are timeless.

ari

Aritomo Shinozaki				ari@kolmogorov.physics.uiuc.edu
Loomis Laboratory of Physics			(217)-244-1744
University of Illinois, Urbana-Champaign
Urbana IL, 61801