The basic problem of feedback coding is vividly described by Rényi [23, p. 47] as a problem of fault-tolerant adaptive search with errors, as follows: […] I made up the following version, which I called “Bar-kochba with lies”. Assume that the number of questions which can be asked to figure out the “something” being thought of is fixed and the one who answers is allowed to lie a certain number of times. The questioner, of course, doesn’t know which answer is true and which is not. Moreover the one answering is not required to lie as many times as is allowed. For example, when only two things can be thought of and only one lie is allowed, then 3 questions are needed […] If there are four things to choose from and one lie is allowed, then five questions are needed. If two or more lies are allowed, then the calculation of the minimum number of questions is quite complicated […] It does seem to be a very profound problem […]
Recent developments of feedback coding, and its relations with many-valued logic
CICALESE, Ferdinando;
2011-01-01
Abstract
The basic problem of feedback coding is vividly described by Rényi [23, p. 47] as a problem of fault-tolerant adaptive search with errors, as follows: […] I made up the following version, which I called “Bar-kochba with lies”. Assume that the number of questions which can be asked to figure out the “something” being thought of is fixed and the one who answers is allowed to lie a certain number of times. The questioner, of course, doesn’t know which answer is true and which is not. Moreover the one answering is not required to lie as many times as is allowed. For example, when only two things can be thought of and only one lie is allowed, then 3 questions are needed […] If there are four things to choose from and one lie is allowed, then five questions are needed. If two or more lies are allowed, then the calculation of the minimum number of questions is quite complicated […] It does seem to be a very profound problem […]I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.