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.
tutorsglobe.com nitrogen family assignment help-homework help by online p block elements tutors
Equi-partition of Energy and Classical Statistics tutorial all along with the key concepts of Equipartition Theorem, Classical Statistics, Probability of Distribution Function, Ideal gases of Atom and Electrons, Maxwell velocity Distribution
Oscillation and Waves tutorial all along with the key concepts of Medium, Categories of Waves, Transverse wave, Longitudinal wave, Sound wave, Oscillation, Harmonic oscillator, Hooke's law, oscillatory motion
tutorsglobe.com descriptive statistics assignment help-homework help by online statistics tutors
Metal Oxide Field Effect Transistor tutorial all along with the key concepts of MOS-FET operation, MOSFET output curves, relationship between Drain voltage and saturation in MOSFET, MOSFET device types, P-Channel Enhancement Mode
tutorsglobe.com reserve money assignment help-homework help by online money tutors
tutorsglobe.com role of bacteria in industry assignment help-homework help by online beneficial activities of bacteria tutors
The process that generates recombinations of gene through interchanging of corresponding segments among the nonsister chromatids of homologous chromosomes, is known as recombination of chromosomes.
the chemical industry-an overview tutorial all along with the key concepts of complex characteristics of the chemical industry, what does the chemical industry produce and economic aspects
Plant anatomy (Ana = as under, tamnein = to cut) is the learning of inner structure and organization of plants, particularly of their parts by the source of dissection and microscopic examination.
Theory and lecture notes of Lines in the Plane all along with the key concepts of Slope of a Line, Point-Slope Form of a Line, Slope-Intercept Form of a Line, General Form of a Line, Vertical and Horizontal Lines, Perpendicular Lines and Parallel Lines. Tutorsglobe offers homework help, assignment help and tutor’s assistance on Lines in the Plane.
www.tutorsglobe.com offers free trade and protection, restrictions on international trade assignment help-homework help, free economics tutorial by qualified tutor's help.
tutorsglobe.com factors governing ionization energy assignment help-homework help by online ionisation potential tutors
Morphological and Genetic adaptations of Microorganism tutorial all along with the key concepts of Microbial adaptation to Marine and Freshwater Environments, Marine and freshwater environments, Polymerase Chain Reaction and temperature-stable DNA polymerase
Micro-organism in Ecosystem tutorial all along with the key concepts of Soil microbiology, Methods of study and isolation of soil microorganisms, Factors affecting microbial growth in soil, Aeromicrobiology, significance of aeromicrobiological studies and isolation of aerial micro-organisms
1946536
Questions Asked
3689
Tutors
1460334
Questions Answered
Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!