Agnishom

Diag = {M | M does not accept M}
HP = {(M, x) | M accepts x}
Co-Univ = {M | there exists w such that M does not accept w}

Claim: HP <= Diag <= Co-Univ

Reduction from HP to Diag

Say HP has input (M, x)
Design Turing Machine N such that:

Agnishom

• We viewed computation just as the process of rewriting. Is this notion powerful enough? Can we use such a model to compute whatever we like?

  • It turns out that we can. Functional programming is based on an abstraction called the Lambda Calculus
  • To have a sense of the multitude of the strange systems that are really just as powerful as traditional computers, see Esoteric Languages. BrainF and FRACTRAN are particularly interesting. Rule 110 could be an honorable mention
  • Having said that, Haskell could be a pleasant and practical language to program in.

• In class, we defined plus in terms of succ.

  • Can you define mult standing for multiplication, in terms of plus
    • Install the Haskell interpreter on your device and check if your program works. Alternately, use the repl.it environment online.

• C

Agnishom

a[1], a[2], a[3], \cdots is an arithmetic progression. b[1], b[2], \cdots is also an arithmetic progression, such that b[i] \in \mathbb{N} for every [i]. Is a[b[1]], a[b[2]], \cdots an arithmetic progression as well?

• What are we doing here?
  • Composing Sequences
    • How many sequences?
      • Two
    • Can we compose more sequences?
      • Yes, but let's try if we can do just two for now.
      • Also, more than two sequences look complicated.
• Which two sequences should we compose?

Agnishom

Broad categories of CS directives.

(incomplete list)

Algorithms

• How do you reach from config to config using rules?
  • How many steps do you need?
  • Given config, rules and objective. How can you minimize/maximize objective?
  • Can you possibly reach from config to config`?

Agnishom

• All You Need Is Lambda

  • Not recommended for a first introduction to functional programming. Most people wouldn't have an idea on what this really is.
  • But it is not a bad idea to convince people that "Computation by rewriting" really works
    • Maybe worthwhile to give examples of other esoteric turing complete systems

• The following chapters are rather essential:

  • Hello, Haskell!
  • Basic Datatypes
  • Types

• Typeclasses

Agnishom

import angr
import strace
import subprocess

def getSysCalls(command):
    p = angr.Project(command)
    pg = p.factory.path_group()
    while len(pg.active) > 0:
        deadNow = len(pg.deadended)
        pg.step()

Agnishom

/*
   american fuzzy lop - fuzzer code
   --------------------------------

   Written and maintained by Michal Zalewski <lcamtuf@google.com>

   Forkserver design by Jann Horn <jannhorn@googlemail.com>

   Copyright 2013, 2014, 2015, 2016 Google Inc. All rights reserved.

Agnishom

# from Kushpreet Singh


Albums (Almost every song in the album is good)
Pink Floyd - Meddle, The Division Bell (Progressive Rock)
Beach House - Depression Cherry (Dream Pop)
Coldplay - Parachutes, Ghost Stories (Alternative rock)

Songs
Archive - Again, Bullets

Agnishom

import random

def randomDAG(minHeight, maxHeight, minFat, maxFat, p):
    '''
    create levels, and draw edges across levels
    from http://stackoverflow.com/questions/12790337/generating-a-random-dag
    '''
    height = random.randint(minHeight, maxHeight)

    nodes = 0

Agnishom

from fibHeap import FibonacciHeap #https://github.com/Agnishom/fibonacci-heap-python/

def prims(adjList, source = 1):
    n = len(adjList)    #intentionally 1 more than the number of vertices, keep the 0th entry free for convenience
    visited = [False]*n
    parent = [None]*n
    cost = [float('inf')]*n

    heapNodes = [None]*n
    heap = FibonacciHeap()