Please use this identifier to cite or link to this item: https://doi.org/10.1006/inco.1995.1133
Title: Finite Identification of Functions by Teams with Success Ratio 1 2 and Above
Authors: Jain, S. 
Sharma, A.
Velauthapillai, M.
Issue Date: Sep-1995
Citation: Jain, S., Sharma, A., Velauthapillai, M. (1995-09). Finite Identification of Functions by Teams with Success Ratio 1 2 and Above. Information and Computation 121 (2) : 201-213. ScholarBank@NUS Repository. https://doi.org/10.1006/inco.1995.1133
Abstract: Consider a scenario in which an algorithmic machine, M, is being fed the graph of a computable function f{hook}. M is said to finitely identify f{hook} just in case, after inspecting a finite portion of the graph of f{hook}, it emits its first conjecture, which is a program for f{hook}, and it never abandons this conjecture thereafter. A team of machines is a multiset of such machines. A team is said to be successful just in case each member of some nonempty subset, of predetermined size, of the team is successful, The ratio of the number of machines required to be successful to the size of the team is referred to as the success ratio of the team. The present paper investigates the finite identification of computable functions by teams of learning machines. The results presented complete the picture for teams with success ratio 1 2 and greater. It is shown that at success ratio 1 2, introducing redundancy in the team can result in increased learning power. In particular, it is established that larger collections of functions can be learned by employing teams of 4 machines and requiring at least 2 to be successful than by employing teams of 2 machines and requiring at least 1 to be successful. Surprisingly, it is also shown that introducing further redundancy at success ratio 1 2 does not yield any extra learning power. In particular, it is shown that the collections of functions that can be finitely identified by a team of 2m machines requiring at least m to be successful is the same as: • the collections of functions that can be finitely identified by a team of 4 machines requiring at least 2 to be successful, if is even, and • the collections of functions that can be identified by a team of 2 machines requiring at least 1 to be successful, if is odd. These latter results require development of sophisticated simulation techniques. © 1995 Academic Press. All rights reserved.
Source Title: Information and Computation
URI: http://scholarbank.nus.edu.sg/handle/10635/99293
ISSN: 08905401
DOI: 10.1006/inco.1995.1133
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

5
checked on Oct 23, 2018

WEB OF SCIENCETM
Citations

4
checked on Oct 23, 2018

Page view(s)

29
checked on Oct 19, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.