Non-computable functions and undecidable problems:

Many questions regarding the behavior of TMs are undecidable. This signifies that there is no algorithm (that is, no TM) which answers such a question regarding any random TM M, given its explanation <M>. The halting trouble is the protypical undecidabilty outcome.  Computability and decidability are essentially similar concept - we use 'decidable’ if the requested outcome is binary, ‘computable’ if the outcome comes from a bigger range of values. Therefore there are lots of non-computable functions - however, nearly no functions are computable!

A) Nearly nothing is computable:

This provocative claim depends on a simple counting argument: there is just a countable infinity of TMs, however there is an uncountable infinity of the functions - therefore, there is not adequate TM to evaluate all the functions.

Once we have stated our code for explaining TMs, all TM M has an explanation <M> that is a string over certain alphabet. Lexicographic ordering of such strings states a 1-to-1 correspondence among the natural numbers and TMs, therefore showing that the set of TMs is countable.

Georg Cantor (1845-1918, originator of set theory) exhibited that the set of functions from natural numbers to natural numbers is not countable. Cantor’s diagonalization method is a standard tool employed to prove undecidability outcomes.

By way of contradiction, suppose that all functions from natural numbers to natural numbers have been positioned in 1-to-1 correspondence with natural numbers 1, 2, 3... and therefore can be labeled f1, f2, f3,...

f1: f1(1) f1(2) f1(3) f1(4) ... f1: f1(1) + 1 f1(2) f1(3) f1(4) ...
f2: f2(1) f2(2) f2(3) f2(4) ... f2: f2(1) f2(2) + 1 f2(3) f2(4) ...f3: f3(1) f3(2) f3(3) f3(4) ... f3: f3(1) f3(2) f3(3) + 1 f3(4) .
   ..
Let consider the ‘diagonal function’ g(i) = fi( i) exhibited at left. This could be one of the functions fk - no trouble so far. Now consider a ‘modified diagonal function’ h(i) = fi( i) + 1 exhibited at right. The function h varies from all fk, as h(k) = fk(k) + 1 ≠ fk(k). This contradicts the supposition that the set of functions could be enumerated and exhibits that there are an uncountable infinity of the functions from natural numbers to natural numbers.

This takes more ingenuity to state a specific function that is probably non-computable:

B) The Busy Beaver problem T. Rado: On non-computable functions

Given n > 0, let consider n-state TMs M = (Q, {0, 1}, f, q1) which begin with a blank tape. The ‘Busy Beaver function’ B(n) is stated as the biggest number of 1s an n-state TM can write and still stop. The accurate value of B(n) based on the details of ‘Turing machine syntax’. We code halting as the action in transition. The given illustrations prove B(1) = 1 and B(2) = 4 by the exhaustive analysis.

Lemma: B(x) is total, that is, defined for all x ≥ 1 (evidently), and monotonic, that is, B(x) < B(x+1) for all x ≥ 1.

Proof: let consider a TM M with x states which attains the maximum score B(x) of writing B(x) 1s before halting.

Beginning in its initial state on blank tape, M will trace certain path through its state space, finishing with the transition of form q, a -> -, 1, Halt. The dash “-” signifies for the convention which a halting transition leads ‘nowhere’, that is, we require no halting state. Writing a 1 prior to halting can’t hurt. M can be employed to construct M’ with x+1 states which writes an additional 1 on tape, as follows. The state space of M’ comprises of the state space of M, an additional state q’, and the given transitions: M’s transition q, a -> -, 1, Halt is altered to q, a -> q’, 1, R. Two new transitions:  q’, 1 -> q’, 1, R and q’, 0 -> -, 1, Halt cause the read or write head to skip over 1s to its right till it finds out a 0. This 0 is modified to 1 just prior to halting, and therefore M’ writes B(x) + 1 “1s”.

Theorem (Rado, 1962): B(x) is not computable. Furthermore, for any Turing computable (net recursive) function

f: N -> N, Here N = {1, 2, ..}, f(x) < B(x) for all adequately large x.

Like most impossibility outcomes (there is no TM which computes B), the reasoning included is not intuitively evident, therefore we provide two proofs. Whenever discussing TMs which compute a function from integers to integers, we suppose all integers x are written in certain (reasonable) notation <x>. Usually, <x> is in binary, bin(x), or in the unary notation u(x), that is, a string of x 1s.

Proof 1: B() is not computable: Suppose B(x) is computable, that is, there is a TM that, when began on a tape initialized with u(x), halts with u( f(x)) on its tape. When B(x) is computable, therefore is D(x) = B(2x). Assume M be a TM which computes D, suppose k is the number of states of M.

For each value of x, suppose Nx be a TM which begins on a blank tape, writes u(x), and halts. Nx can be implemented by using x states (that is, fewer states suffice, however we don’t require that).

Now consider TM Mx, is a combination of Nx and M with x + k states. Nx begins on a blank tape and writes u(x).

Rather than halting, Nx passes control to M, which continues to compute D(x). Therefore, Mx begins on a blank tape and halts with u(D(x)) = (a string of B(2x)  1s). As Mx, with x + k states, is a candidate in Busy Beaver competition which produces B(2x) 1s, and by definition of B(), we encompass B(x + k)  ≥ B(2x).  For the values of x > k, thanks to the monotonicity of B(), we encompass  B(x + k) < B(2x). Such two inequalities lead to the contradiction B(2x) ≤ B(x + k)  <  B(2x) for all x > k, therefore proving B() non-computable.

Proof 2: B() grows quicker than any computable function: Assume f: N -> N be any Turing computable function, and let M be a TM with k states which computes f. We hope that a fast-growing function which writes its outcome f(x) in unary can be turned to a serious competitor in Busy Beaver race. Rather, we will conclude that f is slow-growing function as compared to the Busy Beaver function B(). More accurately, we ask: ‘for what values of x may a modified version of M which produces f(x) in the unary notation is a strong Busy Beaver competitor?’ We will conclude that this may be the case for a finite number of ‘small’ values of x, however M has no chance for all values of x beyond certain fixed x0. The technical details of this argument follow.

For each and every value of x, suppose Nx be a TM which begins on a blank tape, writes u(x), and halts. Nx can be implemented with [log x] + c states, for certain constant c, as follows: Nx first writes bin(x), a string of [log x] bits, utilizing [log x] initialization states. Then Nx summons the binary to unary converter BU, a TM with c states.

Now consider TM Mx, that is, a combination of Nx and M with [log x] + c + k states. Nx begins on a blank tape, writes u(x), then passes control to M, which proceeds to compute f(x) in unary notation, that is, produces f(x) 1s.

Mx, with [log x] + c + k states, is an entry in Busy Beaver competition with score f(x), therefore f(x) ≤ B([log x] + c + k ). As [log x] + c + k < x for all adequately large x, and due to the monotonicity of B() verified in the lemma, B([log x] + c + k ) < B(x), and therefore f(x) < B(x)  for all adequately big x. QED

This is important to differentiate the theoretical concept ‘not computable’ from the pragmatic ‘we don’t know how to evaluate it’, or even the stronger version ‘we will never know how to evaluate it’. Illustration: is the function f(n) = min [ B(n), 109999} computable or not? Yes, it is. As B() is monotonic, f() first grows up to certain argument m, then remains constant: B(1) < B(2) < B(3) <  ... < B(m) ≤ 109999, 109999, ... A big however conceptually trivial TM can store the first m function values and constant 109999, and print the accurate answer f(n) given the argument n. There are two reasons for arguing that ‘we will never be capable to compute f(n)’. First, the numbers included are unmanageable. Second, even when we could enumerate all Busy Beaver competitors till we find out one, state Mk with k states, which prints at least 109999 1s; we could never be certain whether we missed the stronger competitor Mc with c < k states that as well prints at least 109999 1s and halts. Among TMs with c states, there may have been some printed more than 109999 1s, however we dismissed them as not halting. And though it is possible to prove certain specific TM to be halting or non-halting, there is no common algorithm for doing so. Therefore, there will be certain TMs whose halting status remains vague.

Do not confuse the pragmatic ‘will never be capable to compute x’ with the theoretical ‘x is not computable’.

Latest technology based Theory of Computation Online Tutoring Assistance

Tutors, at the www.tutorsglobe.com, take pledge to provide full satisfaction and assurance in Theory of Computation help via online tutoring. Students are getting 100% satisfaction by online tutors across the globe. Here you can get homework help for Theory of Computation, project ideas and tutorials. We provide email based Theory of Computation help. You can join us to ask queries 24x7 with live, experienced and qualified online tutors specialized in Theory of Computation. Through Online Tutoring, you would be able to complete your homework or assignments at your home. Tutors at the TutorsGlobe are committed to provide the best quality online tutoring assistance for Theory of Computation Homework help and assignment help services. They use their experience, as they have solved thousands of the Theory of Computation assignments, which may help you to solve your complex issues of Theory of Computation. TutorsGlobe assure for the best quality compliance to your homework. Compromise with quality is not in our dictionary. If we feel that we are not able to provide the homework help as per the deadline or given instruction by the student, we refund the money of the student without any delay.