檜山正幸のキマイラ飼育記 メモ編 このページをアンテナに追加 RSSフィード

この「はてなダイアリー」は、
2019年1月18日の記事を最後に更新を停止します。
しかし、
「檜山正幸のキマイラ飼育記 メモ編」は保存され、新規ブログに移行します。
新しい「檜山正幸のキマイラ飼育記」と関連ブログについては、
こちらの記事 をごらんください。
連絡は hiyama{at}chimaira{dot}org へ。

2018-10-18(木)

ストレンジな関数/述語

| 19:21 |

function strange-func(x:Func1Code):Void :=
  if (halt(x, x)) then forever()
  else done()
;

predicate strange-pred(x:Pred1Code) :=
  ¬provable(x, x)

Godはゲーデル符号化だとして、次の述語を考える。

  • halt(God(strange-func), God(strange-func)) : Bool
  • provable(God(strange-pred), God(strange-pred)) : Bool
トラックバック - http://d.hatena.ne.jp/m-hiyama-memo/20181018/1539858060