consider the nonstandard-modell of Peano-arithmetics obtained by the
ultrapower-construction wrt. an ultrafilter-extension of the
Frechet-filter. By Los’ theorem an element t of the ultrapower satisfies
the predicate p(x) iff the set of indices of components of t satisfying
p(x) is in the ultrafilter. Now there is a predicate saying that a
natural number is Goedel-number of a Turing-machine. So can one say that
an element of the ultraproduct with only finitely many elements not
being Goedel-numbers of Turing-machines can be regarded as a "nonstadard
Goedel-number" of a "nonstandard Turing-machine" because of Los’
theorem? Does this make any sense?
02
Sep
"Nonstandard" Turing-Machines?
David McCann <darkwo…@gmx.de> wrote:
> consider the nonstandard-modell of Peano-arithmetics obtained by the
> ultrapower-construction [ ... ]
> [ ... ] So can one say that an element of the ultraproduct
> with only finitely many elements not being Goedel-numbers of
> Turing-machines can be regarded as a "nonstadard Goedel-number"
> of a "nonstandard Turing-machine" because of Los’
> theorem? Does this make any sense?
Sure, there are nonstandard Turing machines in this sense.
What of it ?
If you want to work with nonstandard objects, Turing machines or
otherwise, you can read Edward Nelson’s paper on Internal Set Theory
(Bull. Amer. Math. Soc. 83: 1165-98 (1977)). The 1988 book by Alain
Robert, "Nonstandard Analysis", provides a slower introduction.
–
pa at panix dot com
Pierre Asselin wrote:
> Sure, there are nonstandard Turing machines in this sense.
> What of it ?
I was just asking myself what the properties of such nonstandard Turing
machines would be. For example there are nonstandard natural numbers
being greater than any natural number. I was wondering if these
nonstandard Turing machines also are "greater" than standard Turing
machines in the sense of computability, i.e. if there are nonstandard
Turing machines that can solve problems that cannot be solved by
standard Turing machines.
> If you want to work with nonstandard objects, Turing machines or
> otherwise, you can read Edward Nelson’s paper on Internal Set Theory
> (Bull. Amer. Math. Soc. 83: 1165-98 (1977)). The 1988 book by Alain
> Robert, "Nonstandard Analysis", provides a slower introduction.
Thanks for your help. I will have a look at that paper.
David McCann <darkwo…@gmx.de> wrote:
> Pierre Asselin wrote:
> > Sure, there are nonstandard Turing machines in this sense.
> > What of it ?
> I was just asking myself what the properties of such nonstandard Turing
> machines would be. For example there are nonstandard natural numbers
> being greater than any natural number. I was wondering if these
> nonstandard Turing machines also are "greater" than standard Turing
> machines in the sense of computability, i.e. if there are nonstandard
> Turing machines that can solve problems that cannot be solved by
> standard Turing machines.
Yes, but it’s not as interesting as you might think. For example,
there is a nonstandard Turing machine that solves the standard
halting problem (i.e. whether machine m halts on input n, but only
for standard m and n). It can do that by searching a big table of
all the answers for m+n less than some nonstandard limit L. The
table is (hyper-)finite so this counts as a legitimate machine in
the nonstandard world, but you won’t get any sort of effective
solution of the halting problem out of it.
Still in the nonstandard world, you can ask if any machine can
"solve" the unrestricted halting problem there (m, n possibly
nonstandard). By transfer, the answer can only be "no".
–
pa at panix dot com