File: turing.py

package info (click to toggle)
why3 1.8.2-3
  • links: PTS, VCS
  • area: main
  • in suites: forky, sid
  • size: 45,028 kB
  • sloc: xml: 185,443; ml: 111,224; ansic: 3,998; sh: 2,578; makefile: 2,568; java: 865; python: 720; javascript: 290; lisp: 205; pascal: 173
file content (21 lines) | stat: -rw-r--r-- 468 bytes parent folder | download | duplicates (3) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
#
# 'Checking a large routine' Alan Mathison Turing, 1949
#

#@ function factorial(n: int) -> int

#@ assume factorial(0) == 1

#@ assume forall n. n > 0 -> factorial(n) == n * factorial(n-1)

def routine(n):
    #@ requires n >= 0
    #@ ensures  result == factorial(n)
    u = 1
    for r in range(n):
        #@ invariant u == factorial(r)
        v = u
        for s in range(1, r+1):
            #@ invariant u == s * factorial(r)
            u += v
    return u