プログラムの等価性を半決定する関数についての考察

• Item type: Trans(1)
• 公開日: 2006-10-15
• タイトル: プログラムの等価性を半決定する関数についての考察
• タイトル / 言語: en
• タイトル: Considerations for Partial Recursive Functions Which Semidecide Equality between Programs
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 発表概要
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 産業技術総合研究所
• 著者所属(英): en
• 著者所属(英): Information Technology Research Institute, AIST
• 著者名: 海老原, 一郎
• 著者名(英): Ichirou, Ebihara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本発表では，任意の関数についてそれぞれ，その関数と等価な関数を計算可能な最大の範囲で半決定する手続きが存在することを示す．そういう手続きには，等価な関数を認識する範囲に原理的な限界が存在することも示す．また，関数の同値類への帰属問題が，上への1対1写像により，任意の別の関数の別の同値類への帰属問題と同型になることも示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this presentation it is shown that there are respective procedures which semidecide equality between a fixed function and other functions to the limit of computability, and that there is a theoretical limit for such kind of procedures. It is also shown that a problem to determine whether a function belongs to an equivalence class of functions is isomorphic to a problem to determine whether another function belongs to another equivalence class of functions.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 47, 号 SIG16(PRO31), p. 90-90, 発行日 2006-10-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会