首页    期刊浏览 2025年07月11日 星期五
登录注册

文章基本信息

  • 标题:How Many Bits Can a Flock of Birds Compute?
  • 本地全文:下载
  • 作者:Bernard Chazelle
  • 期刊名称:Theory of Computing
  • 印刷版ISSN:1557-2862
  • 电子版ISSN:1557-2862
  • 出版年度:2014
  • 卷号:10
  • 页码:421-451
  • 出版社:University of Chicago
  • 摘要:We derive a tight bound on the time it takes for a flock of birds to reach equilibrium in a standard model. Birds navigate by constantly averaging their velocities with those of their neighbors within a fixed distance. It is known that the system converges after a number of steps no greater than a tower-of-twos of height logarithmic in the number of birds. We show that this astronomical bound is actually tight in the worst case. We do so by viewing the bird flock as a distributed computing device and deriving a sharp estimate on the growth of its busy-beaver function. The proof highlights the use of spectral techniques in natural algorithms
  • 关键词:natural algorithms; dynamical systems; bird flocking; busy-beaver function
国家哲学社会科学文献中心版权所有