Upgrade to Pro — share decks privately, control downloads, hide ads and more …

停止性問題と数 / Halting problem and number

停止性問題と数 / Halting problem and number

2016年2月16日にリブセンスの社内勉強会「0x64物語」で発表した資料です。
毎回テーマを決めてLTを行うスタイルの勉強会で、このときのテーマは「数」でした。

アップロードは2022年9月15日に行いました。

Takahiro Uchiyama

September 15, 2022
Tweet

More Decks by Takahiro Uchiyama

Other Decks in Programming

Transcript

  1. ఀࢭ͢Δ͔Ͳ͏͔ ൑ఆ͢Δ ϓϩάϥϜ IBMU ͕ ॻ͚ͨͱԾఆͯ͠ def halt?(program, data) #

    真に驚くべき実装を発見したが、 # ここに記すには余白が狭すぎる [true, false].sample end
  2. IBMU ͕USVFͳΒಈ͖ଓ͚ͯ GBMTFͳΒఀࢭ͢ΔॲཧΛॻ͘ def self_check(program) result = halt?(program, program) puts

    "The result of 'halt?' is #{result}" if result while true puts "Never halting!!" end else puts "Just halting" end end
  3. def halt?(program, data) # 真に驚くべき実装を発見したが、 # ここに記すには余白が狭すぎる [true, false].sample end

    def self_check(program) result = halt?(program, program) puts "The result of 'halt?' is #{result}" if result while true puts "Never halting!!" end else puts "Just halting" end end self_check($stdin) ϓϩάϥϜ શମ૾
  4. The result of 'halt?' is true Never halting!! Never halting!!

    Never halting!! Never halting!! Never halting!! Never halting!! Never halting!! Never halting!! Never halting!! Never halting!! --snip-- The result of 'halt?' is false Just halting ໃ६͢Δ
  5. ϓϩάϥϜͰ࢖͑Δจࣈ͸ DPVOUBCMFͰ͋Δ a b c d e f g h

    i j k l m n o p q r s t u v w x y z A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 0 1 2 3 4 5 6 7 8 9 ! " # % & ' ( ) + , - . / : ; < = > ? [ \ ] ^ _ ` { | } ~
  6.  ͷ܁ฦ͠ ͷ܁Γฦ͠ ˽ʸ ͷ܁Γฦ͠ ϥϯμϜ    

       ʙͷશͯͷ࣮਺ྻΛ ༻ҙͨ͠ͱԾఆͯ͠
  7.  ͷ܁ฦ͠ ͷ܁Γฦ͠ ˽ʸ ͷ܁Γฦ͠ ϥϯμϜ    

      ֤ྻͷ֤ܻΛର֯ઢʹ૸ࠪͯ͠ ͍ͯ͘͠ͱඞͣ৽͍࣮͠਺͕Ͱ͖Δ