Comment by Jyaif

4 years ago

Can you point me towards some source code where a human can't find the algorithmic complexity?

5 comments

Jyaif

Reply
smallnamespace  4 years ago

Humans can't tell you whether this program will run forever on any particular (positive integer) input, or whether all inputs terminate.

  def collatz(n):
      while n != 1:
          print(n)
      if n % 2 == 0:
          n = n // 2 
      else:
          n = n * 3 + 1

      print(1)

  • kibibyte  4 years ago

    I think your indentation needs to be adjusted? Like so:

      def collatz(n):
      while n != 1:
          print(n)
          if n % 2 == 0:
              n = n // 2 
          else:
              n = n * 3 + 1

      print(1)

    Otherwise, n = 1 terminates, and n != 1 gets stuck looping at lines 2-3.

adrianN  4 years ago

It's not hard to implement the construction in the proof. Generally you'll encounter problems in the wild in any interpreter. Similarly you can encode many open mathematical problems into simple programs where finding runtime bounds is equal to solving the problem. The Collatz Conjecture for example.