Re: 'Super Turing Machines'


"Richard Hayden" <rah03@xxxxxxxxxxxxxxxxxxx> wrote in message
news:d310dk$ep1$1@xxxxxxxxxxxxxxxxxxxxxxx
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Stephen Harris wrote:
> | "Richard Hayden" <rah03@xxxxxxxxxxxxxxxxxxx> wrote in message
> | news:d2pae7$r4$1@xxxxxxxxxxxxxxxxxxxxxxx
> |
> |>-----BEGIN PGP SIGNED MESSAGE-----
> |>Hash: SHA1
> |>
> |>Hi,
> |>
> |>I read somewhere that a so-called 'Super Turing Machine' which has
> |>infinite alphabet and infinite input alphabet could solve the Halting
> |>Problem for normal Turing Machines.
> |>
> |>Can anyone provide an example of such a 'Super Turing Machine'?
> |>
> |>Thanks,
> |>
> |
> |
> | Both Turing Machines and Super Turing Machines are hypothetical
> constructs.
> | Real PCs are quite finite.
> |
> |
>
> Sorry, I realise that, I meant a theoretical Super Turing Machine which
> could solve the Halting Problem.
>
> Thanks,
>
> Richard Hayden.


Andrew Hodges wrote a published biography of Turing and has a website
devoted to Turing. There is a hierarchy of halting problems and oracles.

Here is a reference: http://www.turing.org.uk/philosophy/lecture1.html
"Turing's 1938 Princeton Ph.D. thesis, work conducted in close cooperation
with Church, was entitled Systems of logic defined by ordinals, and
published as (Turing 1939). Predominantly the work consisted of highly
technical developments within mathematical logic. However the driving force
lay in the question: what is the consequence of supplementing a formal
system with uncomputable deductive steps? In pursuit of this question,
Turing introduced the definition of an 'oracle' which can supply on demand
the answer to the halting problem for every Turing machine. Turing gave his
subject-matter an interpretation which described the mathematician's
'intuition' in theorem-proving, and Newman (1955) effectively identified
the uncomputable 'oracle' with intuition. This was perhaps going too far
since the 'oracle' is capable of far more than any human being; nevertheless
Newman had a unique status as Turing's collaborator at this period and must
reflect the tenor of Turing's discussions. In any case, Turing makes it
clear that the 'intuition' being discussed is related to the human act of
seeing the truth of a formally unprovable Gödel statement. To summarise, it
is notable that Turing's 1938 work focussed on the same issue as Penrose now
raises: the interpretation of uncomputable deductions.
Turing defined the 'oracle' purely mathematically as an uncomputable
function, and said, 'We shall not go any further into the nature of this
oracle apart from saying that it cannot be a machine.' The essential point
of the oracle is that it performs non-mechanical steps. Turing does not
give any physical interpretation, and the word 'brain' is notably absent
from the paper. It is not ahistorical to ask what Turing could have imagined
the human brain was doing in such a moment of 'seeing', since Turing's
youthful writing had shown himself alive to such questions. But we have no
idea how he might have answered in this 1938 period. This question is
naturally of interest to Penrose, who draws attention to Turing's oracle
definition (Penrose 1994, p380ff). But Turing's oracle cannot be identified
with the physical effect Penrose needs for his theory of mind. As Penrose
points out, intuition can again outdo the oracle.

At this point I must digress to describe the recent assertions of the
philosopher B. J. Copeland who has made sensational popular claims about
Turing's 'oracle' definition and its capacity to revolutionise future
computer science. The essential point is that Copeland sees the oracle as
the component of a new kind of machine, more powerful than Turing machines;
and with his colleague D. Proudfoot chides others for not acknowledging such
machines. In their popular article (Copeland and Proudfoot 1999a), a
discussion of 'what Turing imagined' is illustrated by a picture of an
oracle in a black box, which accordng to the authors might work by measuring
the capacitance of an electrical element to any desired number of binary
places."

-----------------------------------------------------------------------------

http://plato.stanford.edu/entries/turing/

Turing emphasised (Turing 1939, p. 173): "We shall not go any further into
the nature of this oracle apart from saying that it cannot be a machine."

"Turing's oracle can be seen simply as a mathematical tool, useful for
exploring the mathematics of the uncomputable. The idea of an oracle allows
the formulation of questions of relative rather than absolute computability.
Thus Turing opened new fields of investigation in mathematical logic."

"On computable numbers, with an application to the Entscheidungsproblem"
Turing's early interesting paper. http://www.abelard.org/turpap2/tp2-ie.asp

--------------------------------------------------------------------------------

SH: This idea of relative computability suggests a chain or hierarchy of
halting problems and Super-Turing machines which can solve that particular
problem.

http://www.math.ucla.edu/~hbe/turing.pdf by Herbert B. Enderton

"Turing's 1939 paper, Systems of logic based on ordinals, is based on
his Ph.D. dissertation, written under the supervision of Alonzo Church
during Turing's two-year stay at Princeton.

Godel's incompleteness theorems had shown that any suciently strong
formal system was incomplete, and in particular could not prove its
own consistency. One can then add to this formal system the sentence
expressing its consistency, thereby obtaining a stronger system. And
this process can be iterated.

The iteration can be transfinite, making use of ordinal notations for
the constructive ordinals. This topic, which was later taken up by
Solomon Feferman in the 1950's, does not directly pertain to
computability theory. But in the process, Turing introduced the
important concept of computability relative to an oracle. He gave the
basic definitions, and indicated how his work on computability could be
adapted to incorporate the idea of calculations that, at any stage,
could utilize a hypothetical fixed body of information. This idea later
led to work on the classification (of problems or of sets or of
functions) according to degree of unsolvability. Moreover, the degrees
of unsolvability are partially ordered, under what is now called
Turing reducibility."

--------------------------------------------------------------------------------

SH: Hava Siegelmann writes a lot about Super-Turing Computability
http://fgc.math.ist.utl.pt/papers/hyper.pdf review of her book

"With analog recurrent neural networks of Hava Siegelmann we have
computation without programmability, i.e., the extra power these
systems display has to do with the decoupling between programming
and computation. Up to Turing power all computations are describable
by suitable programs, that correspond to the prescription by finite
means of some rational parameters of the system or some computable
reals. From Turing power up we have computations that are not
describable by finite means: computation without a program. We
would like to quote Michael Manthey from Aalborg University in
Denmark when he says: <<But how can one even have computation without
an 'algorithm'?! The answer is that classical concept of an algorithm
is a specification of a process that is to take when the algorithm is
unrolled into time. [...] One might compare this to the theory of
evolution based on natural selection: this is a process-level theory,
for which the existence of some a priori algorithm is problematic.>>
When we observe natural phenomena and we endow them with computational
significance, it is not the algorithm we are observing but the process,
the computation. Hypercomputation means computation without a program.
Some objects might be performing hypercomputation around us: we
observe... but we will never be able to simulate their behaviour on a
computer. The use of analog recurrent neural networks for computability
analysis is due to Hava Siegelmann and Eduardo Sontag."

---------------------------------------------------------------------------

http://www.everything2.org/?node_id=1547062

"So to return to the original question, if we had an oracle for the halting
problem or some other undecidable question, would everything then magically
become decidable as well? Well, the short, and somewhat surprising answer is
no. One of the first things we notice is that such O-machines are in many
ways the same as ordinary Turing machines; you can still build a universal
Turing machine with an oracle capable of simulating any other TM with the
same oracle, and hence, you still have description numbers for any such
O-machine. The addition of an oracle did not change the fact that the set of
all of your O-machines remains denumerable, while the class of all formal
languages is non-denumerable, so there must always still exist some set of
languages that your O-machines cannot accept.

Further, it may be shown that some undecidable problems are actually
"harder" than others. If we had such an oracle for the halting problem, then
the set of all O-machines with that oracle has a halting problem of its own.
Even these O-machines cannot solve their own halting problem! And if we had
another oracle for that halting problem, the set of O-machines with both
oracles would still have its own halting problem and so on, producing an
infinite hierarchy of undecidable sets, each set "more undecidable" than the
last. This kind of hierarchy is called the Kleene-Mostowski Arithmetical
Hierarchy."

http://arxiv.org/PS_cache/cs/pdf/0412/0412022.pdf

--------------------------------------------------------------------------

SH: Undecidability can also be expressed in terms of periodic/aperiodic
tiling of the plane. Wang Tiles can be used for this. Penrose tiles can
be expressed as a 24 member set of Wang tiles. Other topics are
finite/infinite precision of calculating with real numbers. Real-world PCs
of course have to approximate.
http://arxiv.org/PS_cache/cs/pdf/0107/0107008.pdf page 17

www.google.com is a good search engine to research this and related topics.
Torkel Franzen, expert poster to sci.logic, has written a book about
inexhaustibility.

Regards, Stephen




.

Relevant Pages

  • Re: Arthur ODwyer on the feasibility of simulating a Turing Machine
    ... I do find this discussion of "the feasibility of simulating a Turing ... I concede that a computer simulation of a Turing Machine may fail ... This gesture doesn't seem to be repeated by other cultures of writing. ...
    (comp.programming)
  • Re: LSP and subtype
    ... Concurrency is not a functional requirement, so Turing machine ... >> mathematics, physics, law, pop-music as computing environments... ... I think abstraction is hugely important. ...
    (comp.object)
  • Re: LSP and subtype
    ... > Thus to solve a non-Turing problem on a Turing Machine, ... some properties of Clock, but that will always be a "computable" part of. ... computability: the application is a compiler to Turing-machine. ... let's consider Clock as a problem space entity. ...
    (comp.object)
  • Re: all the incompleteness proofs are worthless untill...
    ... I suppose I am referring specifically to Turing equivalence, ... computability is not bound by physical constraints. ... cone or the physical universe in some sense as "mathematical objects" ... very pedestrian view on mathematics and logic, ...
    (sci.logic)
  • Re: [PO] Proving a negative is hard
    ... This is just how TMs are defined. ... > Not according to another respondent's direct quote of Turing. ... language given in Davis "Computability and Unsolvability" ... bunch of other independently designed computation models, ...
    (sci.logic)