Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!uwm.edu!csd4.csd.uwm.edu!markh
From: markh@csd4.csd.uwm.edu (Mark William Hopkins)
Newsgroups: comp.theory
Subject: Re: Paradox of the non-recursive computer
Message-ID: <11983@uwm.edu>
Date: 9 May 91 12:41:52 GMT
References: <11943@uwm.edu> <3250@ylum.Morgan.COM>
Sender: news@uwm.edu
Organization: University of Wisconsin - Milwaukee
Lines: 40

In article <3250@ylum.Morgan.COM> sethb@Morgan.COM (Seth Breidbart) writes:
>In article <11943@uwm.edu> markh@csd4.csd.uwm.edu (Mark William Hopkins) writes:
>However, for any particular Turing Machine, I can eventually show that
>your machine is not the same as that Turing Machine.  I can even give
>you an upper bound on how long it will take.
>
>|Hence a paradox.
>
>Where?

Not for all Turing Machines.  That would take you forever.

Therefore, you can't even tell if you have such a machine RIGHT NOW, if it were
sitting right before your very eyes.

The paradox is that I've just shown that there is no way to distinguish actual
Turing Machines or anything more powerful from an actual finite state machine,
and certainly not by using any logic equivalent in power to a Turing Machine.

Church's Thesis isn't even falsibiable, for I could show you an real live
counter-example sitting right before your very eyes and you wouldn't even
recognize it as one!

Hence, Church's Thesis is meaningless.

Those are places where the paradox leads.

The originally mentioned machine is "computing" in the sense that for any
statement template of the form

			    2 + 2 = ?

it will find a true statement matching the template.  So it answers questions
about arithmetic problems.

Hence, it's a calculator.  You may not see an "algorithm" in it, but you've
just said yourself that it can't have an algorithm as the term is currently
understood and still be more powerful than a Turing machine.  But that's no
problem, I can think of lots of different kinds of computing machines that
don't actually use algorithms to arrive at answers to questions.