Thursday, November 10, 2011
An objection to proposition 1 of Wittgenstein's 'Tractatus'
From Wittgenstein's 'Tractatus Logico-Philosophicus,' proposition 1:
1. The world is all that is the case.
1.1 The world is the totality of facts, not of things.
1.11 The world is determined by the facts, and by their being ALL the facts.
1.12 For the totality of facts determines what is the case, and also whatever is not the case.
1.13. The facts in logical space are the world.
1.2 The world divides into facts.
1.21 Each item can be the case or not the case while everything else remains the same.
We include proposition 2.0, which includes a key concept:
2.0 What is the case -- a fact -- is the existence of states of affairs [or, atomic propositions].
According to Ray Monk's astute biography, 'Ludwig Wittgenstein, the Duty of Genius' (Free Press division of Macmillan, 1990), Gottlob Frege aggravated Wittgenstein by apparently never getting beyond the first page of 'Tractatus' and quibbling over definitions.
However, it seems to me there is merit in taking exception to the initial assumption, even if perhaps definitions can be clarified (as we know, Wittgenstein later repudiated the theory of pictures that underlay the 'Tractatus'; nevertheless, a great value of 'Tractatus' is the compression of concepts that makes the book a goldmine of topics for discussion).
Before doing that, however, I recast proposition 1 as follows:
1. The world is a theorem.
1.1 The world is the set of all theorems, not of things [a thing requires definition and this definition is either a 'higher' theorem or an axiom]
1.12 The set of all theorems determines what is accepted as true and what is not.
1.13 The set of theorems is the world [redundancy acknowledged]
2. It is a theorem -- a true proposition -- that axioms exist.
This world view, founded in Wittgenstein's extensive mining of Russell's 'Principia' and fascination with Russell's paradox is reflected in the following:
Suppose we have a set of axioms (two will do here). We can build all theorems and anti-theorems from the axioms (though not necessarily solve basic philosophical issues).
With p and q as axioms (atomic propositions that can't be durther divided by connectives and other symbols except for vacuous tautologies and contradictions), we can begin:
1. p, 2. ~p
3. q, 4. ~q
and call these 4 statements Level 0 set of theorems and anti-theorems. If we say 'it is true that p is a theorem' or 'it is true that ~p is an anti-theorem' then we must use a higher order system of numbering. That is, such a statement must be numbered in such a way as to indicate that it is a statement about a statement.
We now can form set Level 1:
5. p & q [theorem]
6. ~p & ~q [anti-theorem]
7. p v q
8. ~p & ~q
9. p v ~q
10. ~p & q
11. ~p v q
12. p & ~q
Level 2 is composed of all possible combinations of p's, q's and connectives, with Level 1 statements combined with Level 2 statements, being a subset of Level 2.
By wise choice of numbering algorithms, we can associate any positive integer with a statement. Also, the truth value of any statement can be ascertained by the truth table method of analyzing such statements. And, it may be possible to find the truth value of statement n by knowing the truth value of sub-statement m, so that reduction to axioms can be avoided in the interest of efficiency.
I have no objection to trying to establish an abstract system using axioms. But the concept of a single system as having a priori existence gives pause.
If I am to agree with Prop 1.0, I must qualify it by insisting on the presence of a human mind, so that 1.0 then means that there is for each mind a corresponding arena of facts. A 'fact' here is a proposition that is assumed true until the mind decides it is false.
I also don't see how we can bypass the notion of 'culture,' which implies a collective set of beliefs and behaviors which acts as an auxiliary memory for each mind that grows within that culture. The interaction of the minds of course yields the evolution of the culture and its collective memory.
Words and word groups are a means of prompting responses from minds (including one's own mind). It seems that most cultures divide words into noun types and verb types. Verbs that cover common occurrences can be noun-ized as in gerunds.
A word may be seen as an auditory association with a specific set of stimuli. When an early man shouted to alert his group to imminent danger, he was at the doorstep of abstraction. When he discovered that use of specific sounds to denote specific threats permitted better responses by the group, he passed through the door of abstraction.
Still, we are assuming that such men had a sense of time and motion about like our own. Beings that perceive without resort to time would not develop language akin to modern speech forms.
In other words, their world would not be our world.
Even beings with a sense of time might differ in their perception of reality. The concept of 'now' is quite difficult to define. However, 'now' does appear to have different meaning in accord with metabolic rate. The smallest meaningful moment of a fly is possibly below the threshold of meaningful human perception. A fly might respond to a motion that is too short for a human to cognize as a motion.
Similarly, another lifeform might have a 'now' considerably longer than ours, with the ultimate 'now' being, theoretically, eternity. Some mystics claim such a time sense.
The word 'deer' (perhaps it is an atomic proposition) does not prove anything about the phenomenon with which it is associated. Deer exist even if a word for a deer doesn't.
Or does it? They exist for us 'because' they have importance for us. That's why we give it a name.
Consider the eskimo who has numerous words for phenomena all of which we English-speakers name 'snow.' We assume that each of these phenomena is an element of a class named 'snow.' But it cannot be assumed that the eskimo perceives these phenomena as types of a single phenomenon. They might be as different as sails and nails as far as he is concerned.
These phenomena are individually named because they are important to him in the sense that his responses to the sets of stimuli that 'signal' a particular phenomenon potentially affect his survival. (We use 'signal' reservedly because the mind knows of the phenomenon only through the sensors [which MIGHT include unconventional sensors, such as spirit detectors].
Suppose a space alien arrived on earth and was able to locomote through trees as if they were gaseous. That being might have very little idea of the concept of tree. Perhaps if it were some sort of scientist, using special detection methods, it might categorize trees by type. Otherwise, a tree would not be part of its world, a self-sevident fact.
What a human is forced to concede is important, at root, is the recurrence of a stimuli set that the memory associates with a pleasure-pain ratio. The brain can add various pleasure-pain ratios as a means of forecasting a probable result.
A stimuli set is normally, but not always, composed of elements closely associated in time. It is when these elements are themselves sets of elements that abstraction occurs.
Much more can be said on the issue of learning. perception and mind but the point I wish to make is that when we come upon logical scenarios, such as syllogisms, we are using a human abstraction or association system that reflects our way of learning and coping with pleasure and pain. The fact that, for example, some pain is not directly physical but is 'worry' does not materially affect my point.
That is, 'reality' is quite subjective, though I have not tried to utterly justify the solipsist point of view. And, if reality is deeply subjective, then the laws of form which seem to describe said reality may well be incomplete.
I suggest this issue is behind the rigid determinism of Einstein, Bohm and Deutsch (though Bohm's 'implicate order' is a subtle and useful concept).
Deutsch, for example, is correct to endorse the idea that reality might be far bigger than ordinarily presumed. Yet, it is his faith that reality must be fully deterministic that indicates that he thinks that 'objective reality' (the source of inputs into his mind) can be matched point for point with the perception system that is the reality he apprehends (subjective reality).
For example, his reality requires that if a photon can go to point A or point B, there must be a reason in some larger scheme whereby the photon MUST go to either A or B, even if we are utterly unable to predict the correct point. But this 'scientific' assumption stems from the pleasure-pain ratio for stimuli sets in furtherance of the organism's probability of survival. That is, determinism is rooted in our perceptual apparatus. Even 'unscientific' thinking is determinist. 'Causes' however are perhaps identified as gods, demons, spells and counter-spells.
Determinism rests in our sense of 'passage of time.'
In the quantum area, we can use a 'Russell's paradox' approach to perhaps justify the Copenhagen interpretation.
Let's use a symmetrical photon interferometer. If a single photon passes through and is left undetected in transit, it reliably exits only in one direction. If, detected in transit, detection results in a change in exit direction in 50 percent of trials. That is, the photon as a wave interferes with itself, exiting in a single direction. But once the wave 'collapses' because of detection, its position is irrevocably fixed and so exits in the direction established at detection point A or detection point B.
Deutsch, a disciple of Hugh Everett who proposed the 'many worlds' theory, argues that the universe splits into two nearly-identical universes when the photon seems to arbitrarily choose A or B, and in fact follows path A in Universe A and path B in Universe B.
Yet, we might use the determinism of conservation to argue for the Copenhagen interpretation. That is, we may consider a light wave to have a minimum quantum of energy, which we call a quantum amount. If two detectors intercept this wave, only one detector can respond because a detector can't be activated by half a quantum unit. Half a quantum unit is effectively nothing. Well, why are the detectors activated probablistically, you say? Shouldn't some force determine the choice?
Here is where the issue of reality enters.
From a classical standpoint, determinism requires ENERGY. Event A at time(0) is linked to event B at time(1) by an expenditure of energy. But the energy needed for 'throwing the switch on the logic gate' is not present.
We might argue that a necessary feature of a logically consistent deterministic world view founded on discrete calculations requires that determinism is also discrete (not continuous) and hence limited and hence non-deterministic at the quantum level.
[The hit counters on all of Paul Conant's pages have been behaving erratically, going up and in numbers with no apparent rhyme or reason.]
[This page first posted January 2002]
Most Hamiltonian circuit families grow polynomially
DraftStatement (i) A method exists for obtaining a set of optimal 'traveling salesman' routes that is a member of a family that grows no faster than 0(In2)2n. (ii) However, even for large n, the method yields a polynomial rate for most sets of fields of nodes.
Remark 1
We operate on a euclidean plane using nodes (cities) that can be specified with cartesian coordinates. We ignore graphs where all points lie on a line.
We adopt the convention that a route begins and ends at an origin city.
Remark 2
We assume that every road linking two cities is straight. This assumption is justified by the fact that a graph composed of curvilinear roads can be deformed into another one that preserves distances -- provided the roads don't cross outside the cities. This proviso is one of the criteria adopted below.
Proof
(i) Our aim is to show that a pretzel circuit can always be replaced by a shorter simple loop (Hamiltonian circuit).
We begin by showing that route backtrackings and crossings are unnecessary.
It is straightforward that if a route covers the same link twice, a shorter route can be drawn.
Suppose a node p is inside a field of nodes and the route enters p from the left, proceeds to x and then backtracks to p exiting toward the right.
x n p mFor non-trivial cases, there must exist some node m to the immediate right of p and some node n to the immediate left. Since mpx is not straight, it is longer than mx. Hence mxpn is shorter than mpxpn.
Similar reasoning holds if p is outside a field.
We show that a route that intersects at a city can be replaced by a shorter route.
Consider any two two-dimensional fields of n nodes and have them intersect at point p.
[F I E L D 1] m n p q r [F I E L D 2]The optimal route for the new field F1 U F2 will not cross at p because of the option mpq linking F1 and F2 and nr linking the fields, with nr < npr; or because of the option npr and mq.
So then no route drawn on a graph need cross at a city.
We now show that a route that intersects outside a city can be replaced by a shorter route.
We have some field of four nodes.
a d b x cThe route acdba crosses at a non-nodal point we call x. Because bxc is not straight, bxc is longer than bc and hence abxcdxa is longer than abcda.
Now we take another four-node field F2 and attach it to the graph above. But we consider only two-point attachments, as we already know that one-point attachments are not optimal. So it is evident that if F2's route does not intersect x, the composite graph's route is shorter than if the alternative holds. An induction proof can be used for any number of fields, of course.
Now suppose we have a ray segment that holds more than two nodes (ignoring origin) adjacent to another ray with at least two.
a b c O f dHow might we link these rays with an un-loop? Suppose cfdba. We will find that more than one link between two adjacent rays is wasteful. The proof is left for the reader.
Also, we know that backtracking is wasteful and so we would not enter the vertical ray at b. In fact our route enters a ray at top or bottom node and leaves at bottom or top. Intermediate nodes can be ignored.
We will not always require that our rays have more than one non-origin node.
(ii)
Our aim is to show a means of obtaining the set of simple loops on any (non-trivial) field of nodes.
We take a field of n nodes and select any node as origin of a set of rays, with each ray drawn through one or more nodes in the field such that all nodes are intersected by rays.
Now our route must begin at origin and link every ray before returning to origin. At origin, we pick any ray to begin and (b = bottom node, t = top node) our path on that ray is determined: 0bt. However, after that there exists a choice. For ray 2 our path may be bt or tb and likewise for subsequent rays. Now if there are 2 nodes per ray, there are n/2 rays and there are about 2n/2 acceptable paths.
Repeating this procedure for every node in the field, it will be seen that we have established the set of all n-gons, regular or irregular, that can be drawn on the field. Since any route that is not an n-gon is not a simple loop, such a route intersects itself at least once, which we know can be replaced by a shorter circuit.
The set of simple loops would then have an upper limit of n(2n/2), though it is evident that n is much too high since changes of reference frame will slide nodes out of ray alignment and there is no reason to expect that an equal number of new alignments will occur.
Now suppose we have a field with all rays intersecting two nodes. If we add a point to that field but place it on a ray, the ray's interior point drops out and there is no significant change.
This tends to show that though a set of 0 2n may occur, it is very unlikely to occur on the next step. But, at this point, we do not rule out the possibility of a set of fields corresponding to an exponential growth rate 0(In2)2m for m < n.
However, in most cases, a field's upper limit of acceptable routes is given by the number of rays per origin times the number of nodes in the field, or n2(n-1), which gives 3n2 - 2n, or 0n2, as the rate of change.
Remark 3
It seems apparent that a computer program needs to identify the nodes that form edges of the regular or irregular polygons associated with each node as origin and then to measure only edge distances. Hence we can expect that, for a random field of n nodes, the program will very likely, but perhaps not certainly, run efficiently.
Remark 4
It may be that, for some families of loops, a hard rate continues from n through infinity; or that a hard rate alternates with an efficient rate over infinity; or that the hard rate always zeroes out. The third statement would prove that NP=P.
Assuming that for most sets of fields P-time computer programs can be derived from our method, it may be that encypherment experts may wish to consider their options.
When algorithms collide: An infinite sum that isn't (or is it?)
Peano, Hilbert and others devised space-filling curves about a century ago, helping to initiate the field of topology. So, from a topological standpoint, the result below is unremarkable.
Yet, philosophically it seems curious that the same structure can yield two different values.
It seems quite reasonable that an area under a curve is ever better approximated by summing areas defined by rectangular strips that fit the area ever more closely. At the limit of width w = 0, the area is defined as the infinite sum of vertical heights f(x) between x=a and x=b. This calculus approximation algorithm is standard.
Yet it is possible to devise an algorithm which seems to yield a sum of y heights that clashes with the area algorithm.
We create a sawtooth path between some curve f(x) and a finite x axis interval by this means: Divide the interval by h, keeping h a positive odd integer. Then trace the path a to f(a) to f(a+1/h) to f(a+2/h) to a+2/h to a+3/h to f(a+3/h) ... to f(a+n/h) to a+n/h = b. The length of this path is always longer than the path connecting the discrete points of f(x). [There are more than two points between f(a) and f(a+1/h) for the sawtooth path but only two points for the other path.]
As h approaches infinity, the number of sawteeth approaches infinity. At the limit of h=infinity, the sawteeth have narrowed to the infinitesimal area f(x), where the route is presumably twice f(x). But the infinite sum of f(x) cannot be infinite if the area is finite (fits inside a finite square). Quite often, the infinite sum (the integral) is less than the continuous arc length for f(x).
So this would seem to indicate that the sawtooth function must be considered undefined at h = infinity.
The special case of the unit square makes this plain:
Use the unit square lying on the positive x axis between origin and x=1. Divide 1 by the odd (for convenience) positive integer h. Trace a sawtooth path from 0,0 to 0,1 to 1/h,1 to 1/h,0 to 2/h,0 to 2/h,1 and so on to 1,0. The sawtooth path length is h+2. As h approaches infinity, the sawtooth path length also nears infinity.
It would seem that at the limit, the 'infinitesimal entity' is twice the height f(x). The sum is the integral of f(x), which, by the fundamental theorem of calculus, is the area quantified as 1.
So that at infinity, if the sawtooth function exists, the sawtooth route length collapses to distance 1.
But would a long-lived or very speedy salesman traveling through all the points of a sawtooth curve find that the sawtooth route is optimal at infinity?
The area is rarely directly proportional to some x interval or radius. For example, take any finite radius circle and define its radius as 1. Then the area is less than the circumference. But take exactly the same circle and define its radius as 3, and now the area is greater than the circumference. Now make a sawtooth path through half of the same circle.
The salesman will find, as h increases, that his path length exceeds the area quantity for every h after some h=k. If the sawtooth algorithm is completable (an 'actual infinity' is agreed), then he would appear to find that the optimal route is the sawtooth route.
But, there is an infinity of areas that can be assigned to the semicircle. For every area quantity there exists a k after which h means that the sawtooth path length is longer.
This observation can be generalized.
So we conclude that the sawtooth function is either unbounded or undefined at h's infinite limit.
If we say it is unbounded, however, we would need to explain why we are forbidden to sum the f(x) heights.
As my son Jim, a Cornell topologist, points out, sawtooth functions are well-known for producing curves with infinite perimeters that contain a finite area, the Koch snowflake being a famous example.
Of course the issue here is not that such functions occur but that the logical conclusion of this particular sawtooth algorithm yields an anomolous result.
Disjoint nondenumerable sets of irrationals
[This page went online Feb. 28, 2002.]
I wish to thank Amherst logician Dan Velleman, author of 'How to Prove It,' for not permitting any slack or insecure arguments. He has not vouched for the final version of this theorem and proof. The theorem itself is nothing special. But the proof is amusing in that it gives an inkling of how vast is the sea of irrationals with respect to the rationals.
Theorem: There exists a denumerable infinite family of sets such that each family member is a nondenumerable set of irrationals that is disjoint from every other member.
Proof:
We establish a monotonically climbing differentiable real function h(x), where x is continuous, and where the first derivative exists and is neither a constant nor a periodic (as in cos(ax)). We use only the integer values h(n) in our proof.
We denote a rational q's infinite decimal digit string by S_0 and its recurring finite substring by s. We see that the first digit of s, which has k digit places, recurs every (nk)th digit place. We denote the initial digit place of s by p. We pair p with d_2, which symbolizes a specific numeral digit. Initially, we are assuming a base 10 system.
We then establish the erase-and-replace function f by locating the h(n)th (p, d_2) and replacing d_2 with d_3.
The altered string, S_x, is forever aperiodic.
Example:
s = (01), k = 2, h = n^2
S_0 = 0.010101010101010101...
S_x = 0.210101210101010121...
We know the set of h functions is infinite and we presume that that set, and hence the set of f functions, is denumerable. So we form the indexed set U f_i.
However, this permits us to form a 'diagonal' function g, such that g is formed by the sequence f_1(1), f_2(2), f_3(3) ... ad infinitum. We then alter the g(n)th (p,d_1) by use of a third digit symbol, writing (p,d_3).
Since g is aperiodic and cannot be indexed, we have established a nondenumerable set of irrationals, which we denote R.
In general, we will write R_a to mean the set R derived from the rational q_a.
Indexing the denumerable set of rationals by j, we question whether R_1 intersection R_2 is nonempty. If empty, we proceed consecutively until we find -- if ever -- R_1 intersection R_j is nonempty.
In that event, we form a new function t_i and require use of (p, d_4) on the subset of R_j strings, denoted R'_j, that are identical to R_1 strings. R_j U R'_j we call T_j (which still holds if R_j U R'_j = R_j). We then proceed to the next instance where R_j intersection R_(j+n) is nonempty. Again, we insert digit d_5, obtaining T_(j+n).
Obviously, with a base 10 system, this procedure can be repeated 9 times.
As the number of digit places in s is irrelevant, we can increase our set of available digits with a higher base number system. In that case, we apply induction: If a base m system yields m-1 replacement digits, then a base m+1 system, yields m replacement digits.
With m e M = N, and N denumerable, we find that the family U( T_j) exists, where J = N, requiring that U( T) is denumerable and that for all j e J, n e N(T_j is disjoint from T_(j+n).
Proof concluded.
Remark: It is curious that the set of writable functions is considered denumerable because each expression is composed of a finite string of symbols. For example, 2 + log x, contains 9 symbols, including spaces. Hence, each such expression can be counted, and the entire set of such expressions must also be countable. Since our diagonal function is writable as g(n) = f_n(n), we have shown a nondenumerable subset of writable functions.
A geometric note on Russell's paradox
Here we regard the null set as the initial set and build sets from there, as in:
Step 0: { }
Step 1: { { { } },{ } }
Using an axiom of infinity, we can continue this process indefinitely, leading directly to a procedure for building an abstraction of all countable sets; indirectly, noncountable sets can also be justified.
In Russell's conundrum, some sets are elements of themselves.
So let us regard a plane as pre-existent (null space or some such) and regard Set sub 0, the empty set, as a circle surrounding nothing. Set sub 1 we picture as a concentric circle around set 0. Now those two circles express the element represented as {{ }}.
We might also say the two circles express the set that contains the element { }.
In that case, we may wish to say that the set {{ }} = the element {{ }}.
Suppose we establish two construction algorithms for sets of concentric circles. In algorithm A, the outer circle is a solid line, so that the null space container is not construed to be part of the set. In algorithm B, the outer circle is a dashed line, so that the null space container is construed to be part of the set.
At each step we add a new enclosing circle and require that it be either solid or dashed.
So as step n is taken to infinity, we find that the null space container vanishes. That is, the circles fill the plane.
In that case, the container is non-existent or undefined, so that the rule that requires that it be either part of the set or not part of the set is not applicable.
We have assumed that the initial circle surrounds something that is not an element -- as with { }. But we really must give a rule that says the inmost area is not an element. We could have a rule that permits not only the outmost but the inmost circle to be dashed. In that case the inner void would be considered a part (element) of the set. Though the void in a null set is, for sound reasons, not permitted to be construed as an element, it is still useful to see the relationship of admitting the inner void to Russell's paradox.
Russell's paradox is usually disposed of by resort to an axiom prohibiting a set from being an element of itself. But we can see that sets and elements can be identical except for the rule prohibiting a set belonging to itself.
For example, element {{ }} in a set-building algorithm X is identical to the set containing the element { } in set-building algorithm Y.
It seems that the axiom while necessary remains questionable from the standpoint of logical consistency.
First published ca. 2000
An algorithm to imply the set of reals
An algorithm to imply the set of reals
We present an algorithm for "constructing" the entire set of reals and find that our intuition suggests that no diagonal can exist, which accords with Cantor's proof.
Cantor's diagonalization proof says that if it were possible that all reals were listed, then one could create an anti-diagonal number from the diagonal that intersects all the listed numbers. Hence, no such diagonal exists and the set of reals is not 1-to-1 with the set of naturals.
However, we are assuming that there is a set N containing all naturals. We are also assuming that because a finite n x n square always has a (non-Pythagorean diagonal of n cells) that intersects every row, then the same holds for the tiled quarter-plane.
However, the infinity axiom says that N exists, in which case we may say that the set of X axis integers is 1-to-1 with the set of Y axis integers, and further that the cellular diagonal with a cell vertex at (0,0) has cardN and intersects every horizontal string of cells bounded by y and y+1. In that case, we may use Cantor's argument to say that the reals can't be mapped 1-to-1 onto this tiling.
Interestingly, our algorithm for constructing all the reals intuitively says that such a set has no diagonal. But, that intuition is simply an intuition until we apply Cantor's proof and the infinity axiom.
We write an algorithm for determining the set of reals, thus:
We have the set of 1x1 square cells in a quadrant of the Cartesian grid. Each square is eligible to contain a digit. We consider only the horizontal strings of cells.
Suppose we use a base 2 system. We begin at step 0 using 2 consecutive spaces and obtaining 4 possible combinations, to wit: 00, 11, 10, 01. For step 1 (3 spaces), the number of combinations is 2*4 and for step n the number of combinations is 2n+2.
At limn->inf. 2n+2, we have established all base 2 infinite digit strings, expressing the entire set of reals greater than an arbitrary j e Z and less than or equal to j+1.
Remark: Our algorithm does not compute reals sequentially. It only computes 'pre-reals,' since a real is defined here as an infinite digit string. No element "materializes" prior to the entire set's establishment at (denumerable) infinity.
The algorithm above requires that for any step n, the set of digit strings is a rectangle n2n+2.
But limn->inf. n/2n = 0, meaning the rectangle elongates and narrows toward a limiting form of a half-line.
For an integer diagonal to include an element of all horizontal digit strings, we must have a square of n columns and n rows. But such a square of the reals is never attainable. It would then seem safe to say that the set of reals, expressed as infinite digit strings, has no diagonal, which is equivalent to saying the set of reals is non-denumerable.
However, our intuition that the set of reals so constructed should have no diagonal is provable by agreement to the infinity axiom, which permits the cardN diagonal, and by Cantor's anti-diagonal result.
It also follows that no exponentially defined set of tiles n x kn has a cellular diagonal at the tiling algorithm's infinite limit.
On the other hand, a tiling defined by nk can be said to have k cellular diagonals, such that collectively the k diagonals intersect every horizontal cellular string. It then can be shown that such a tiling is one-to-one with N.
Interestingly, the power set of any n e N has card2n, which corresponds to step n of our algorithm, in which we have a set of 2n+2 pre-reals.
Additional remark:
Lemma: Any set with limn->inf kn elements has the cardinality of the reals, with k =/= 0, -1, 1 and k e Z.
Proof:
The set of reals is 1-to-1 with a set that has limn->inf 2n elements. Hence the cardinality of each set is identical. Similarly, the algorithm above can be rewritten as ckn, with c a nonzero integer constant, meaning that all real digit strings are established at limn->inf ckn.
Theorem: Some non-enumerable reals can be approximated with explicit rationals to any degree of accuracy in a finite number of steps.
Proof:
Construct n Turing machines consecutively, truncating the initial integer, and compute each one's output as a digit string n digits long. Use some formula to change each diagonal digit.
The infinite diagonal cannot be encoded as a Turing machine number, so it is not enumerable. Yet a computer can compute its approximation as a rational up to n. (The accuracy of this approximation is the same as the accuracy obtainable, in principle, for an enumerable irrational.)
Comment: The denumerable set of computables implies an extension of the concept of denumerability.
Justification:
We give these instructions for diagonalizing Turing computables:
Up to and including the nth diagonal space, follow this rule: if a digit is not 0, replace it with 0; if 0, replace it with 1. After the nth diagonal space, follow this rule: if a digit is not 2, replace it with 2; if it is 2, replace it with 3.
None of these diagonals is enumerable with respect to the Turing numbers. Yet we have a countably infinite set of diagonals. Hence, non-denumerability implies the existence of two denumerable sets of reals which are not denumerable with respect to each other.
If we diagonalize the diagonals, it is not apparent to me that this real is not a member of the computables.
Definition of choice sequence:
If f(n) gives an of cauchy sequence {an}, then {an} is a choice sequence if f(n) --> aon+1 or a1n+1 or . . . or amn+1.
Note i.Since a choice sequence is cauchy |am - an| <= 1/k for all m and n after some no. However, the rule for determining step n+1 means that more than one choice sequence is possible for every n after some no. That is, a choice sequence's limiting value must fall within an upper and lower bound.
Note ii: It may be that axn+1 is non-randomly determined. Yet, there exists an infinity of choice sequences such that the limiting value of {an} is an effectively random element of some infinite subset of reals (known as a 'spread') bounded by a least upper bound and a greatest lower bound.
Remark: Though choice sequences are primarily of interest to intuitionists, here we require that they be governed by ZFC.
Theorem: The question of whether the set of choice sequences contains an element with a non-enumerable limiting value is not decidable.
Proof:
We first prove (Lemma i) that within a spread (x,y), with x the GLB and y the LUB, a non-enumerable exists.
Use a diagonalization formula on the digit string outputs from the set of Turing machines, obtaining one non-enumerable real. Prefix, in turn, every rational digit string to this real and then move the decimal point to the front of each new string. Lemma i is proved.
So then suppose x and y are irrational enumerables. Rationals arbitrarily close to x from above and to y from below can be found.
Let x < p and q < y. So calling the choice sequence limit L, we have
Case i: (x < p < L < q < y).
Case ii: The possibility x < L < p exists, but then a smaller rational can be found between x and L.
Case iii: Likewise for the possibility q < L < y.
It is now straightforward that if L is a choice function limit, there is an effectively random possibility that L is enumerable or non-enumerable. This possibility is in principle undecidable.
Though probability laws suggest that the set of choice sequences includes a sequence with a non-enumerable limit, this suggestion is undecidable.
The cosmos cannot be fully modeled as a Turing machine or Turing computation
Dave Selke, an electrical engineer with a computer background, has made a number of interesting comments concerning this page, spurring me to redo the argument in another form. The new essay is entitled "On Hilbert's sixth problem" and may be found at
http://paulpages.blogspot.com/2011/11/first-published-tuesday-june-26-2007-on.html
Draft 3 (Includes discussion of Wolfram cellular automata)
Comments and suggestions welcome
Note: The word "or" is usually used in the following discussion in the inclusive sense.
Many subscribe to the view that the cosmos is essentially a big machine which can be analyzed and understood in terms of other machines.
A well-known machine is the general Turing machine, which is a logic system that can be modified to obtain any discrete-input computation. Richard Feynman, the brilliant physicist, is said to have been fascinated by the question of whether the cosmos is a computer -- originally saying no but later insisting the opposite. As a quantum physicist, Feynmen would have realized that the question was difficult. If the cosmos is a computer, it certainly must be a quantum computer. But what does that certainty mean? Feynmen, one assumes, would also have concluded that the cosmos cannot be modeled as a classical computer, or Turing machine [see footnote below].
Let's entertain the idea that the cosmos can be represented as a Turing machine or Turing computation. This notion is equivalent to the idea that neo-classical science (including relativity theory) can explain the cosmos. That is, we could conceive of every "neo-classical action" in the cosmos to date -- using absolute cosmic time, if such exists -- as being represented by a huge logic circuit, which in turn can be reduced to some instance (computation) of a Turing algorithm. God wouldn't be playing dice.
A logic circuit always follows if-then rules, which we interpret as causation. But, as we know, at the quantum level, if-then rules only work (with respect to the observer) within constraints, so we might very well argue that QM rules out the cosmos being a "classical" computer.
On the other hand, some would respond by arguing that quantum fuzziness is so miniscule on a macroscopic (human) scale, that the cosmos can be quite well represented as a classical machine. That is, the fuzziness cancels out on average. They might also note that quantum fluctuations in electrons do not have any significant effect on the accuracy of computers -- though this may not be true as computer parts head toward the nanometer scale. (My personal position is that there are numerous examples of the scaling up or amplification of quantum effects. "Schrodinger's cat" is the archetypal example.)
Of course, another issue is that the cosmos should itself have a wave function that is a superposition of all possible states -- until observed by someone (who?). (I will not proceed any further on the measurement problem of quantum physics, despite its many fascinating aspects.)
Before going any further on the subject at hand, we note that a Turing machine is finite (although the set of such machines is denumerably infinite). So if one takes the position that the cosmos -- or specifically, the cosmic initial conditions (or "singularity") -- are effectively infinite, then no Turing algorithm can model the cosmos.
So let us consider a mechanical computer-robot, A, whose program is a general Turing machine. A is given a program that instructs the robotic part of A to select a specific Turing machine, and to select the finite set of initial values (perhaps the "constants of nature"), that models the cosmos.
What algorithm is used to instruct A to choose a specific cosmos-outcome algorithm and computation? This is a typical chicken-or-the-egg self-referencing question and as such is related to Turing's halting problem, Godel's incompleteness theorem and Russell's paradox.
If there is an algorithm B to select an algorithm A, what algorithm selected B? -- leading us to an infinite regression.
Well, suppose that A has the specific cosmic algorithm, with a set of discrete initial input numbers, a priori? That algorithm, call it Tc, and its instance (the finite set of initial input numbers and the computation, which we regard as still running), imply the general Turing algorithm Tg. We know this from the fact that, by assumption, a formalistic description of Alan Turing and his mathematical logic result were implied by Tc. On the other hand, we know that every computable result is programable by modifying Tg. All computable results can be cast in the form of "if-then" logic circuits, as is evident from Turing's result.
So we have
Tc <--> Tg
Though this result isn't clearly paradoxical, it is a bit disquieting in that we have no way of explaining why Turing's result didn't "cause" the universe. That is, why didn't it happen that Tg implied Turing who (which) in turn implied the Big Bang? That is, wouldn't it be just as probable that the universe kicked off as Alan Turing's result, with the Big Bang to follow? (This is not a philisophical question so much as a question of logic.)
Be that as it may, the point is that we have not succeeded in fully modeling the universe as a Turing machine.
The issue in a nutshell: how did the cosmos instruct itself to unfold? Since the universe contains everything, it must contain the instructions for its unfoldment. Hence, we have the Tc instructing its program to be formed.
Another way to say this: If the universe can be modeled as a Turing computation, can it also be modeled as a program? If it can be modeled as a program, can it then be modeled as a robot forming a program and then carrying it out?
In fact, by Godel's incompleteness theorem, we know that the issue of Tc "choosing" itself to run implies that the Tc is a model (mathematically formal theory) that is inconsistent or incomplete. This assertion follows from the fact that the Tc requires a set of axioms in order to exist (and hence "run"). That is, there must be a set of instructions that orders the layout of the logic circuit. However, by Godel's result, the Turing machine is unable to determine a truth value for some statements relating to the axioms without extending the theory ("rewiring the logic circuit") to include a new axiom.
This holds even if Tc = Tg (though such an equality implies a continuity between the program and the computation which perforce bars an accurate model using any Turing machines).
So then, any model of the cosmos as a Boolean logic circuit is inconsistent or incomplete. In other words, a Turing machine cannot fully describe the cosmos.
If by "Theory of Everything" is meant a formal logico-mathematical system built from a finite set of axioms [though, in fact, Zermelo-Frankel set theory includes an infinite subset of axioms], then that TOE is either incomplete or inconsistent. Previously, one might have argued that no one has formally established that a TOE is necessarily rich enough for Godel's incompleteness theorem to be known to apply. Or, as is common, the self-referencing issue is brushed aside as a minor technicality.
Of course, the Church thesis essentially tells us that any logico-mathematical system can be represented as a Turing machine or set of machines and that any logico-mathematical value that can be expressed from such a system can be expressed as a Turing machine output. (Again, Godel puts limits on what a Turing machine can do.)
So, if we accept the Church thesis -- as most logicians do -- then our result says that there is always "something" about the cosmos that Boolean logic -- and hence the standard "scientific method" -- cannot explain.
Even if we try representing "parallel" universes as a denumerable family of computations of one or more Turing algorithms, with the computational instance varying by input values, we face the issue of what would be used to model the master programer.
Similarly, one might imagine a larger "container" universe in which a full model of "our" universe is embedded. Then it might seem that "our" universe could be modeled in principle, even if not modeled by a machine or computation modeled in "our" universe. Of course, then we apply our argument to the container universe, reminding us of the necessity of an infinity of extensions of every sufficiently rich theory in order to incorporate the next stage of axioms and also reminding us that in order to avoid the paradox inherent in the set of all universes, we would have to resort to a Zermelo-Frankel-type axiomatic ban on such a set.
Now we arrive at another point: If the universe is modeled as a quantum computation, would not such a framework possibly resolve our difficulty?
If we use a quantum computer and computation to model the universe, we will not be able to use a formal logical system to answer all questions about it, including what we loosely call the "frame" question -- unless we come up with new methods and standards of mathematical proof that go beyond traditional Boolean analysis.
Let us examine the hope expressed in Stephen Wolfram's New Kind of Science that the cosmos can be summarized in some basic rule of the type found in his cellular automata graphs.
We have no reason to dispute Wolfram's claim that his cellular automata rules can be tweaked to mimic any Turing machine. (And it is of considerable interest that he finds specific CA/TM that can be used for a universal machine.)
So if the cosmos can be modeled as a Turing machine then it can be modeled as a cellular automaton. However, a CA always has a first row, where the algorithm starts. So the algorithm's design -- the Turing machine -- must be axiomatic. In that case, the TM has not modeled the design of the TM nor the specific initial conditions, which are both parts of a universe (with that word used in the sense of totality of material existence).
We could of course think of a CA in which the first row is attached to the last row and a cylinder formed. There would be no specific start row. Still, we would need a CA whereby the rule applied with aribitrary row n as a start yields the same total output as the rule applied at arbitrary row m. This might resolve the time problem, but it is yet to be demonstrated that such a CA -- with an extraordinarily complex output -- exists. (Forgive the qualitative term extraordinarily complex. I hope to address this matter elsewhere soon.)
However, even with time out of the way, we still have the problem of the specific rule to be used. What mechanism selects that? Obviously it cannot be something from within the universe. (Shades of Russell's paradox.)
Footnote
Informally, one can think of a general Turing machine as a set of logic gates that can compose any Boolean network. That is, we have a set of gates such as "not", "and," "or," "exclusive or," "copy," and so forth. If-then is set up as "not-P or Q," where P and Q themselves are networks constructed from such gates. A specific Turing machine will then yield the same computation as a specific logic circuit composed of the sequence of gates.
By this, we can number any computable output by its gates. Assuming we have less than 10 gates (which is more than necessary), we can assign a base-10 digit to each gate. In that case, the code number of the circuit is simply the digit string representing the sequence of gates.
Note that circuit A and circuit B may yield the same computation. Still, there is a countable infinity of such programs, though, if we use any real for an input value, we would have an uncountable infinity of outputs. But this cannot be, because an algorithm for producing a real number in a finite number of steps can only produce a rational approximation of an irrational. Hence, there is only a countable number of outputs.
*************************
Thanks to Josh Mitteldorf, a mathematician and physicist, for his incisive and helpful comments. Based upon a previous draft, Dr. Mitteldorf said he believes I have shown that, if the universe is finite, it cannot be modeled by a subset of itself but he expressed wariness over the merit of this point.
No comments:
Post a Comment