Scribd Logo
Upload

Welcome to Scribd!

  • 70 views

    COMP 4036 Computability

    Uploaded by

    Marko Schuetz
    This document discusses computability and partial functions. It introduces the concept that not all functions are computable by a Turing machine. It provides examples of computable and non-computable functions, including the halting problem which cannot be solved algorithmically. The document also discusses how programming languages are constrained by computability limits but are still Turing complete, allowing them to compute any partial recursive function.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd

    COMP 4036 Computability

    Uploaded by

    Marko Schuetz
    70 views18 pages
    This document discusses computability and partial functions. It introduces the concept that not all functions are computable by a Turing machine. It provides examples of computable and non-computable functions, including the halting problem which cannot be solved algorithmically. The document also discusses how programming languages are constrained by computability limits but are still Turing complete, allowing them to compute any partial recursive function.

    Original Title

    computabilityS

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses computability and partial functions. It introduces the concept that not all functions are computable by a Turing machine. It provides examples of computable and non-computable functions, including the halting problem which cannot be solved algorithmically. The document also discusses how programming languages are constrained by computability limits but are still Turing complete, allowing them to compute any partial recursive function.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    70 views18 pages

    COMP 4036 Computability

    Uploaded by

    Marko Schuetz
    This document discusses computability and partial functions. It introduces the concept that not all functions are computable by a Turing machine. It provides examples of computable and non-computable functions, including the halting problem which cannot be solved algorithmically. The document also discusses how programming languages are constrained by computability limits but are still Turing complete, allowing them to compute any partial recursive function.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 18

    COMP 4036

    Computability
    Overview
    · not all functions are computable

    · (almost) all programming languages are suitable to ex-


    press all computable functions

    · computability limits power of programming languages in


    general
    Partial Functions & Computability
    ?
    · program ≡ function from inputs to outputs

    · theory and practice...


    Expressions and Values
    · What is the value of 3 + 2, 232, sin(π), 3/0?

    · computation: error termination; nontermination

    · examples: error termination 3/0; nontermination ...


    Nontermination
    f(x:int) = if x = 0 then 0 else x + f(x - 2)

    f(4) =?
    f(5) =?
    Nontermination
    f(x:int) = if x = 0 then 0 else x + f(x - 2)

    f(4) = 4 + f(2) = 4 + 2 + f(0) = 4 + 2 + 0


    f(5) = 5 + f(3) = 5 + 3 + f(1) = 5 + 3 + 1 + f(-1) =
    ...

    =⇒ partial
    Partial Functions
    · functions in programming differ from functions in math:
    partial vs. total

    · total function: takes every element from its domain to a


    unique element in its range

    · partial function: may not map some of its domain ele-


    ments (“undefined”)
    Programs and Partial Functions
    · recursion, loops, . . . → possible nontermination

    · example: f(x:int) = if x = 0 then 0 else x + f(x


    - 2)

    · x ≥ 0 and x is even: terminates with a value


    x < 0 or x is odd: computation can go on forever without
    giving a result

    Note g(x:nonnegeven) = if x = 0 then 0 else x + g(x


    - 2) is a total function. g(-1) or g(5) are illegal expres-
    sions → type checker
    Computability
    · computable?

    − f : N → N. f (x) = 3x

    − g : N → N. g(x) = x

    true if the tooth fairy exists


    n
    − h : B. h =
    false otherwise
    − k : N → N. k(x) = the first 10x digits of π

    · computable: there is a program that computes it


    Computability as Criterion
    · programming languages differ

    Can we implement something in one programming lan-


    guage but not in another?

    · Church’s Thesis

    All computing devices can compute exactly the partial


    recursive functions.

    · Characterizations of partial recursive functions, e.g.:

    − Turing machines

    − Lambda calculus (details later)

    · (almost) all programming languages are Turing complete


    Turing Machine
    · very primitive computational model, here: multi--tape

    · k tapes, infinite to one side, divided into cells

    · tape symbols

    · read--/write--head per tape on exactly one cell

    · finite control, state

    · computation step:

    1. state change

    2. replace symbols under heads

    3. move heads (per tape L, R, S)


    Turing Machines more formal
    A Turing machine M is defined by:

    M = (Q, T, I, δ, b, q0, qf )

    where

    Q set of states

    T set of tape symbols

    I set of input symbols I ⊆ T

    δ state--transition function Q×T k → Q×(T ×{L, R, S})k

    b blank

    q0 initial state
    qf final state

    · configuration: (α1, . . . , αk ) for k tapes, where αi = xiqyi

    · computation step: `
    Computing Functions with TMs
    · input encodes arguments: e.g. x1#x2# . . . #xn#

    · one tape is a “result tape”: e.g. the kth

    · TM stops with y on tape k: TM computes f (x1, x2, . . . , xn) =


    y
    Non--Computable Functions
    · Are there “interesting” functions that we cannot com-
    pute?

    · Yes! → e.g. Halting Problem


    Halting Problem
    · given: program text T , string S

    · wanted: Answer to the question “Will T terminate when


    run on input S?”

    · no program can solve the Halting Problem


    Non--Computability of the Halting
    Problem
    · Halting Problem as function:

    true if T halts when run on input S


    n
    fHalt(T, S) =
    false otherwise

    · assume program Q computes fHalt

    · construct program D as:

    D(T) = if Q(T,T) then run forever else halt

    · does D(D) halt?


    Applications
    · recursion, loops

    while (...) {
    ...
    }
    ... remaining program ...

    or

    let f(x:int) = if x = 0 then 0 else x + f(x - 2)


    in g(f(3))

    · checking of precise types: e.g. this program uses the first


    3 characters of its string input

    You might also like