Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!zaphod.mps.ohio-state.edu!uwm.edu!csd4.csd.uwm.edu!markh
From: markh@csd4.csd.uwm.edu (Mark William Hopkins)
Newsgroups: comp.theory
Subject: The Ulam Machine (was: Re: Paradox of the non-recursive computer)
Message-ID: <12089@uwm.edu>
Date: 12 May 91 18:18:40 GMT
References: <11943@uwm.edu>
Sender: news@uwm.edu
Organization: University of Wisconsin - Milwaukee
Lines: 21

In article <11943@uwm.edu> markh@csd4.csd.uwm.edu (Mark William Hopkins) writes:
>Consider an abstract machine that correctly emulates T0, T1, T2, and so on.
>It exists, according to the Axiom of Choice, but is more powerful than a
>Turing Machine (and thus "non-computeable")
>
>Yet at any point in time it has only "computed" a finite set and can thus be
>emulated by a finite machine.  So is this machine actually computing or not?
>
>My answer is yes.  It's a non-recursive computer.

This machine's construction follows the proof of Goedel's Completeness Theorem
and I believe its existence is EQUIVALENT to Ulam's Conjecture (dealing with
the existence ultrafilters of infinite lattices), which is slightly weaker
than the Axiom of Choice (so I mane it the Ulam Machine, and not the Choice
Machine).

But here's something more to digest, that illustrates how deep the paradox runs:

			  The Ulam Metatheorem:
     Every automata theory capable of representing Finite State Automata
     has a model containing automata more powerful than the Turing Machine.