Mathematics desk
< August 8	<< Jul \| August \| Sep >>	Current desk >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

August 9[edit]

Alternative definition of "forest"[edit]

Can a forest be defined as a set X together with a partial function $p\colon X\rightarrow X$ such that $p^{n}(x)$ , if defined, is never equal to x for any positive integer n and any $x\in X$ ? GeoffreyT2000 (talk) 15:43, 9 August 2015 (UTC)[reply]

That would be something like a rooted forest. --JBL (talk) 16:00, 9 August 2015 (UTC)[reply]

I don't see how every forest can be described by such a partial function. Consider the graph with nodes {1,2,3,4} and edges {(1,2),(1,3),(1,4)}. What is your partial function for this tree? In other words, how can your definition work for a graph with a maximum degree greater than 2? -- ToE 14:26, 10 August 2015 (UTC)[reply]

There are four possible functions, corresponding to the four choices of a root node for the single connected component. One of them is the partial function {1→2, 3→1, 4→1}. --JBL (talk) 14:45, 10 August 2015 (UTC)[reply]

Thank you. I was looking at it backwards. -- ToE 14:53, 10 August 2015 (UTC)[reply]

Fuzzy logic, when you are using a digital computer[edit]

Moved from the computing desk, trying to get further explanations

Is it possible, or does it make sense to implement fuzzy logic using a digital computer? Whatever you do, nowadays you'll be getting digital information, which does not have infinite values, although you might want lots of intermediary values.

Either you have a digital sensor, or you have an analog sensor, and are converting the signal into a digital form. And you'll be encoding it in some binary form in your computer, that does not support infinite states.

Would an implementation of fuzzy logic in real life be any different than an implementation of other forms of many-valued logic? --YX-1000A (talk) 18:20, 9 August 2015 (UTC)[reply]

Digital doesn't mean just 0 or 1, unless you are only talking about a single bit. Using 10 bits, you can have 1024 values, so ranges of certainty from 0-100%, in approximately 0.1% increments. You can use more bits, as needed. 20 bits gives you over a million possible values, 30 gives over a billion, and 40 over a trillion. That may not be infinite, but it's close enough. Any analog device will only have a certain resolution of precision/accuracy, too, so they aren't "infinite" either. StuRat (talk) 18:29, 9 August 2015 (UTC)[reply]

Yes, but it leaves the question open, how is an implementation using fuzzy logic different from other form of logic that admits multiple values? For example, When developing an intelligent controller for braking you can consider temperatures, speeds, deceleration, which go into several decimal places.--YX-1000A (talk) 18:48, 9 August 2015 (UTC)[reply]

Well, some logic allows a small number of finite possibilities. For example, an automatic transmission on a car only has a few gears to choose from (typically 3-6). Fuzzy logic, on the other hand, can theoretically handle an infinite number of values (like a continuously variable transmission), although the digital approximation can have a very large number of values, but not infinite. StuRat (talk) 19:14, 10 August 2015 (UTC)[reply]

Just because something is represented digitally, doesn't mean that it's somehow less precise or less correct than analog value. All analog sensors have only finite accuracy - and you can almost always store numbers to higher precision inside a computer than any available sensor can measure them. For example, almost any computer can store and manipulate IEEE double precision floating point. These have about 16 significant digits of precision. One part in 10¹⁶ is better than almost all physical instruments. So it truly doesn't matter whether 'real world' data is analog or digital. That's a complete red-herring.

Fuzzy logic just means that the concept of 'true' and 'false' are replaced with a continuum of confidence spanning complete uncertainty to complete certainty. Doing that to a precision of one part in 10¹⁶ will be more than adequate for any likely application.

Bottom line - don't sweat it. Computers can do this stuff just fine. SteveBaker (talk) 19:42, 9 August 2015 (UTC)[reply]

But your "continuum" would be a set of finite values, so, what's "fuzzy" here? How is that different from a non-fuzzy approach? --YX-1000A (talk) 19:52, 9 August 2015 (UTC)[reply]

You may want to head over to the math desk with this question for better answers. There is not just the Truth value to be considered but the Formal system. The above naive arguments do not even hold for algebra, see: Numerical analysis.—eric 20:59, 9 August 2015 (UTC)[reply]

Adding information to the question:

The biggest issue for me is that any truth value is acceptable in fuzzy logic. That means, any real number can be a truth value. However, not all real numbers are representable on a digital computer. You can still have many truth-values for your expressions in a computer, but it certainly seems to me that there's a conflict here. --YX-1000A (talk) 21:44, 9 August 2015 (UTC)[reply]

That's not true, we don't use 0..infinity for our fuzzy false...true scale. Conventionally, 0.0 is utterly false and 1.0 is completely true - so only values between 0.0 and 1.0 are needed. But regardless, you might as well argue that you can't draw a circle of radius 100 on a computer because you'd need an irrational number of pixels or that you can't compute the path of a spacecraft because the value of the universal gravitational constant ('G') is unlikely to be a rational number when expressed in SI units. In the first case, you don't need a perfect circle in order to do what you need to do with it - and in the second case, nobody knows 'G' to more than 4 digits anyway so your spaceship will need a mid-course correction burn, no matter how many digits the computer carries around during the calculation.

The information you feed to your fuzzy logic algorithm won't have 10¹⁶ possible gradations of truthhood (except, perhaps for absolute falsehood and absolute truth - which can be expressed exactly in binary using the 0..1 scale) - and the answers you produce at the end won't be used for anything that requires 16 digits of precision in the conclusion. So it simply doesn't matter that we're only using an approximation of the calculation to produce an approximate answer based on approximate data - that's what computers do all the time for pretty much all kinds of calculations, and this truly astoundingly tiny imperfection doesn't reduce their usefulness to the slightest degree.

That is...unless their programmers are morons who do things like: { double x, y ; x = 1.0/5.0 ; y = x * 5.0 ; if ( y == 1.0 ) doSomethingImportant() ; }. This may or may not fail to doSomethingImportant because 0.2 is a repeating number in binary and it cannot be represented with sufficient precision to guarantee that 0.2x5.0 equals 1.0 exactly. But good programmers know these things and generally do not test for exact answers when using non-integer variables: if ( y <= TINY_THRESHOLD ) ... is what we'd use in this case.

SteveBaker (talk) 15:33, 10 August 2015 (UTC)[reply]

Real numbers themselves are just models. No one has ever exhibited a real number, to infinite precision, in either a digital or an analog setting. For all we know, the universe has only a large but finite number of admissible states, so real numbers are themselves only idealizations. If you insist on an overly literal interpretation of the fuzziness in fuzzy logic that excludes digital computers by design, then you also excluding any reasonable analog realizations as well. Now there are intuitionistic models of the continuum, that can be (and are) implemented in intuitionistic type systems like Coq. I don't know enough about fuzzy logic to say whether these systems support it, but I don't find the objection that continua cannot exist in a finite state machine to be terribly persuasive. Sławomir
Biały 21:35, 9 August 2015 (UTC)[reply]

Consider a real-life application - the IBM 'Watson' computer that won the Jeopardy! game show against the two best human players in the world. It used (in part) fuzzy logic - it assessed the relative validity and reliability of dozens to hundreds of documents (some from right here on Wikipedia) that related to the question and used fuzzy logic to combine the significance of those results into an ordered list of confidence values. It would then pick the response with the highest confidence level - and if it exceeded some threshold, pressed the buzzer to answer the question. It did this with perfectly normal digital circuits. Sure, the precision of it's estimates were not absolutely perfect - but you hardly needed the results to be expressed as a probability with more than 16 digits of precision in this kind of application.

The outcome and practicality of fuzzy logic doesn't have to be free of tiny digital artifacts - certainly no more than in any other computer-based calculation. You could use the same argument to argue that image processing, neural networks, weather prediction, self-driving cars cannot be implemented in computers. There is absolutely nothing special about fuzzy logic algorithms that makes them even the slightest bit difficult to implement and usefully use in digital computers with far less precision than the 16 digits you get in IEEE double-precision floating point. It's common to find fuzzy logic built very successfully on tiny 8 bit microcontrollers with just two and a half decimal digits of precision.

SteveBaker (talk) 04:14, 10 August 2015 (UTC)[reply]

Put another way, if Jeopardy! asks "Queen Victoria's news from Dorset Street, London" - and Watson finds both "Where was the computer invented? - 50.000000000001%" and "Where was Mary Jane Kelly murdered? - 49.9999999999999%" - then it probably shouldn't press the buzzer - it doesn't really matter that the true result should be 50% and 50%. SteveBaker (talk) 15:47, 10 August 2015 (UTC)[reply]