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

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

N/A
N/A
Protected

Academic year: 2021

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

Copied!
1
0
0

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

全文

(1)

I222

計算の理論

(Theory of Computation) Report (2)

2007

年度

II-1

(10,11

月) 担当: 上原 隆平

([email protected])

出題

(Propose): 10

16

(火) (October 16 (Tue))

提出

(Deadline): 10

19

(金)

講義終了時

(October 19 (Fri), 10:50)

注意

(Note):

レポートには氏名,学生番号,問題,解答を,すべて手書きで書くこと.(Do not forget to

handwrite your name, student ID, problems, and answers on your report.)

Problem 1 (3 points):

素数を小さい順に並べて,

i

番目の素数を

p

iとする.つまり

p

1

= 2, p

2

= 3, p

3

= 5, p

4

= 7, p

5

= 11, . . .

となる.よく知られた事実として,素数は有限個ではなく,無限個ある.以 上のことから,素数の集合の濃度は可算無限であり,半帰納的である.したがって定理

3.2

に示した 通り,RAN GE(g)が素数の集合に一致するような計算可能関数

g

が存在する.関数

g

を計算するプ ログラム

G

の概要を書け.(We denote the

ith prime by p

i

. That is, we have p

1

= 2, p

2

= 3, p

3

= 5, p

4

= 7, p

5

= 11, . . .. It is well known there are infinite primes. Thus, the cardinality of the set of primes is uncountable, and hence semi-recursive. Therefore, by Theorem 3.2, there is a function g such that RAN GE(g) is equal to the set of primes. Describe the outline of the program G that computes the function g.)

Problem 2 (2 points):

自然数の集合を

N

とし,

N

の部分集合全体からなる集合を

2

Nとする.このとき

2

Nは非可算無限であることを対角線論法を使って示せ.(Let

N denote the set of natural numbers.

Then the set 2

N

consists of all subsets of N . Now, prove that 2

N

is an uncountable infinity set by diagonalization.)

Hint:

例えば集合

S = { 1, 2, 3 }

に対しては

2

S

= { φ, { 1 } , { 2 } , { 3 } , { 1, 2 } , { 2, 3 } , { 1, 3 } , { 1, 2, 3 }}

なる.(For example, for set

S = { 1, 2, 3 } , 2

S

= { φ, { 1 } , { 2 } , { 3 } , { 1, 2 } , { 2, 3 } , { 1, 3 } , { 1, 2, 3 }} .)

参照

関連したドキュメント

Therefore, with the weak form of the positive mass theorem, the strict inequality of Theorem 2 is satisfied by locally conformally flat manifolds and by manifolds of dimensions 3, 4

This paper is a sequel to [1] where the existence of homoclinic solutions was proved for a family of singular Hamiltonian systems which were subjected to almost periodic forcing...

R.Brown and J-L.Loday [5] noted that if the second dimension G 2 of a simplicial group G, is generated by the degenerate elements, that is, elements coming from lower dimensions,

Recently, Arino and Pituk [1] considered a very general equation with finite delay along the same lines, asking only a type of global Lipschitz condition, and used fixed point theory

In analogy with Aubin’s theorem for manifolds with quasi-positive Ricci curvature one can use the Ricci flow to show that any manifold with quasi-positive scalar curvature or

Indeed, in order to conclude from Gromov’s Theorem that G has a nilpotent subgroup of finite index, it suffices to know that G has a connected Cayley graph of finite valency that

the log scheme obtained by equipping the diagonal divisor X ⊆ X 2 (which is the restriction of the (1-)morphism M g,[r]+1 → M g,[r]+2 obtained by gluing the tautological family

Therefore, there is no control on the growth of the third modified energy E (3) and thus Theorem 1.8 with the second modified energy E (2) is the best global well-posedness result