Uncommon Descent Serving The Intelligent Design Community

# AI, state/configuration space search and the ID search challenge

Share
Flipboard
Print
Email

In his well-known work, No Free Lunch, p. 11, ID Researcher William A Dembski has illustrated the search challenge concept in terms of an arrow hitting a target amidst a reference class of possibilities. In so doing, he reaches back to the statistical mechanical and mathematical concept of a phase space “cut down” to address configurations only (leaving out momentum), aka state space.  He then goes on to speak in terms of probabilities, observing:

>>. . . in determining whether an event is sufficiently improbable or complex to implicate design, the relevant probability is not that of the event [= E] itself. In the archery example, that probability corresponds to the size of the arrowhead point in relation to the size of the wall and will be minuscule regardless of whether a target [= T] is painted on the wall. Rather the relevant probability is that of hitting the target . . . [corresponding] to the size of the target in relation to the wall and can take any value between zero and one . . . The smaller the target the harder it is to hit it by chance and thus apart from design. The crucial probability then is the probability of the target with respect to the reference class of possible events [= Omega, Ω . . . traditionally used in statistical mechanics]. [NFL, p. 11.]>>

We may now freely correlate this with the AI concept of state-space search, as was recently pointed out in the Answering DiEb UD discussion thread:

KF, 30: >>Note this from Wiki on searches of a state space:

State space search is a process used in the field of computer science, including artificial intelligence (AI), in which successive configurations or states of an instance are considered, with the intention of finding a goal state with a desired property.

Problems are often modelled as a state space, a set of states that a problem can be in. The set of states forms a graph where two states are connected if there is an operation that can be performed to transform the first state into the second.

State space search often differs from traditional computer science search methods because the state space is implicit: the typical state space graph is much too large to generate and store in memory. Instead, nodes are generated as they are explored, and typically discarded thereafter. A solution to a combinatorial search instance may consist of the goal state itself, or of a path from some initial state to the goal state.

Representation

Examples of State-space search algorithms

Uninformed Search

According to Poole and Mackworth, the following are uninformed state-space search methods, meaning that they do not know information about the goal’s location.[1]

Depth-first search
Lowest-cost-first search

Informed Search

Some algorithms take into account information about the goal node’s location in the form of a heuristic function[2]. Poole and Mackworth cite the following examples as informed search algorithms:

Heuristic depth-first search
Greedy best-first search
A* search

Muy interesante, no? . . . .   Cf my remarks above [which provide a definition of search tied to the state/configuration space concept]:

Several times, you [DiEb] have raised the issue of search [ –> as in, in recent exchanges at UD]. I have pointed out that at base, it is tantamount to sampling from a configuration space.

[As, algebraic representation is commonly desired (and is often deemed superior to illustration or verbal description), a traditional representation of such a space is to symbolise it as Omega, here we can use w. Search then is obviously — and the obviousness is a material point here — tantamount to taking a subset of cases k in w by whatever relevant means, blind or intelligent. The search challenge then is to find some relevant zone z in w such that a performance based on configuration rises above a floor deemed non-functional: find/happen upon some z_i in w such that p(z) GT/eq f_min. Zones z are islands of function in the configuration space, w.]>>

The correlations are patent.

Now, let us adjust. First, the relevant reference class of possibilities is the state or configuration space, Ω  [which for combox convenience I and others often represent as w or W].  Here, see Boltzmann’s tomb, recording the key contribution that tragic figure wished to forever be remembered for:

And yes, entropy S is directly connected. (So, too, in the informational sense.)

Next, consider the case where there may be many potential targets, dotted about a — still abstract — space of possibilities and where many searches are conducted in parallel — think of Shakespeare’s King Henry V, with English and Welsh longbow-men at Agincourt facing the French Chivalry [= heavy armoured cavalry] coming at them. Estimates have suggested longbow-men mass-volleys of 40,000 shafts per minute and of the cloud of arrows briefly and brutally shading out the sun. Obviously, this improves the odds of hitting some one or more targets [especially the poor innocent horses], as the outcome of that battle notoriously testifies:

However, we note, there are only so many arrows, and each shot taken diminishes the supply; each volley also takes time. There is a COST to each instance of parallel target-seeking by the collective longbow-men. And so at Agincourt there was an exchange between rate and cumulative volume of fire and the time the Chivalry charge would take to cross to the point where lance and sword could bite home. As would happen on that horrible July 1, 1916 on the Somme, the attackers decisively lost the exchange.

These concrete [though, pardon, awful] real-world cases can help us to now understand the relevant kinds of “search” that ID is addressing.

Obviously, a search pattern, whether by one observer or by many in parallel, samples from the space of possibilities, and each individual “shot” can hit or miss the targets, while there is a cost of time and resources for every shot. But now, we first ponder, what happens when targets are isolated and scattered across a vast space of possibilities? Where, also, resources are very limited so in aggregate they will be exhausted long before other than an all-but-zero fraction of the space is sampled? And, what happens if the bowman is blind-folded and deaf so he cannot sense where a target is likely to be? And what if we now revert to purposeless “bow-men” scattering their “shots” at random and/or based on some mechanical necessity not correlated to where targets are?

That is, we are now looking at needle-in-the-haystack, blind search:

In that light, let us now look briefly at a later discussion by Dembski in which he implies that kind of blind bow-men scattershot search. Though, I must request a look with fresh eyes, not the mind full of objections and real or imagined peculiarities and personalities. Notice, how closely Dembski’s conceptions mirror what we have seen above, underscoring the relevance of the description of what search is as relevant to ID:

KF, 22 : >>William A. Dembski and Robert J. Marks II, “The Search for a Search: Measuring the Information Cost of Higher Level Search,” Journal of Advanced Computational Intelligence and Intelligent Informatics, Vol.14, No.5, 2010, pp. 475-486.

Abstract

Needle-in-the-haystack [search] problems look for small targets in large spaces. In such cases, blind search stands no hope of success. Conservation of information dictates any search technique [–> as in not specifically correlated to the structure of the space, i.e. a map of the targets] will work, on average, as well as blind search. Success requires an assisted [intelligently directed, well-informed] search. But whence the assistance required for a search to be successful? To pose the question this way suggests that successful searches do not emerge spontaneously but need themselves to be discovered via a search. The question then naturally arises whether such a higher-level “search for a search” is any easier than the original search.

[–> where once search is taken as implying sample, searches take subsets so the set of possible searches is tantamount to the power set of the original set. For a set of cardinality n, the power set has cardinality 2^n.]

We prove two results: (1) The Horizontal No Free Lunch Theorem, which shows that average relative performance of searches never exceeds unassisted or blind searches, and (2) The Vertical No Free Lunch Theorem, which shows that the difficulty of searching for a successful search increases exponentially with respect to the minimum allowable active information being sought.

1. Introduction

Conservation of information theorems [1–3], especially the No Free Lunch Theorems (NFLT’s) [4–8], show that without prior information about a search environment or the target sought, one search strategy is, on average, as
good as any other [9]. This is the result of the Horizontal NFLT presented in Section 3.2.

A search’s difficulty can be measured by its endoge-nous information [1, 10–14] defined as

I_w = – log_2 p …………. (1)

where p is the probability of a success from a random query [1]. When there is knowledge about the target lo-cation or search space structure, the degree to which the search is improved is determined by the resulting active information[1, 10–14]. Even moderately sized searches are virtually certain to fail in the absence of knowledge about the target location or the search space structure. Knowledge concerning membership of the search prob-lem in a structured class [15], for example, can constitute search space structure information [16].

Endogenous and active information together allow for a precise characterization of the conservation of
informa-tion. The average active information, or active entropy,of an unassisted search is zero when no assumption is made concerning the search target. If any assumption is made concerning the target, the active entropy becomes negative. This is the Horizontal NFLT presented in Sec-tion 3.2. It states that an arbitrary search space structure will, on average, result in a worse search than assuming nothing and simply performing an unassisted search . . . >>

Here, searches can come from a configuration space of possibilities blindly by chance and/or by some mechanism which in general is not correlated to the target-map of the space of possibilities. Once the ratio of space to target approaches the needle in haystack challenge level, blind searches are not a plausible means of getting to one or more targets. In that context the gap between blind search and observed hitting of targets is best explained on direction through so-called active information. That may be externally provided or may arise from an implicit mapping by hill climbing on a performance that rises above a floor of non-function, once the space has a sufficiently smooth slope that such will not fall into the pitfalls for hill-climbing.

Function based on complex, coherent, information-rich organisation — functionally specific, complex organisation and/or information [FSCO/I] is now present. As an illustration:

Just for fun, let me add [Feb 3] an illustration of gearing found in life forms:

Let’s compare a gear train:

And, what is required informationally and organisationally to make the precise matching:

A moment’s reflection on such configurations will instantly tell us that there is an abstract space of possible configurations of the parts, scattered or clumped together, of which only a very few, proportionately, will rise above the floor of non-function to work as a fishing reel. Thus we see FSCO/I and the reason why it arises in deeply isolated, rare, islands of function in spaces of possibilities. For, well matched, correctly oriented, aligned and coupled parts must be brought together for functionality to result.

We can pause for a moment to speak to those who now wish to race off on side-tracks about how biological, cell based life reproduces and that renders the above irrelevant. The problem is, part of what is to be explained is that as von Neumann suggested, such cell based life uses FSCO/I-rich facilities, the von Neumann kinematic self-replicator, to achieve this capability:

In short, at OOL, the appeal to vNSR has to be addressed in terms of explaining the FSCO/I in it on precisely the sort of blind search challenge that has been discussed; credibly requiring 100 – 1,000 kbits of genetic information coupled to execution machinery and an encapsulated metabolic entity, which has to form in a plausible environment by blind processes demonstrated to be feasible per observation, not speculation or speculation on steroids by way of computer simulation. Then, to move on to explain the variety of major body plans, innovations of 10 – 100+ million bits of further information and associated systems has to be accounted for.

Where, just 500 – 1,000 bits of information correspond to configuration spaces of order 3.27*10^150 to 1.07*10^301 possibilities.  And yes, we can here represent the search challenge in the very generous terms of the 10&57 atoms of our solar system or the 10^80 of the observed cosmos each making 10^14 [fast chemical reaction rate, especially for organic chemistry] observations of a tray of coins (or equivalently a paramagnetic substance) every second, for 10^17 s, comparable tot he time to the singularity:

(In short, we can readily see the emptiness of dismissive remarks on “big numbers” that too often appear in UD’s objector sites.)

The search challenge then becomes a matter of a space of possibilities explored through random walks (including dusted hops) and/or equally blind trajectories based on mechanical necessity. The target zones are islands of function out there in the space of possibilities corresponding of course to cell based life.  The first challenge is to get to the shoreline of a first such island of function. Once there, presumably population variation and selection driven hill-climbing may operate within the island of function, subject to the problems of such hill climbing. But then, to move across to another island of function for a novel body plan, intervening seas of non-function will have to be crossed, precisely what hill-climbing is not applicable to. Where, no, it is not plausible that there is a grand continent of functionality, starting from the known scattering of protein fold domains in amino acid configuration space, a part of the whole situation.

We may freely illustrate:

And:

So, we may see that in an ID context informed by the AI approach of state space search (or more broadly, the underlying statistical mechanics approaches):

KF, :>>search . . . is tantamount to sampling from a configuration space.

[As, algebraic representation is commonly desired (and is often deemed superior to illustration or verbal description), a traditional representation of such a space is to symbolise it as Omega, here we can use w. Search then is obviously — and the obviousness is a material point here — tantamount to taking a subset of cases k in w by whatever relevant means, blind or intelligent. The search challenge then is to find some relevant zone z in w such that a performance based on configuration rises above a floor deemed non-functional: find/happen upon some z_i in w such that p(z) GT/eq f_min. Zones z are islands of function in the configuration space, w.]

In that context, the search problem is to solve the search challenge as identified, especially for large configuration spaces that exceed 10^150 – 10^300 possibilities, i.e. for 500 – 1,000 bits as a threshold. The answer to which is, that there is no credible solution by blind chance and/or mechanical necessity within the scope of the sol system to the observed cosmos. I add: intelligently directed configuration, using insight, routinely solves this problem, e.g. posts pro and con in this thread. The observed base of cases exceeds a trillion.

A search algorithm can be identified as attacking the search problem i/l/o the relevant possible searches, modulo the issue that there may be a need to intervene and impose a computational halt as some searches may run without limit if simply left to their inherent dynamics. Where, an algorithm is generally understood to be a finite, stepwise computational process that starts with a given initial point and proceeds to provide a result that is intended by its creator. This obtains for computation, which may model the real world situation which is dynamical rather than algorithmic.

I would consider that, given the context, search problems and algorithms are relatively trivial to understand, once search has been adequately conceptualised [and as above, further informed by the AI approach, state space search].>>

All of this then feeds into the reason why the design inference explanatory filter (here in successive, per aspect form) is credibly reliable in identifying cases of design as materially relevant cause, simply from observing FSCO/I:

For, the first decision step distinguishes highly contingent from low contingency situations, filtering off cases where mere mechanical necessity is the best explanation of a particular aspect. At the second decision node we filter off things of low complexity and also cases where the function is not of relevant type: specific, highly complex [thus a large configuration space], dependent on synergistic interaction of parts.

While in many cases this is an interesting exercise in mathematical modelling or analysis, it is not actually relevant to search challenge.

For, we may readily identify when a search is of excessive cost comparable to even the atomic resources of our solar system and/or the observed cosmos. Once complexity is beyond 500 – 1,000 bits, that is enough for our purposes. Under that scope of possibilities, the relevant resources cannot blindly search sufficient of the space to make any happening on a target seem plausible. If a target was hit under these circumstances, the best explanation per Newton’s vera causa principle of actually observed causes being used in scientific explanations, is active information conveying an implicit map or else intelligence that puts us down next to a target zone/ island of function or else a golden search that must be similarly selected with insightful knowledge of the possibilities.

So, we have excellent reason to freely conclude that the basic design inference and underlying frame of thought — never mind all sorts of objections that have been made or that will continue to be made — are well-founded. But those objections are so persistent that it is sometimes necessary to take a sledgehammer to a cashew nut. END

Re CR: Notice, the unmet challenge after 5 days, re 7 above:
Your actual evidence for a different architecture of life is ______ and the way it avoids a complex and functionally integrated metabolic network is _____ , it avoids proteins by _______ , it avoids molecular storage media by _____ and it avoids a kinematic self replicator by ____ . This was observed by ____ and they won the Nobel or equivalent prize on ____ .
KFkairosfocus
February 9, 2018
February
02
Feb
9
09
2018
01:41 AM
1
01
41
AM
PDT
PPS: If you want that in more "scientific" language, here are Walker and Davies:
In physics, particularly in statistical mechanics, we base many of our calculations on the assumption of metric transitivity, which asserts that a system’s trajectory will eventually [--> given "enough time and search resources"] explore the entirety of its state space – thus everything that is phys-ically possible will eventually happen. It should then be trivially true that one could choose an arbitrary “final state” (e.g., a living organism) and “explain” it by evolving the system backwards in time choosing an appropriate state at some ’start’ time t_0 (fine-tuning the initial state). In the case of a chaotic system the initial state must be specified to arbitrarily high precision. But this account amounts to no more than saying that the world is as it is because it was as it was, and our current narrative therefore scarcely constitutes an explanation in the true scientific sense. We are left in a bit of a conundrum with respect to the problem of specifying the initial conditions necessary to explain our world. A key point is that if we require specialness in our initial state (such that we observe the current state of the world and not any other state) metric transitivity cannot hold true, as it blurs any dependency on initial conditions – that is, it makes little sense for us to single out any particular state as special by calling it the ’initial’ state. If we instead relax the assumption of metric transitivity (which seems more realistic for many real world physical systems – including life), then our phase space will consist of isolated pocket regions and it is not necessarily possible to get to any other physically possible state (see e.g. Fig. 1 for a cellular automata example).
[--> or, there may not be "enough" time and/or resources for the relevant exploration, i.e. we see the 500 - 1,000 bit complexity threshold at work vs 10^57 - 10^80 atoms with fast rxn rates at about 10^-13 to 10^-15 s leading to inability to explore more than a vanishingly small fraction on the gamut of Sol system or observed cosmos . . . the only actually, credibly observed cosmos]
Thus the initial state must be tuned to be in the region of phase space in which we find ourselves [--> notice, fine tuning], and there are regions of the configuration space our physical universe would be excluded from accessing, even if those states may be equally consistent and permissible under the microscopic laws of physics (starting from a different initial state). Thus according to the standard picture, we require special initial conditions to explain the complexity of the world, but also have a sense that we should not be on a particularly special trajectory to get here (or anywhere else) as it would be a sign of fine–tuning of the initial conditions. [ --> notice, the "loading"] Stated most simply, a potential problem with the way we currently formulate physics is that you can’t necessarily get everywhere from anywhere (see Walker [31] for discussion). ["The “Hard Problem” of Life," June 23, 2016, a discussion by Sara Imari Walker and Paul C.W. Davies at Arxiv.]
kairosfocus
February 9, 2018
February
02
Feb
9
09
2018
01:36 AM
1
01
36
AM
PDT
F/N: For convenience let me clip from another thread and highlight an exchange here: Non-lin, 2: >>"For more than half a century it has been accepted that new genetic information is mostly derived from random‚ error-based’ events. Now it is recognized that errors cannot explain genetic novelty and complexity." This has been known for a while: http://nonlin.org/random-abuse/ … The Infinite Monkeys theorem affirms that randomness could create Hamlet or The Odyssey (but the argument is really about life forms, not about literature). Indeed, a random process could theoretically generate these masterpieces. And if we allow for many alternative targets (like any document ever created), the probability of success goes up substantially. Quite likely, the “monkeys” would have duplicated many other information (like chemical formulas) way before typing Hamlet. But monkeys care about bananas, not Hamlet, so the random output remains meaningless until an educated reader assigns meaning based on his/her prior knowledge. Hamlet and Odyssey are important precisely because we recognize them as non-random. They fit in our history and culture and have been preceded and followed by other non-random creations. Creators, not Randomness, provide meanings.>> KF,4: >>Non-lin, actually, on factoring in atomic and temporal resources and costs, no feasible number of monkeys would ever credibly arrive at a significant result by chance. The point is, that the abstractly possible (to arrive at any particular configuration in a space of possibilities by blind chance and/or mechanical necessity) is not to be confused with what is plausibly feasible (to be dominated by the implications of relative statistical weights of clusters of possible states, as the 2nd law of thermodynamics emphasises). That is closely tied to the search challenge issue to find islands of function in large configuration spaces that is being discussed in several other threads.>> N-L, 6: >>are you referring to something like this: https://uncommondescent.com/informatics/ai-state-configuration-space-search-and-the-id-search-challenge/? I have to review it first, but it’s likely a weaker argument. First because they can say “no one is searching for anything”, and second because they might say “because there’s no target and no search, the outcomes we see have been reached much faster than a search algorithm predicts”. On the other hand, it’s indisputable that information requires an intelligent user/creator. Also “randomness” is mathematically unknowable, so they can’t possibly defend that claim. Let’s keep it simple, remember?>> KF, 7: >>the claim no ONE is acting as a self-aware, volitional agent doing a search is not a refutation of, we have a space of possibilities being explored by natural random walk/hop and/or mechanical/"ballistic" trajectory processes as molecules interact in Darwin's pond or the like. Evolutionary search algorithms is a known field of study, and the ideas are broadly connected to neural network "learning" also. The further arguments about broad sense hill-climbing in a field of possibilities through the differential outcomes on a fitness landscape is also relevant. I am in effect pointing out that such a fitness landscape of clustered or scattered atoms and molecules is overwhelmingly dominated by seas of biologically non-functional gibberish. So the core search-challenge is to reach shorelines of coherent, configuration-driven function that rise above the gibberish level. Search is a handy term and one used in the field. I suspect we may be seeing yet another run of the no true englishsman [--> "Scientist"] speaks in those terms game. As in, whenever design thinkers etc use a term often enough, it is disdained in popular literature or by internet atheists and popularisers as though the terms are idiosyncratic or are being somehow distorted. A glance at the UD weak argument correctives will show cases in point with thinks like macro vs micro evolution, [neo-]darwinism etc. Rhetorical dirty tricks like that are a sign that the point has been lost on the merits. A good example of islands of function in seas of non function is protein-functional molecules in amino acid sequence space, especially given deeply isolated domains that follow no obviously closely related structural pattern that leads to evolutionary sequence hypotheses. In general, complex, configuration-driven function depends on well-matched, correctly oriented, arranged and coupled parts forming a coherent whole. I have often illustrated with the Abu 6500 3C fishing reel exploded diagram, and notice the sneering snickers that pretend that a point is not being made by way of undeniable fact. That same functionally specific, complex organisation and/or associated information [FSCO/I for short] is manifest in the bacterial flagellum on UD's masthead above. It is found in ATP synthase. It is found in mRNA, tRNA and DNA. It is in ribosomes. It is in other functional units in the cell. It is in the integrated metabolic reaction set of the cell -- compare a petroleum refinery -- and much more. The sneering is a sign that the point has been lost on the merits but there is a zero concession, animus-driven policy in effect towards those IDiots. And yes, more polite objectors, ponder the company you keep and the behaviour you enable and give respectable cover to. I suspect many objectors are unfamiliar with the common concept in statistical thermodynamics of an ensemble of systems starting from similar initial conditions and then spontaneously playing out from there. Resemblance to the model of each atom in the observed cosmos [~10^80] observing a tray of 1,000 coins in a string flipping at 10^14 times/s for 10^17 s is not coincidental. And, coins are a stand-in for a simple bidirectional paramagnetic substance subject to a weak orienting field and subject to thermal disorientation. The point is, this explores a toy model digital space of 1.07*10^301 possibilities, and gives a picture of a describing/specifying language. Tie together enough of these strings and any 3-d entity can be described in some language so discussion on such strings is WLOG. It also happens to pose a very simple experimental test: use blind chance and/or blind mechanical necessity to produce FSCO/I-rich strings by way of say computer runs. This has actually been tried and it underscores the 500 - 1,000 bit threshold, once we recognise that ASCII codes use up the 128 available states for 7 bits. Let me again clip the Wiki article on the infinite monkeys theorem, on random text generation:
The theorem concerns a thought experiment which cannot be fully carried out in practice, since it is predicted to require prohibitive amounts of time and resources. Nonetheless, it has inspired efforts in finite random text generation. One computer program run by Dan Oliver of Scottsdale, Arizona, according to an article in The New Yorker, came up with a result on August 4, 2004: After the group had worked for 42,162,500,000 billion billion monkey-years, one of the "monkeys" typed, "VALENTINE. Cease toIdor:eFLP0FRjWK78aXzVOwm)-‘;8.t" The first 19 letters of this sequence can be found in "The Two Gentlemen of Verona". Other teams have reproduced 18 characters from "Timon of Athens", 17 from "Troilus and Cressida", and 16 from "Richard II".[24] A website entitled The Monkey Shakespeare Simulator, launched on July 1, 2003, contained a Java applet that simulated a large population of monkeys typing randomly, with the stated intention of seeing how long it takes the virtual monkeys to produce a complete Shakespearean play from beginning to end. For example, it produced this partial line from Henry IV, Part 2, reporting that it took "2,737,850 million billion billion billion monkey-years" to reach 24 matching characters: RUMOUR. Open your ears; 9r"5j5&?OWTY Z0d... Due to processing power limitations, the program used a probabilistic model (by using a random number generator or RNG) instead of actually generating random text and comparing it to Shakespeare. When the simulator "detected a match" (that is, the RNG generated a certain value or a value within a certain range), the simulator simulated the match by generating matched text.[25] More sophisticated methods are used in practice for natural language generation. If instead of simply generating random characters one restricts the generator to a meaningful vocabulary and conservatively following grammar rules, like using a context-free grammar, then a random document generated this way can even fool some humans (at least on a cursory reading) as shown in the experiments with SCIgen, snarXiv, and the Postmodernism Generator.
A factor of 10^100 short of searching 10^150 possibilities [~500 bits]. Do I dare to suggest: empirical support for a longstanding prediction? And, do you notice how, to get more functional results, more and more intelligently directed configuration has to be front-loaded in? In short, we are seeing an inadvertent confirmation of the power of the per aspect, FSCO/I based design inference explanatory filter. Not too shabby for those IDiots, nuh?>> Let's see how this plays out. KF PS: Let me clip the opening remarks in the Wiki article, on more admission against known ideological interests:
The infinite monkey theorem states that a monkey hitting keys at random on a typewriter keyboard for an infinite amount of time will almost surely type a given text, such as the complete works of William Shakespeare. In fact the monkey would almost surely type every possible finite text an infinite number of times. However, the probability that monkeys filling the observable universe would type a complete work such as Shakespeare's Hamlet is so tiny that the chance of it occurring during a period of time hundreds of thousands of orders of magnitude longer than the age of the universe is extremely low (but technically not zero). In this context, "almost surely" is a mathematical term with a precise meaning, and the "monkey" is not an actual monkey, but a metaphor for an abstract device that produces an endless random sequence of letters and symbols. One of the earliest instances of the use of the "monkey metaphor" is that of French mathematician Émile Borel in 1913,[1] but the first instance may have been even earlier. Variants of the theorem include multiple and even infinitely many typists, and the target text varies between an entire library and a single sentence. Jorge Luis Borges traced the history of this idea from Aristotle's On Generation and Corruption and Cicero's De natura deorum (On the Nature of the Gods), through Blaise Pascal and Jonathan Swift, up to modern statements with their iconic simians and typewriters. In the early 20th century, Borel and Arthur Eddington used the theorem to illustrate the timescales implicit in the foundations of statistical mechanics.
kairosfocus
February 9, 2018
February
02
Feb
9
09
2018
01:25 AM
1
01
25
AM
PDT
CR
you’re assuming that the biosphere was an intended target
Explicitly, no. Kindly read the OP where that is explicitly pointed out. Further, nowhere have I stipulated the current architecture for life forms, only I have noted that FSCO/I due to the need for well matched, correctly arranged and coupled parts, will lead to deeply isolated islands of function. Your actual evidence for a different architecture of life is ______ and the way it avoids a complex and functionally integrated metabolic network is _____ , it avoids proteins by _______ , it avoids molecular storage media by _____ and it avoids a kinematic self replicator by ____ . This was observed by ____ and they won the Nobel or equivalent prize on ____ . In short, speculative, dismissive IOU's don't count. Meet the Newtonian vera causa standard or fail. KF PS: Kindly observe that the reference to AI in the OP has to do with the state space search strategy, which is used in AI contexts. If you intend to show that this is not a valid search strategy (a significant point in the OP), it's a little late for that. KFkairosfocus
February 4, 2018
February
02
Feb
4
04
2018
05:53 PM
5
05
53
PM
PDT
Artificial General Intelligence will occur when we have breakthrough in epistemology. From this article....
And in any case, AGI cannot possibly be defined purely behaviourally. In the classic ‘brain in a vat’ thought experiment, the brain, when temporarily disconnected from its input and output channels, is thinking, feeling, creating explanations — it has all the cognitive attributes of an AGI. So the relevant attributes of an AGI program do not consist only of the relationships between its inputs and outputs. The upshot is that, unlike any functionality that has ever been programmed to date, this one can be achieved neither by a specification nor a test of the outputs. What is needed is nothing less than a breakthrough in philosophy, a new epistemological theory that explains how brains create explanatory knowledge and hence defines, in principle, without ever running them as programs, which algorithms possess that functionality and which do not. Such a theory is beyond present-day knowledge. What we do know about epistemology implies that any approach not directed towards that philosophical breakthrough must be futile. Unfortunately, what we know about epistemology is contained largely in the work of the philosopher Karl Popper and is almost universally underrated and misunderstood (even — or perhaps especially — by philosophers). For example, it is still taken for granted by almost every authority that knowledge consists of justified, true beliefs and that, therefore, an AGI’s thinking must include some process during which it justifies some of its theories as true, or probable, while rejecting others as false or improbable. But an AGI programmer needs to know where the theories come from in the first place. The prevailing misconception is that by assuming that ‘the future will be like the past’, it can ‘derive’ (or ‘extrapolate’ or ‘generalise’) theories from repeated experiences by an alleged process called ‘induction’. But that is impossible. I myself remember, for example, observing on thousands of consecutive occasions that on calendars the first two digits of the year were ‘19’. I never observed a single exception until, one day, they started being ‘20’. Not only was I not surprised, I fully expected that there would be an interval of 17,000 years until the next such ‘19’, a period that neither I nor any other human being had previously experienced even once. How could I have ‘extrapolated’ that there would be such a sharp departure from an unbroken pattern of experiences, and that a never-yet-observed process (the 17,000-year interval) would follow? Because it is simply not true that knowledge comes from extrapolating repeated observations. Nor is it true that ‘the future is like the past’, in any sense that one could detect in advance without already knowing the explanation. The future is actually unlike the past in most ways. Of course, given the explanation, those drastic ‘changes’ in the earlier pattern of 19s are straightforwardly understood as being due to an invariant underlying pattern or law. But the explanation always comes first. Without that, any continuation of any sequence constitutes ‘the same thing happening again’ under some explanation. So, why is it still conventional wisdom that we get our theories by induction? For some reason, beyond the scope of this article, conventional wisdom adheres to a trope called the ‘problem of induction’, which asks: ‘How and why can induction nevertheless somehow be done, yielding justified true beliefs after all, despite being impossible and invalid respectively?’ Thanks to this trope, every disproof (such as that by Popper and David Miller back in 1988), rather than ending inductivism, simply causes the mainstream to marvel in even greater awe at the depth of the great ‘problem of induction’. In regard to how the AGI problem is perceived, this has the catastrophic effect of simultaneously framing it as the ‘problem of induction’, and making that problem look easy, because it casts thinking as a process of predicting that future patterns of sensory experience will be like past ones. That looks like extrapolation — which computers already do all the time (once they are given a theory of what causes the data). But in reality, only a tiny component of thinking is about prediction at all, let alone prediction of our sensory experiences. We think about the world: not just the physical world but also worlds of abstractions such as right and wrong, beauty and ugliness, the infinite and the infinitesimal, causation, fiction, fears, and aspirations — and about thinking itself.
Unless ID's designer can somehow induce theories from observations, how does it manage to obtain the knowledge of which genes will result in just the right proteins that will result in just the right features? Sure, people start out with a specific problem to solve and conjecture explanatory theories of how the world works specifically designed to solve that problem. So, they are not random to the problem to solve. And they are often triggered by observations that reveal problems. Background knowledge plays a role as well. But if the actual contents of theories do not come from observations, then how does ID's designer avoid the process of variation and criticism? In the same sense, arguing that AI will never be able to choose between theories based on observations is a misguided criticism. That task is just as impossible for us as it would be for AI. So, it's a bad criticism.critical rationalist
February 4, 2018
February
02
Feb
4
04
2018
03:14 PM
3
03
14
PM
PDT
First, you're assuming that the biosphere was an intended target. That represents a theory that imposes limits on choices, and then you apply some measure of probability based on that theory. But there is no such assumption in Darwinism. Life could have turned out quite differently and the means by which problems organisms faced are currently solved is not assumed to be the only solution. This is why probability isn't a valid means of choosing between theories. Without knowing what the options are, you can't apply probability. And it theories that determine what the options are. For example, take the question of why life has 20 amino acids, when 13 of those that formed over time would have been sufficient. The best explanation is that an increase of oxygen in the biosphere triggered the evolutionary development of the remaining seven.
All extant life employs the same 20 amino acids for protein biosynthesis. Studies on the number of amino acids necessary to produce a foldable and catalytically active polypeptide have shown that a basis set of 7–13 amino acids is sufficient to build major structural elements of modern proteins. Hence, the reasons for the evolutionary selection of the current 20 amino acids out of a much larger available pool have remained elusive. Here, we have analyzed the quantum chemistry of all proteinogenic and various prebiotic amino acids. We find that the energetic HOMO–LUMO gap, a correlate of chemical reactivity, becomes incrementally closer in modern amino acids, reaching the level of specialized redox cofactors in the late amino acids tryptophan and selenocysteine. We show that the arising prediction of a higher reactivity of the more recently added amino acids is correct as regards various free radicals, particularly oxygen-derived peroxyl radicals. Moreover, we demonstrate an immediate survival benefit conferred by the enhanced redox reactivity of the modern amino acids tyrosine and tryptophan in oxidatively stressed cells. Our data indicate that in demanding building blocks with more versatile redox chemistry, biospheric molecular oxygen triggered the selective fixation of the last amino acids in the genetic code. Thus, functional rather than structural amino acid properties were decisive during the finalization of the universal genetic code.
From the article...
However, the problem remained of why the soft amino acids were added to the tool box in the first place. What exactly were these readily reactive amino acids supposed to react with? On the basis of their results, the researchers conclude that at least some of the new amino acids, especially methionine, tryptophan, and selenocysteine, were added as a consequence of the increase in the levels of oxygen in the biosphere. This oxygen promoted the formation of toxic free radicals, which exposes modern organisms and cells to massive oxidative stress. The new amino acids underwent chemical reactions with the free radicals and thus scavenged them in an efficient manner. The oxidized new amino acids, in turn, were easily repairable after oxidation, but they protected other and more valuable biological structures, which are not repairable, from oxygen-induced damage. Hence, the new amino acids provided the remote ancestors of all living cells with a very real survival advantage that allowed them to be successful in the more oxidizing, "brave" new world on Earth. "With this in view, we could characterize oxygen as the author adding the very final touch to the genetic code," stated Moosmann.
IOW, the target of those 20 amnio acids wan't a predetermined target. Rather, their addition represented a survival advantage.critical rationalist
February 4, 2018
February
02
Feb
4
04
2018
03:03 PM
3
03
03
PM
PDT
F/N: When a "bad dog" with a habit of pouncing suddenly goes missing in action that it itself a significant signal. KFkairosfocus
February 4, 2018
February
02
Feb
4
04
2018
02:22 AM
2
02
22
AM
PDT
F/N: let's compare what DiEb and others said at TSZ on January 29th:
The Search Problem of William Dembski, Winston Ewert, and Robert Marks . . . Search is a central term in the work of Dr. Dr. William Dembski jr, Dr. Winston Ewert, and Dr. Robert Marks II (DEM): it appears in the title of a couple of papers written by at least two of the authors, and it is mentioned hundreds of times in their textbook “Introduction to Evolutionary Informatics“. Strangely – and in difference from the other central term information, it is not defined in this textbook, and neither is search problem or search algorithm. Luckily, dozens of examples of searches are given. I took a closer look to find out what DEM see as the search problem in the “Introduction to Evolutionary Informatics” and how their model differs from those used by other mathematicians and scientists.
It turns out i/l/o the OP above, that the Evo Informatics folks used a reasonable approach to search which is reflective of fairly standard ideas from the world of statistical thermodynamics; phase space and its relatives. Secondly, it turns out that they were trying to capture blind watchmaker search, which is yet another example of how evolutionary thought de-personalises a matter that we are familiar with from intelligent action. For instance, artificial -- designed -- selection for animal breeding became NATURAL selection at Darwin's hands; reflecting the idea to make a designer mimic that then squeezes out the perceived need for a designer to explain functionally specific coherent organisation and associated information. Such is of course at the heart of modern evolutionary theories. Just so, search now becomes de-personalised to become a blind sampling of a configuration or state space that somehow is to stumble upon a zone of relevant functionality that allows hill-climbing. Now, we see that others have used similar search strategies, from Poole and Mackworth as reflected in Wikipedia [a quite common first level reference, even with all its flaws]. On waking back up, let me insert a clip from Wiki:
State space search is a process used in the field of computer science, including artificial intelligence (AI), in which successive configurations or states of an instance are considered, with the intention of finding a goal state with a desired property. Problems are often modelled as a state space, a set of states that a problem can be in. The set of states forms a graph where two states are connected if there is an operation that can be performed to transform the first state into the second. State space search often differs from traditional computer science search methods because the state space is implicit: the typical state space graph is much too large to generate and store in memory. [--> that is, this attacks needle in the haystack problems.] Instead, nodes are generated as they are explored, and typically discarded thereafter. A solution to a combinatorial search instance may consist of the goal state itself, or of a path from some initial state to the goal state.
So the material difference is that they went back to first principles and built a search concept based on exploring a space of configurational possibilities, as we may see from NFL and the reference to omega. Further, as we may see from the search for a search paper, they highlighted the needle in haystack search challenge:
Needle-in-the-haystack [search] problems look for small targets in large spaces. In such cases, blind search stands no hope of success. Conservation of information dictates any search technique [–> as in not specifically correlated to the structure of the space, i.e. a map of the targets] will work, on average, as well as blind search. Success requires an assisted [intelligently directed, well-informed] search. But whence the assistance required for a search to be successful? To pose the question this way suggests that successful searches do not emerge spontaneously but need themselves to be discovered via a search. The question then naturally arises whether such a higher-level “search for a search” is any easier than the original search. [–> where once search is taken as implying sample, searches take subsets so the set of possible searches is tantamount to the power set of the original set. For a set of cardinality n, the power set has cardinality 2^n.] We prove two results: (1) The Horizontal No Free Lunch Theorem, which shows that average relative performance of searches never exceeds unassisted or blind searches, and (2) The Vertical No Free Lunch Theorem, which shows that the difficulty of searching for a successful search increases exponentially with respect to the minimum allowable active information being sought.
That is, once configuration spaces are large enough, blind searches are practically speaking hopeless, i.e. maximally implausible as an effective means to find deeply isolated zones of interest; here, islands of function. Likewise, if searches are blindly applied without a matching of type of search to the "map" of the space in view, on average such a search will be just as ineffective. Where, as a simple view we may note that as searches are samples, they take subsets of the space, thus the space of possible searches is tantamount to the power set of the original configuration space. this implies that it is plausible that a search for a golden search will be exponentially harder than the original search challenge, as for a set of cardinality n the cardinality of the power set will be 2^n. Onward higher order searches will be again each exponentially harder in turn. So, what best explains finding FSCO/I in a config space for things of order 10^150 to 10^300+ possibilities? The origin of this comment (as well as any further comments including objections) is a clue: intelligently directed configuration. For, intelligence uses insight and imagination as well as its capability to move beyond mere information-processing computation on input and stored data, to give rise to novel, creative functional, composite, coherent, complex entities. In short, we are back to why the design inference on FSCO/I as sign is well-warranted i/l/o search challenge for direct blind search or searches that are blindly chosen. Where, the underlying point is that FSCO/I requires correct, properly oriented, aligned and coupled parts brought together in a coherently functional whole. Accordingly, the natural structure of relevant configuration spaces will have islands of function that are deeply isolated in large spaces mostly populated by non-functional gibberish. KF PS to AF: The 6500 fishing reel illustrates a concrete example of FSCO/I, which relates to the general pattern of such configuration-based function. Snide dismissiveness and sneering will not answer to the fact that FSCO/I is real, and that it is also deeply embedded in the world of life, including the metabolic reaction set [which I have often compared to a petroleum refinery] and the von Neumann kinematic self replication facility which has to be explained as foundational to self-replication of cells. PPS: And BTW, at least one case of a gear has been found in the world of life so one of the objectors will need to re-think the implications of design inference on gears s/he made. Especially as living systems do in fact embed vNSRs and a lot of other interesting components such as walking trucks in cells, NC machinery, string data structures, communication networks etc. Nor will trying to imply oh analogies are weak and can be dismissed work in the face of clear instantiation, not analogy. (Looks like I will need to go on to a first principles of reasoning discussion of the links between analogies and inductive reasoning; which happens to be foundational to science.)kairosfocus
February 3, 2018
February
02
Feb
3
03
2018
12:15 AM
12
12
15
AM
PDT
Interesting silence . . .kairosfocus
February 2, 2018
February
02
Feb
2
02
2018
11:47 PM
11
11
47
PM
PDT
AI, state/configuration space search and the ID search challengekairosfocus
February 2, 2018
February
02
Feb
2
02
2018
01:50 AM
1
01
50
AM
PDT