Question

Hello, I need an explaination of the following: (Turing-)computable functions = μ-recursive functions = λ-computable functions. Please give me an examples and equations for μ-recursive functions and λ-computable functions. If possible, can you please provide a brief explaination on both functions so they are easy to understand and provide examples. Thank you

Answer 1

I will explain here each functions separately and will be providing example for each one too.

From that you can able to grasp how it connected together and why it is called equal.

I hope it helps. Let’s start Turing computable function

Turing computable

A function is Turing computable if the function’s value can be computed with a Turing machine.

More specifically, let DDD be a set of words in a given alphabet and let fff be a function which maps elements of DDD to words on the same alphabet. We say that fff is Turing computable if there exists a Turing machine such that

• If one starts the Turing machine with a word w∈DwDw\in D as the initial content of the tape, the computation will halt.
• When the computation halts, the tape will read f⁢(w)fwf(w).

Formally, let Σnormal-Σ\Sigma be an alphabet and f:Σ*→Σ*normal-:fnormal-→superscriptnormal-Σsuperscriptnormal-Σf:\Sigma^{*}\to\Sigma^{*} on words over Σnormal-Σ\Sigma. Then fff is said to be Turing-computable if there is a Turing machine TTT over Σnormal-Σ\Sigma (its input alphabet), as defined in this entry, such that for any w∈Σ*wsuperscriptnormal-Σw\in\Sigma^{*},

(s,τw,1)→*(h,τf⁢(w),m)superscriptnormal-→ssubscriptτw1hsubscriptτfwm(s,\tau_{w},1)\rightarrow^{*}(h,\tau_{{f(w)}},m)

for some mmm. Here, hhh is a halt state (either an accept or a reject state), and τwsubscriptτw\tau_{w} for any word www is defined as the tape description such that the content of the iii-th square is the iii-th letter of www, and blank everywhere else.

Because of the fact that all types of Turing machines (deterministic, non-deterministic, single head, multiple head, etc.) all have the same computational power, it does not matter which type of Turing machine one uses in the definition.

It is not hard to find examples of Turing computable functions — because Turing machines provide an idealized model for the operation of the digital computer, any function which can be evaluated by a computer provides an example.

Notation:

We represent a natural number n by a string of n1s. We represent a sequence of k natural numbers n1,n2….nk by a string of the form #11..11#1..#111where there are s between the ith and i+11th#.We will use the notation #(n1,n2,…nk) to represent this string. For example,

#(3,2)=#111#11

Definition:

A function f:N*N*…..*N->N of k,of variables, is called Turing Computable if there exists a Turing Machine Tf

such that for all n1,n2….nk we have the derivation

q1#(n1,n2,…nkàq accept#(f(n1,n2…nk))).

Example: Suppose f:N*N*…..*N->N= n^21+n2

then

Q1#11#1qa accept#11111#

A function is recursive iff it Turing Computable. With appropriate modifications of the relevant definitions, this also holds for partial recursive functions.

Next we will move to μ-recursive functions

μ-recursive functions

In mathematical logic and computer science, the μ-recursive functions are a class of partial functions from natural numbers to natural numbers that are "computable" in an intuitive sense. In fact, in computability theory it is shown that the μ-recursive functions are precisely the functions that can be computed by Turing machines. The μ-recursive functions are closely related to primitive recursive functions, and their inductive definition builds upon that of the primitive recursive functions. However, not every μ-recursive function is a primitive recursive function—the most famous example is the Ackermann function.

Other equivalent classes of functions are the λ-recursive functions and the functions that can be computed by Markov algorithms.

The μ-recursive functions (or partial μ-recursive functions) are partial functions that take finite tuples of natural numbers and return a single natural number. They are the smallest class of partial functions that includes the initial functions and is closed under composition, primitive recursion, and the μ operator.

The smallest class of functions including the initial functions and closed under composition and primitive recursion (i.e. without minimisation) is the class of primitive recursive functions. While all primitive recursive functions are total, this is not true of partial recursive functions; for example, the minimisation of the successor function is undefined. The primitive recursive functions are a subset of the total recursive functions, which are a subset of the partial recursive functions. For example, the Ackermann function can be proven to be total recursive, but not primitive.

a)Constant function: For each natural number n {\displaystyle n\,} n and every Fk {\displaystyle k\,}

f ( x 1 , … , x k ) = n {\displaystyle f(x_{1},\ldots ,x_{k})=n\,}f(x1,……xk)=n.

Alternative definitions use compositions of the successor function and use a zero function, that always returns zero, in place of the constant function.

b)Successor function S:

S ( x ) = d e f x + 1 {\displaystyle S(x){\stackrel {\mathrm {def} }{=}}x+1\,} S(x)def=x+1

c)Projection function P i k {\displaystyle P_{i}^{k}} :For all natural numbers i , k {\displaystyle i,k\,} I,k such that 1 {\displaystyle 1} 1 <=i<=k

P^k(x1,….xk)def=xi.

Next we will move to λ-computable functions.

λ-computable functions

Lambda calculus (also written as λ-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation that can be used to simulate any single-taped Turing machine and was first introduced by mathematician Alonzo Church in the 1930s as part of an investigation into the foundations of mathematics.

Lambda calculus consists of constructing lambda expressions and performing reduction operations on them. Expressions are built from just the following forms:

Syntax	Name	Description
a	Variable	A character or string representing a mathematical or logical parameter
(λx.M)	Abstraction		Function definition (M is a lambda expression). The variable x        becomes bound in the expression.
(M N)	Application	Applying a function to an argument. M and N are lambda expressions

producing expressions such as: (λx.λy.(λz.(λx.z x) (λy.z y)) (x y)). Parentheses can be dropped if the expression is unambiguous. In some applications terms for logical and mathematical values and operations may be included.

The reduction operations include:

Operation	Name	Description
((λx.M) E) → (M[x:=E])	β-reduction	Substituting the bound variable by the argument expression in the body of the abstraction
(λx.M[x]) → (λy.M[y])	α-conversion	Renaming the bound (formal) variables in the expression. Used to avoid name collisions.

Lambda calculus is Turing complete, that is, it is a universal model of computation that can be used to simulate any single-taped Turing machine.^[1] Its namesake, the Greek letter lambda (λ), is used in lambda expressions and lambda terms to denote binding a variable in a function.

Lambda calculus may be typed and untyped. In typed lambda calculus, functions can be applied only if they are capable of accepting the given input's "type" of data.

Lambda calculus has applications in many different areas in mathematics, philosophy, linguistics, and computer science. Lambda calculus has played an important role in the development of the theory of programming languages. Functional programming languages implement the lambda calculus. Lambda calculus also is a current research topic in Category theory

The lambda calculus consists of a language of lambda terms, which is defined by a certain formal syntax, and a set of transformation rules, which allow manipulation of the lambda terms. These transformation rules can be viewed as an equational theory or as an operational definition.

As described above, all functions in the lambda calculus are anonymous functions, having no names. They only accept one input variable, with currying used to implement functions with several variables.

From these explanation and example it is clear that

i.e.,(Turing-)computable functions = μ-recursive functions = λ-computable functions P i k ( x 1 , … , x k ) = d e f x i . {\displaystyle P_{i}^{k}(x_{1},\ldots ,x_{k}){\stackrel {\mathrm {def} }{=}}x_{i}\,.}