markh@csd4.csd.uwm.edu (Mark William Hopkins) (05/08/91)
You can enumerate all the statements of a formal logic system, A0, A1, A2, ...
Consider a family of sets T0, T1, T2, ..., built on an axiom base T. Each
set is incremented from the previous in the following way:
T(n+1) = T(n) + [An] if statement An is consistent with Tn + axioms T.
T(n+1) = T(n) + [not An] if statement An is inconsistent with Tn + T.
(T(-1) is set to the empty set).
Since each set is a finite set of statements, it's computeable.
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.
And if you answer no, then the next obvious question is this: if you actually
had such a machine before you how would you recognize so, seeing that it only
calculates finite sets at finite times? In other words, how can one ever
possibly hope to falsify the "no" position when it would take an infinite
amount of time to recognize a counter-example as being such?
Hence a paradox.rockwell@socrates.umd.edu (Raul Rockwell) (05/08/91)
Mark William Hopkins:
You can enumerate all the statements of a formal logic system, A0,
A1, A2, ... Consider a family of sets T0, T1, T2, ..., built on an
axiom base T:
T(n+1) = T(n) + [An] if statement An is consistent with Tn + axioms T.
T(n+1) = T(n) + [not An] if statement An is inconsistent with Tn + T.
Since each set is a finite set of statements, it's computeable.
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")
er... while it may exist for formal theories, I don't see how that
makes it more powerful than a TM.
In other words, what's the paradox??
Raul Rockwellsethb@Morgan.COM (Seth Breidbart) (05/09/91)
In article <11943@uwm.edu> markh@csd4.csd.uwm.edu (Mark William Hopkins) writes: |You can enumerate all the statements of a formal logic system, A0, A1, A2, ... |Consider a family of sets T0, T1, T2, ..., built on an axiom base T. Each |set is incremented from the previous in the following way: | | T(n+1) = T(n) + [An] if statement An is consistent with Tn + axioms T. | T(n+1) = T(n) + [not An] if statement An is inconsistent with Tn + T. | |(T(-1) is set to the empty set). Or, T(0) = T |Since each set is a finite set of statements, it's computeable. |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") Well, "exists" may not be the right word. |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? Define "computing". You have a machine that from time to time outputs a statement. Why do you say it is "computing"? |My answer is yes. It's a non-recursive computer. |And if you answer no, then the next obvious question is this: if you actually |had such a machine before you how would you recognize so, seeing that it only |calculates finite sets at finite times? In other words, how can one ever |possibly hope to falsify the "no" position when it would take an infinite |amount of time to recognize a counter-example as being such? Well, if I can observe it for only a finite time (=finite number of state transitions), then I can't tell it isn't a finite state automaton programmed to do exactly what I've observed. Of course, the same holds true for observing any machine. If you can only observe a Turing Machine for a finite amount of time, you can't prove it's not a finite automaton. 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? Seth sethb@fid.morgan.com
markh@csd4.csd.uwm.edu (Mark William Hopkins) (05/09/91)
In article <ROCKWELL.91May8082000@socrates.umd.edu> rockwell@socrates.umd.edu (Raul Rockwell) writes: >er... while it may exist for formal theories, I don't see how that >makes it more powerful than a TM. > >In other words, what's the paradox?? It's a replication of the Goedel's Completeness proof. It "computes" a Complete theory consistent with the axioms of arithmetic (let's say) in the sense that it will arrive at an answer for any proposition in finite time. No Turing Machine has that ability. Yet at all finite times it has only "computed" a finite subset (which IS actually recursively computeable), so that at any given time it is never more powerful than even a Finite State Machine, let alone a Turing Machine.
markh@csd4.csd.uwm.edu (Mark William Hopkins) (05/09/91)
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.
sethb@Morgan.COM (Seth Breidbart) (05/10/91)
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
rockwell@socrates.umd.edu (Raul Rockwell) (05/10/91)
me: er... while it may exist for formal theories, I don't see how that me: makes it more powerful than a TM. me: In other words, what's the paradox?? Mark William Hopkins: > It's a replication of the Goedel's Completeness proof. It "computes" > a Complete theory consistent with the axioms of arithmetic (let's > say) in the sense that it will arrive at an answer for any > proposition in finite time. > No Turing Machine has that ability. No turing machine has the ability to determine if a wf is consistent with a formal theory??? But all you have to have is a good model. For example, if your formal theory is equivalent to predicate calculus then it is a simple matter for a turing machine to determine if a wf is consistent. > Yet at all finite times it has only "computed" a finite subset > (which IS actually recursively computeable), so that at any given > time it is never more powerful than even a Finite State Machine, let > alone a Turing Machine. Well, that's mostly hand waving, but it tends to show that what you are talking about is turing computable. Raul Rockwell