• 検索結果がありません。

I222 計算の理論 (Theory of Computation) Report (3)

N/A
N/A
Info
ダウンロード
Protected

Academic year: 2021

シェア "I222 計算の理論 (Theory of Computation) Report (3)"

Copied!
1
0
0

読み込み中.... (全文を見る)

今ダウンロードする ( 1 ページ )

全文

(1)

I222

計算の理論

(Theory of Computation) Report (3)

2007

年度

II-1

期

(10,11

月) 担当: 上原 隆平

([email protected])

出題

(Propose): 10

月

23

日

(火) (October 23 (Tue))

提出

(Deadline): 10

月

26

日

(金)

講義終了時

(October 26 (Fri), 10:50)

注意

(Note):

レポートには氏名，学生番号，問題番号，解答を，すべて手書きで書くこと．

(Do not forget to handwrite your name, student ID, problem numbers, and answers on your report.)

Problem 1 (3 points):

クラス

co- RE

とは，co-

RE = { L | Lが枚挙可能 ¯ }

と定義される集合のクラス であった．“適当な計算可能述語

R

が存在して，L

= { x | ∀ w ∈ Σ

∗

[R(x, w)] }

と表現できる” 集 合

L

のクラスを

C

とする．このとき

co- RE = C

であることを証明せよ．(co-

RE denotes the class defined by co- RE = { L | L ¯ is enumerable } . Let C be a class defined by the set of sets L such that L = { x | ∀ w ∈ Σ

∗

[R(x, w)] } for some computable predicate R. Then, prove co- RE = C .)

Hint:定理 3.5

をよく考えよう．(Concider Theorem 3.5 carefully.)

Problem 2 (2 points): HALT ∈ REC

ならば，REC

= RE

が成立することを証明せよ．(Prove

REC = RE under the assumtion that HALT ∈ REC .)

Note:

実際には

HALT 6∈ REC

が成立する．(Actually, we have HALT

6∈ REC .)

参照

今ダウンロードする ( PDF - 1 ページ - 24.75 KB )

関連したドキュメント

実函数の計算理論

チューリング機械の原論文 [14]

計算の理論

As soon as an Analytic Engine exists, it will necessarily guide the future course of the

実函数の計算理論

Lipschitz continuous ordinary differential equations are polynomial-space complete.. A computable ordinary differential equation which possesses no

2. On the Computation of the Efficient Frontier

An easy-to-use procedure is presented for improving the ε-constraint method for computing the efficient frontier of the portfolio selection problem endowed with additional cardinality

第１章　積算基準

⑥ニューマチックケーソン 職種 設計計画 設計計算 設計図 数量計算 照査 報告書作成 合計.. 設計計画 設計計算 設計図 数量計算

神谷 徳昭(Noriaki Kamiya) 会津大学 (U

小林 英恒 (Hidetsune Kobayashi) 計算論理研究所 (Inst. Computational Logic) 小野 陽子 (Yoko Ono) 横浜市立大学 (Yokohama City.. Structures and Their

数理解析研究所 2011

 当図書室は、専門図書館として数学、応用数学、計算機科学、理論物理学の分野の文

計算の理論

Whenever any result is sought by its aid, the question will arise—By what course of calculation can these results be arrived at by the machine in the shortest time. — Charles