トップページ⇒tech
111コメント36KB

ループの中毒性

■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさん2007/02/12(月) 20:54:08

ループは便利だが使い方を誤ると大変な中毒性をもたらすことが明らかになった。

参考動画
http://www.nicovideo.jp/watch/utJS0CxKuocsE

とかちつくちて！
0002デフォルトの名無しさん2007/02/12(月) 21:01:25
自己解決しました
0003デフォルトの名無しさん2007/02/12(月) 21:03:03
何この永久ループ
0004デフォルトの名無しさん2007/02/12(月) 22:34:31
やべぇ…はまったｗｗｗｗ
0005デフォルトの名無しさん2007/02/12(月) 23:35:16
♪もっと 高めて果てなく 心の奥まで
貴方だけが使える テクニックで
とかちつくちてwwwwwwwwwwwwwwwww
0006デフォルトの名無しさん2007/02/13(火) 03:25:38
糞スレage
0007デフォルトの名無しさん2007/02/13(火) 05:16:07
ニコニコビデオはＮＧリスト登録決定・・・
0008デフォルトの名無しさん2007/02/13(火) 15:10:27
さいごのもにゃ妻って元の歌詞はなんだ…
0009デフォルトの名無しさん2007/02/13(火) 16:31:39
ゲシュタルト崩壊ってこんな感じか。。。
0010デフォルトの名無しさん2007/02/13(火) 19:52:37
映像とコメントがなくてもいける猛者へｗ
ttp://www.geocities.jp/klimlq/idol_tokachi.mp3
0011デフォルトの名無しさん2007/02/13(火) 20:07:07
#include <stdio.h>

main () {
int i;
for(i = 0; ; ) {
printf("%d\n", i);
i++;
}
return 0;
}
これをコンパイルして実行してみろ中毒なるぞ
0012デフォルトの名無しさん2007/02/13(火) 21:01:22
#include <stdio.h>

main () {
char i[] = "お前はキモオタ" ;
for(; ;){
printf("%s\n", i);
}
return 0;
}
0013デフォルトの名無しさん2007/02/13(火) 21:23:31
#include<iostream>
int main()
{
　　while(1)
　　{
　　　　std::cout << "nurupo" << std::endl;
　　}
　　return 0;
}
0014デフォルトの名無しさん2007/02/14(水) 00:12:47
>>12
きもいコード
0015デフォルトの名無しさん2007/02/17(土) 00:55:11
hehehe
0016デフォルトの名無しさん2007/02/17(土) 03:29:55
板違いにもかかわらずスレタイだけで>>1の内容を推測できてしまった
0017デフォルトの名無しさん2007/02/17(土) 12:11:36
(while t
(dolist (c '(33478 33449 33471 33474 33453 33471 33476 10))
(princ (code-char c))
(sit-for 0.03)))
0018デフォルトの名無しさん2007/02/20(火) 21:04:38
俺はてっきり

goto >>1

と書いていくスレかと思っていたのだが
0019デフォルトの名無しさん2007/02/21(水) 22:58:39
goto >>1
0020デフォルトの名無しさん2007/02/21(水) 23:04:16
gosub >>50
0021デフォルトの名無しさん2007/02/21(水) 23:40:23
十勝はこちらべぇ

とかちつくちて
http://game12.2ch.net/test/read.cgi/gal/1171269751/
0022デフォルトの名無しさん2007/02/22(木) 03:36:16
sleep or die
0023デフォルトの名無しさん2007/03/03(土) 21:48:46
>>1
現在ご利用いただけません
0024デフォルトの名無しさん2007/04/23(月) 19:54:36
無限ループって怖くね？
だって同じことが繰り返されるんだぜ？
0025デフォルトの名無しさん2007/07/21(土) 20:17:14
ほんとに怖いね
抜け出るには誰かが不正メモリアクセスして値が変わるか
管理者にkillコマンドで殺されるか
電源ＯＦＦされて世界自体が終わってしまうか
他力を当てにしないとずっと同じことの繰り返しなんだぜ
案外、人ってのは自力でなんとかなるとか思ってんだろうけど、
決められた運命（ソースコード）に沿ってexitまで道のりをひたすら歩いていくだけ
0026デフォルトの名無しさん2007/07/21(土) 21:32:54
宇宙の真理を発見した気がする
0027デフォルトの名無しさん2007/07/21(土) 22:15:13
宇宙のﾏﾘｰを発見した気もする
0028デフォルトの名無しさん2007/07/22(日) 02:30:40
誰だよｗ
0029デフォルトの名無しさん2007/07/22(日) 02:49:01
俺俺、俺だよ俺。
0030デフォルトの名無しさん2007/07/22(日) 07:35:48
無限ループを検出するプログラムを作ると、無限ループに陥るらしいね（豆知識）
0031デフォルトの名無しさん2007/07/22(日) 08:49:15
はあ？
普通に線形時間で終わるだろ。
0032デフォルトの名無しさん2007/07/22(日) 08:55:43
>>31
ラベルじゃなくアドレス変数でjmpするかもしれないし、
プログラムが自己書き換えかもしれないじゃない。
0033322007/07/22(日) 08:58:36
と、ここまで書いて思ったが、
ハーバードアーキテクチャだと停止判定できるのかな？
0034デフォルトの名無しさん2007/07/22(日) 09:30:31
>>31
チューリングマシンの停止問題
0035デフォルトの名無しさん2007/07/22(日) 09:34:18
ループが止まらなかったら人が目視して
「あ、無限ループになってる・・・」で手直しすればＯＫ
チューリングマシンはアホだから自分が何をやってるのかもわかってない。
全てのプログラミング言語はチューリング等価ということは
みんなアホってこと。
0036デフォルトの名無しさん2007/07/22(日) 09:44:21
なんでもかんでもチューリング例に持ち出すアホってまだいたんだな
0037デフォルトの名無しさん2007/07/22(日) 09:45:57
任意のプログラムxに対して、無限ループするかどうかを
確実に検出するプログラムPが存在すると仮定する。
Pを用いて、次のようなプログラムP'を構成する：
P'は、入力xに対してPを用いて判定し、
(1) xが無限ループするなら停止し、
(2) xが無限ループにならないならわざと無限ループする

さあ、P'の入力として、P'自身を判定させてみよう！
上記のxにP'を代入すると、
(1) P'が無限ループするなら（P'は）停止し、
(2) P'が無限ループにならないなら（P'は）わざと無限ループする

言ってることが完全に矛盾しているので、最初の仮定は誤り。
よって、任意のプログラムに対して、無限ループするかどうかを
確実に検出するプログラムは存在しない。

という証明をこのまえ学校で習いました。
0038デフォルトの名無しさん2007/07/22(日) 09:48:42
では、その学校の教育が間違っていない事を証明せよ
0039デフォルトの名無しさん2007/07/22(日) 09:51:37
>>37みたいな証明って嫌い
確かに正しいんだろうけど、なんかイライラする
なに一人で言ってんだって感じ
だから論理学は嫌いだった。
0040デフォルトの名無しさん2007/07/22(日) 09:55:38
なにが嫌っていうと

>P'は、入力xに対してPを用いて判定し、
>(1) xが無限ループするなら停止し、
>(2) xが無限ループにならないならわざと無限ループする

これがすげー嫌い
0041デフォルトの名無しさん2007/07/22(日) 09:57:49
「私はウソをついている」

みたいな問題？
0042デフォルトの名無しさん2007/07/22(日) 10:12:58
任意のプログラムxに対して、プログラムサイズを「確実に正しく」計算
するプログラムPが存在すると仮定する。
Pを用いて、次のようなプログラムP'を構成する：
P'は、入力xに対してPを用いて計算し、
(1) xが空プログラムなら100KBを返し、
(2) xが空プログラムでならないなら0KBを返す

さあ、P'の入力として、P'自身を判定させてみよう！
上記のxにP'を代入すると、
(1) P'は空プログラムではないのに0KBが返される

言ってることが完全に矛盾しているので、最初の仮定は誤り。
よって、任意のプログラムに対して、プログラムサイズを「確実に正しく」計算
するプログラムは存在しない。



んな、馬鹿なorz
0043デフォルトの名無しさん2007/07/22(日) 10:19:32
>>37
Pが「無限ループするかどうかを確実に検出する」んだから
P'が無限ループするかどうかは判定できるじゃん。
>P'自身を判定させてみよう
言うまでも無く判定できる。
意味があるのはここまで。

問題はその後の文、
「言ってることが完全に矛盾しているので、」
この言葉がどこに掛かるのか不明。
つまり問題が矛盾してるという認識を行った時点で、
問題の作り方から間違ってるのだから、何も証明したことにはならず、
単に駄文を晒してるだけ。
0044デフォルトの名無しさん2007/07/22(日) 10:23:25
ごめん、
つまり問題作成者がアホってことね
0045デフォルトの名無しさん2007/07/22(日) 10:38:34
>>42
P'がファイルサイズを返さなきゃいけない理由がない

>>43
P'が無限ループしないならP'は無限ループ（矛盾）
0046デフォルトの名無しさん2007/07/22(日) 10:43:13
そもそも問題の条件だと何も食わせていないP'の振る舞いが未定義なので
P'(a)そのものに食わせるP'(b)が無限ループするか否かは不定
0047デフォルトの名無しさん2007/07/22(日) 10:44:22
>>45
P'は無限ループする、しない、に関わらず判定はできる。
どこにも矛盾はない。

一見パラドクス問題にも見えなくもないが、
実体は単なる作成者自身が問いをきちんと掌握できずに
放出した失敗オナニー。
0048デフォルトの名無しさん2007/07/22(日) 10:47:20
37の学校はヤバイな
0049デフォルトの名無しさん2007/07/22(日) 10:47:27
>>46
P'の定義なら、このように書いてある
>P'は、入力xに対してPを用いて判定し、
>(1) xが無限ループするなら停止し、
>(2) xが無限ループにならないならわざと無限ループする

>>47
P'は判定するプログラムではなく、定義の通りに振舞うだけのプログラム
判定をしているのは、存在を仮定したP
0050デフォルトの名無しさん2007/07/22(日) 10:50:09
P'はPに関係なく何でもできるから・・・・？
・・？
P'がこうだからこうだとかは全く意味ないってこと？
0051デフォルトの名無しさん2007/07/22(日) 10:51:57
Pの存在を仮定すれば、P'のようなプログラムをでっちあげることが可能
0052デフォルトの名無しさん2007/07/22(日) 10:52:38
>>49
>言ってることが完全に矛盾しているので、最初の仮定は誤り。

だからさー、これが全く論法になってないんだよ。
別に矛盾してないんだから。
AだからB、と言いたいんだろうけど、だったら
「言ってること」が何なのか説明してくれ。
0053デフォルトの名無しさん2007/07/22(日) 10:54:24
>>52
「言ってること」＝「(2) P'が無限ループにならないなら（P'は）わざと無限ループする」
0054デフォルトの名無しさん2007/07/22(日) 10:56:37
でっちあげられたＰ’がうんぬんってイライラする・・・
夢の国へようこそ臭がする
0055デフォルトの名無しさん2007/07/22(日) 10:58:04
P'(x)が無限ループするかってのはxに依存するわけでしょ
なら
>P'の入力として、P'自身を判定
を表すP'( P'(x) )のxは何になるのって話
P(x)もP'(x)も入力があることが前提で判断を行うんだから
P'( P' )みたいなものはありえないでしょ？

って頭の固い俺は考えてしまうんだけど
0056デフォルトの名無しさん2007/07/22(日) 10:58:07
仮定→でっちあげ→結果は言ってることがむちゃくちゃでした→仮定がおかしい
0057デフォルトの名無しさん2007/07/22(日) 11:00:34
P: P(x)
P': P'(P(x))

x = P'で
P'(P(P'))はありうるでしょ
0058デフォルトの名無しさん2007/07/22(日) 11:01:14
>>53
P'はPが含まれるんだから(1)(2)のことは当然知ってるわけで、
P'(P'(x)))に矛盾する所は何もないが。
0059デフォルトの名無しさん2007/07/22(日) 11:03:12
>>55,58
P'(P'(x))じゃなくてP'(P')

>>56
仮定⇒でっちあげが「可能」⇒これこれの入力を与えることが「可能」⇒論理的に「不可能」であることと矛盾
006046=552007/07/22(日) 11:04:56
P'の返す結果は入力がある条件でのみ定義されているから一番中にいるP'が返す結果は未定義
よってその外のPの返す結果もその外のP'が返す結果も未定義になるんじゃないの？
0061デフォルトの名無しさん2007/07/22(日) 11:07:07
>>60
P'(P')の中にあるほうのP'は、実行せずにプログラムそのものを入力として渡すということ
0062デフォルトの名無しさん2007/07/22(日) 11:07:54
>  (1) xが無限ループするなら停止し、
>  (2) xが無限ループにならないならわざと無限ループする
ここが x(x) の間違いなんじゃないの
0063デフォルトの名無しさん2007/07/22(日) 11:10:05
証明において「実行」うんたら〜とか言ってたら先生に怒られた
0064デフォルトの名無しさん2007/07/22(日) 11:13:47
任意のプログラムxに対して、無限ループするかどうかを
確実に検出するプログラムPが存在すると仮定する

→P(x)が存在すると仮定

これはいいとして、


Pを用いて、次のようなプログラムP'を構成する：
P'は、入力xに対してPを用いて判定し････

→P'(x)
なんだよな。

なんかP'(P(x))って考えてしまう
定義と処理をごっちゃ混ぜにしてしまってる？
0065デフォルトの名無しさん2007/07/22(日) 11:15:27
わからんなぁ
動的にしか決まらない値を静的に判定が可能という仮定に対する矛盾ってこと？
0066デフォルトの名無しさん2007/07/22(日) 11:16:13
>>59
P'(P')でも別に矛盾はない。
Pの解が一度に2通り出るというだけで、
後はP'がその結果からどう振舞うかというだけの話。
0067デフォルトの名無しさん2007/07/22(日) 11:20:09
>>62
任意の入力に対して停止するかどうかを判定するのに
どちらの場合も確実に停止するPを仮定してるから大丈夫

>>65
「静的に判定」とは？

>>66
Pの解が一度に2通り出ることはありません
0068デフォルトの名無しさん2007/07/22(日) 11:21:52
>>64
P(x)が存在すると仮定してるんじゃなくて、
「任意のx」に対してxが無限ループすることがあるかないかを判定する
Pが存在することを仮定している
0069デフォルトの名無しさん2007/07/22(日) 11:28:08
Pの性質として任意のxに対してxが無限ループする事があるか無いかを判定する
ことに対してxは一意に決まっている必要ってある？それともない？
0070デフォルトの名無しさん2007/07/22(日) 11:28:51
>>67
後付けでありませんて言われてもなあ。
問題にそういう断りがないんだから別にいいだろ。
どっちにしろ>>37の
「無限ループするかどうかを確実に検出する」
ことには変わりないんだし。
0071デフォルトの名無しさん2007/07/22(日) 11:31:47
文章で説明するから曖昧になるんだよ
数式で説明しようぜ

俺は存在記号とかよくわからんけど
0072デフォルトの名無しさん2007/07/22(日) 11:34:19
>>69
ごめん、「xは一意に決まっている」の意味がよくわからない
Pがxを判定している途中に、xが外部の影響か何かを受けて
変化することがあるかどうかってこと？
さすがにそんな可能性は考えてなかったな

>>70
後付けだと感じたなら申し訳なかったが、「判定」できると言って
いるのに「どちらかわからない」なんて答えは普通想定しないかと
0073622007/07/22(日) 11:34:29
>>67
> 任意の入力に対して停止するかどうかを判定するのに
> どちらの場合も確実に停止するPを仮定してるから大丈夫
それが >>62 とどう関係するの？
0074622007/07/22(日) 11:40:50
数式で書いてみたよ
最初の P が受け取る x は引数をとらないと解釈した。
↓ が「停止する」ね。
どこが矛盾？

> 任意のプログラムxに対して、無限ループするかどうかを
> 確実に検出するプログラムPが存在すると仮定する。

∃P.∀x. (x↓ ⇔ P(x)↓true)

> Pを用いて、次のようなプログラムP'を構成する：
> P'は、入力xに対してPを用いて判定し、
> (1) xが無限ループするなら停止し、
> (2) xが無限ループにならないならわざと無限ループする

∃P'.∀x. (x↓ ⇔ ¬(P'(x)↓))

> さあ、P'の入力として、P'自身を判定させてみよう！
> 上記のxにP'を代入すると、

代入すると
P'↓ ⇔ ¬(P'(P')↓)
0075デフォルトの名無しさん2007/07/22(日) 11:43:57
>>72
どっちかわからん、とかいう糞味噌な理由じゃなくて、
ある条件の下で2通り解が出るというだけ。
複数解だとしても、それが無限ループかどうかを判定する
検出の妨げにはならない。
解が常に一意である、なんて主張を後から通すなんて
単なるわがまま。
0076622007/07/22(日) 11:45:04
ごめん一個目の式まちがえた
× ∃P.∀x. (x↓ ⇔ P(x)↓true)
○ ∃P.∀x. ((x↓ ⇒ P(x)↓true) ∧ (¬(x↓) ⇒ P(x)↓false))
0077デフォルトの名無しさん2007/07/22(日) 11:45:33
>>73-74
何かすごいことになってる・・・
まだよく読んでないけど、67はxが任意の入力に対して停止するかどうか
というつもりで書いた
0078622007/07/22(日) 11:49:05
>>77
x って、P'に食わせる x のこと？
0079デフォルトの名無しさん2007/07/22(日) 11:53:02
>>75
停止問題の話をしてるんだから、そんな変な状況は想定しないでしょ
P(x)というのは、xがいかなる条件に対しても必ず停止するならtrue
xがある条件に対しては停止しないことがあるならfalse
という判定（trueとfalseはどちらでも構わないけど）
これなら判定結果が必ず一意に決まるが、そうでなければ確実に判定
なんて通常は言わない

>>78
Pの入力にするxのほうのつもり
まあP'に渡したxも結局Pに渡すので同じ意味にとってもらって大丈夫だと思うけど
0080622007/07/22(日) 11:59:49
>>79
> P(x)というのは、xがいかなる条件に対しても必ず停止するならtrue
> xがある条件に対しては停止しないことがあるならfalse
ん？そうすると >>74 は違うかな。
どっちにしても矛盾は出そうにないんだが。
0081デフォルトの名無しさん2007/07/22(日) 12:29:40
■前提1
>任意のプログラムxに対して、無限ループするかどうかを確実に検出するプログラムPが存在すると仮定する。
　　BOOL Function_P ( x )
　　{
　　　　StateCheck( x );　//任意のプログラムxの構文をチェックし、無限ループの可能性を判定
　　　　if( LOOP )　　return( TRUE );　//無限ループする場合
　　　　else　　return( FALSE );　//無限ループしない場合
　　}

■前提2
>P'は入力xに対してPを用いて判定、xが無限ループなら停止・そうでなければわざと無限ループ
　　VOID Procedure_PDUSH( x )
　　{
　　　　BOOL result = Function_P( x );
　　　　while( !result );
　　}

■前提3
>さあ、P'の入力として、P'自身を判定させてみよう！
　　VOID Procedure_PDUSH( Procedure_PDUSH->Binary() )
　　{
　　　　BOOL result = Function_P( Procedure_PDUSH->Source() )
　　　　{
　　　　　　LoopCheck(　"VOID Procedure_PDUSH( x )"　);　//UnChecked
　　　　　　LoopCheck(　"BOOL result = Function_P( x );"　);　//UnChecked
　　　　　　LoopCheck(　"while( !result );"　);　//Check!!
　　　　　　return( TRUE );　//Procedure_PDUSHは、無限ループする可能性がある
　　　　}　　//BOOL result = TRUE

　　　　while( !result );
　　　　//　引数Procedure_PDUSH->Source()　は無限ループの可能性が有るため、プログラム実行を停止
　　}
0082812007/07/22(日) 12:33:54
改行制限きっついわー。

>■前提3　の
>VOID Procedure_PDUSH( Procedure_PDUSH->Binary() )　は
VOID Procedure_PDUSH( Procedure_PDUSH->Source() )　に脳内補完しといて。
どうでも良い点ではあるが。


…で。
俺には、何処がどう矛盾しているのかさっぱり解らない。
0083デフォルトの名無しさん2007/07/22(日) 12:35:04
よくわからん・・・

∃P. ∀x. (P(x)↓)∧((∀y. x(y)↓) ⇔ P(x))　・・・(1)
∃P'.∀x. (P(x) ⇔ ¬(P'(x)↓))　・・・(2)

(1)、(2)から

∃P'.∀x. ((∀y. x(y)↓) ⇔ ¬(P'(x)↓))　・・・(3)

(3)にx = P'を代入

∃P'. ((∀y. P'(y)↓) ⇔ ¬(P'(P')↓))

ってことで、(∀y. P'(y)↓) ⇒ P'(P')↓だから矛盾てことでいいのかな
0084デフォルトの名無しさん2007/07/22(日) 12:44:15
こんなごだごだで非生産的だから論理学は嫌い
事実だけ使えればＯＫ
0085デフォルトの名無しさん2007/07/22(日) 13:06:53
つーか、これって

・常に無限ループするプログラム
・無限ループする"場合がある"プログラム

を一緒くたにしてるのが悪い。

そして、無限ループするかどうかを
外部(引数x)に依存してるから判定不可能。

・静的に無限ループするかどうかを決定するプログラムは判定可能
・動的に無限ループするかどうかを決定するプログラムは判定不可能

これでFAなんじゃねーか？

論理学以前の問題だぜ。
0086デフォルトの名無しさん2007/07/22(日) 13:09:47
>>85
常に無限ループするかどうかはどうでもいい
無限ループする可能性が少しでもあるかないか、それだけ

動的であろうと静的であろうと（←どういう意味合いで使ってるのか
知らないけど）無限ループすることが「ある」か「ない」かだけが問題
0087デフォルトの名無しさん2007/07/22(日) 13:14:57
そもそも考え方が間違ってるのに矛盾するって結論付けるのがおかしい。
0088デフォルトの名無しさん2007/07/22(日) 13:17:21
そんなグダグダなこと言われても困ります
0089デフォルトの名無しさん2007/07/22(日) 13:20:16
>>86
俺は単に

実行する前に無限ループするかどうかが決定されているプログラムなら判定可能
実行時に無限ループするかどうかが決定されるプログラムなら判定不可能
そして、この二つのプログラムは本質的に別物として扱わなければいけない。

という事を言いたいだけだぜ。

それに問題文に書かれているのは「可能性」の話ではなくて、
無限ループ「するかどうか」だぜ。

True False の話に『可能性』を勝手に持ち込むな。
0090デフォルトの名無しさん2007/07/22(日) 13:24:14
>>89
「実行時に無限ループすることが決定」ってどういう状況？
あと、「可能性」っていっても「確率」の話じゃなくて、存在するかしないかの話
存在するならTrue、しないならFalseで完全に二分される
0091デフォルトの名無しさん2007/07/22(日) 13:26:50
>>90
プログラムが引数や、時刻など、外部から与えられる要素で無限ループするかどうかを決定するって意味。
そーゆープログラムは、場合によって挙動が変わるからその外部要素も決定してしまわないと判定できないよねって事。

そういう意味で、動的・静的という言葉を使った。
0092デフォルトの名無しさん2007/07/22(日) 13:31:12
>>91
当然プログラムの内部は全て有限かつ離散量で表されていることが前提
（そうでなければ計算機科学の範疇を越える）
動的に変化しうるなら、その変化の全ての組み合わせに対して判定すれば
いいだけじゃん
内部表現が離散的かつ有限であるなら、組み合わせは有限通りしかない
0093デフォルトの名無しさん2007/07/22(日) 13:46:17
>>92
再帰を忘れてるぜ。
P'の引数としてのxが任意である以上再帰の問題がある。
再帰を用いるとすべての組み合わせっていうのが無限になりうるから決定不可能。

>>37が学校で習った事を適当な理解で意訳して書いたのが問題の始まりって気がするな。
0094デフォルトの名無しさん2007/07/22(日) 13:58:13
>>93
何が再帰している場合のことを言ってるのか知らないけど、
おそらく帰納的に計算可能でしょ
つーかどっちにしろ停止問題は決定不能だし
0095デフォルトの名無しさん2007/07/23(月) 08:18:06
一日でこんなにスレが延びるなんて…
ころがループの中毒性か
0096デフォルトの名無しさん2007/10/08(月) 20:00:04
P'は、ブザーになるだけじゃないの?
最初は、無限ループじゃないから、無限ループを開始する
無限ループを検出したら、ループを止める、ループが止まったらループが開始する以下繰り返し
0097デフォルトの名無しさん2008/04/26(土) 21:45:41
oq
0098デフォルトの名無しさん2008/07/15(火) 16:49:25
とかちつくしてから、格げーのコマンド表かぁ
すごいスレだな
0099デフォルトの名無しさん2008/07/30(水) 18:04:37
Common Lispのloopマクロはかなり中毒性あるよ
0100デフォルトの名無しさん2008/08/07(木) 05:41:34
ttp://toshi-2chan.com/b10/src/1216296826045.gif
0101デフォルトの名無しさん2008/11/08(土) 10:49:53
PやP'は無限ループすると言ってるんだから必ず停止するんじゃないの？
どこが矛盾なのかさっぱり・・・
おしえてエロイ人！
01021012008/11/08(土) 13:11:11
よくわからないからWPのチューリングマシンの停止性問題を読んでみたが
たぶん>>37が言ってることはチューリングが言ったこととは似て非なるもの
チューリングが言ったことは論理的に正しいように思えた
どこが違うと言われるとわけわからなくなってしまうんだが
0103デフォルトの名無しさん2008/11/08(土) 14:15:03
>>83
(∀y. P'(y)↓) ⇔ ¬(P'(P')↓) は
P'(P')↓ かつ ∃y. ¬(P'(y)↓) なら矛盾しない。
つまりこの設定だと矛盾しない。
だから P' を
∀x.((∀y.x(y)↓) ⇔ ¬(P'(x)↓))
ではなく、ちゃんと
∀x.((x(x)↓) ⇔ ¬(P'(x)↓))
と定義しないといけない。
0104デフォルトの名無しさん2008/11/08(土) 14:16:07
まあ、>>37に教えた人か>>37の理解が間違ってたってこった。
01051012008/11/08(土) 14:16:34
よ〜く考えてみたらチューリングマシンの停止性問題自体がおかしい気がしてきた
Mは無限ループで作るんだから有限時間に停止しない場合があることは判ってる
したがってM自身を判定させたら必ず停止する
M自身は停止するときとしないときがあってM自身を判定するときは
必ず停止するんだから全く矛盾しない
この証明はプログラムが有限時間に停止するときとしないときがあって
それを一緒に扱ってしまっていることに欠陥がある
やべ俺ってチューリングより頭良い？
0106デフォルトの名無しさん2008/11/08(土) 14:43:54
>>102
P'とMの定義が違う。
P'の定義は曖昧になってて
P'(x) = x が停止するならループ、しないなら停止
だと P' は入力を取らないプログラムを引数に取るので
P'(P') は考えられない。よってP'は次のように定義されていると思われる。
P'(x) = 任意の入力 y に対して x(y) が停止するならループ、そうでなければ停止
これだと>>103や>>105の言うとおり、
P'(停止するプログラム) は停止しないので、
P'の定義からP'(P')は停止し、それはなんら矛盾しない。
でも wikipedia のように
M(x) = x(x) が停止するならループ
と定義すると矛盾する。
0107デフォルトの名無しさん2008/11/08(土) 14:47:26
あ、すまん
P'(停止するプログラム)
じゃなくて
P'(ある入力に対し停止するプログラム)
だ。いや、常に停止するんでもいいんだけどさ。
0108デフォルトの名無しさん2008/11/08(土) 16:35:11
なるほどMが再帰的に入力されるって事ですね
俺の頭のスペックでは正しいってことしか判りませんでした
チューリング博士ごめんなさい
0109デフォルトの名無しさん2008/11/08(土) 17:20:15
M(x) = x(x) が停止するならループ
後半抜けてる
M(x) = x(x) が停止するならループ、そうでなければ停止
x に M を代入すると明らかにおかしくなるわな。
0110デフォルトの名無しさん2009/03/21(土) 16:24:24
は？
0111デフォルトの名無しさん2009/04/19(日) 14:55:21
は？
■ このスレッドは過去ログ倉庫に格納されています