Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!swrinde!mips!sdd.hp.com!wuarchive!uunet!mstan!sethb
From: sethb@Morgan.COM (Seth Breidbart)
Newsgroups: comp.theory
Subject: Re: Paradox of the non-recursive computer
Message-ID: <3268@ylum.Morgan.COM>
Date: 9 May 91 23:33:06 GMT
References: <11943@uwm.edu> <3250@ylum.Morgan.COM> <11983@uwm.edu>
Organization: Morgan Stanley, & Co., Inc. / New York City, NY
Lines: 39

In article <11983@uwm.edu> markh@csd4.csd.uwm.edu (Mark William Hopkins) writes:
>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.

True.  So what?  If I can only observe the behavior of a machine, I
can't tell a Universal Turing Machine from a Finite State Automaton in
a finite amount of time.

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

Unless it came with a descriptive label.

>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.

Where is the paradox?

>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.

No, Church's Thesis says that your box is not an effective model of
computation.  Since you can't even build one without using the Axiom
of Choice, I'd tend to agree with Church.

Seth		sethb@fid.morgan.com