記念特集 2-2-2 計算限界の頂(いただき)を目指して──チューリングからコンプへ──

電子情報通信学会 - IEICE会誌 試し読みサイト
Vol.100 No.10 (2017/10) 目次へ

前の記事へ次の記事へ


fig_2.png

富田悦次 正員:フェロー 電気通信大学先進アルゴリズム研究ステーション

Etsuji TOMITA, Fellow (The Advanced Algorithms Research Laboratory, The University of Electro-Communications, Chofu-shi, 182-8585 Japan).

電子情報通信学会誌 Vol.100 No.10 p.1046 2017年10月

©電子情報通信学会2017

1.は じ め に

 近代“コンピュテーション”の元祖はチューリング(Alan Turing)であり,2012年にはチューリング生誕100年,本年はチューリング賞の50周年記念の年でもある.コンピュータの最も基本的な形がチューリング機械であり,コンピュテーション研究会では正にその発展形の上に立って直接的に関与した基礎研究を活発に行い,情報化社会の理論的基盤を支えている.

2.オートマトンと自動制御研専,オートマトン

研専,オートマトンと言語研専

 本会では,1954年に「自動制御研専」が発足して活動が続けられていたが,この間,1956年にはプリンストン大学出版局から「Automata Studies」が出版され,当研究分野の活発な活動の原動力となっていた.

 これらの影響も受け,前研究会は1958年に「オートマトンと自動制御研専」へと衣替えされ,名実共に「コンピュテーション研究会」の直接的前身となる研究会がスタートした.1963年には電気通信学会雑誌11月号がオートマトン特集号として出版されている.IEEEにおいては,1966年にAnnual Symposium on Switching and Automata Theory(SWAT)がスタートした.この流れを受け,前記研究会は1967年に「オートマトン研専」へと名称が集約された.更に,1972年には「オートマトン研専」と「インフォメーション理論研専」を改組して,「オートマトンと言語研専」へと発展した.

3.コンピュテーション研専の発足

 上記研究会における中心テーマは文字どおりオートマトン/言語理論であったが,次第にアルゴリズム,計算量の解明等へと研究の幅を広げていった.IEEEでは1975年にSWATをAnnual Symposium on Foundations of Computer Science(FOCS)へと改称して新出発した.同年には,理論計算機科学の主要論文誌であるTheoretical Computer Science(TCS)も発刊された.これらの進展に合わせ,前記研究会は1986年に「コンピュテーション研専」へと改称され,今日に至っている.

 この間1989年には,戸田誠之助の論文(1)が,理論計機科学における最高の賞であるゲーデル賞受賞に輝いた.また,TCS誌は2015年に創刊40周年を迎え,TCSの各年出版論文における被引用最多論文が選出されたが(2),その中に日本人著者を含む3論文が入っている.

 最近においても,次の大型プロジェクトが実施された:今井量子計算,湊離散構造処理系,河原林巨大グラフの各ERATOプロジェクト,幾つかのCRESTプロジェクト,及び,科研の「特定領域」,「新学術領域」研究,など.これら関連研究の多くが本研究会において発表され,研究会は精力的に発展している.

 なお,情報処理学会アルゴリズム研究会,LAシンポジウムとは相互協力をしている.国際的には,ISAAC,ALT,AAACやWALCOMなどとも協力関係を持っている.

文     献

(1) S. Toda, “PP is as hard as the polynomial-time hierarchy,” SIAM J. Comput., vol.20, pp.865-877, 1991.

(2) https://www.journals.elsevier.com/theoretical-computer-science/virtual-special-issues/40th-anniversary-of-theoretical-computer-science/

(平成29年4月29日受付)

images/fig_1.png

(とみ)() (えつ)() (正員:フェロー)

 昭41東工大・電子卒.昭46同大学院博士課程了.工博.同年東工大助手等を経て,電通大教授.平20同名誉教授.理論計算機科学とその応用の研究に従事.平15船井情報科学振興賞,2010 TCS Top Cited Article 2005-2010等受賞.著書「オートマトン・言語理論」(森北出版)等.


続きを読みたい方は、以下のリンクより電子情報通信学会の学会誌の購読もしくは学会に入会登録することで読めるようになります。 また、会員になると豊富な豪華特典が付いてきます。


続きを読む(PDF)   バックナンバーを購入する    入会登録


  

電子情報通信学会 - IEICE会誌はモバイルでお読みいただけます。

電子情報通信学会誌 会誌アプリのお知らせ

電子情報通信学会 - IEICE会誌アプリをダウンロード

  Google Play で手に入れよう

本サイトでは会誌記事の一部を試し読み用として提供しています。