The relationship between counting and machine stop
I hope I am not helping you answer the exam question by answering your question.
Accounting machines and Turing machines are very two sides of the same coin. They are additional ways to determine if a problem is "computable". There are other equivalent ways of displaying computability (search for abacus, countable functions, computable functions, etc.). By definition, you can show that a problem can be computable if you can demonstrate that it can be solved with a Turing machine. Alternatively, you can show that a problem can be computable if you can show that it has a bijection of a solution from a countably infinite set.
By the way, a countably infinite set is a "small" infinite set or set âľâ. (In layman's terms, a small infinite or countably infinite set is a set of integers. Integers, odd numbers, or even numbers have the same cardinality - a small infinite set. There is an infinite hierarchy of infinite sets, starting at âľâ and going up for âľ_â. âľâ set integers is the smallest infinite set. âľâ is a superset of âľâ. R , the set of real numbers has the same cardinality as âľâ, and so on.) Understanding that there is a hierarchy of infinities will help you understand what you need to prove in order to show computability.
An elementary Turing machine has a small endless tape. Showing that a problem can be a computed Turing machine means that the problem has a solution, limited to a small infinite time and space. A Turing machine has a tape with infinite cells that can contain symbols. There are infinite cells in any direction (small infinite), just as the set of integers is infinite in any direction. Tape-bound is a read-write head that can move left or right on the tape and can read or write one character on each turn. Show a sequence of instructions that move the head on the tape from an initial state to a final stop or complete state to indicate that the problem is "computable". Proof thatthat a Turing machine cannot solve a problem is to prove that the problem is not computable - whether we provide countably infinite time or resources. By the way, time and space complement each other. If you can solve a problem in finite time using countably infinite space, or solve it by consuming finite space with countable (i.e. Small) infinite time, you can show that the problem is computable.by consuming finite space with countable (i.e. Small) infinite time, you can show that the problem is computable.by consuming finite space with countable (i.e. Small) infinite time, you can show that the problem is computable.
source to share
I can give you a little answer (sorry, I only know a little theory of computing).
There are only countably many Turing machines. So, if you have a set of problems that are uncountable, you know that there is at least one problem in this set for which there is no Turing machine to solve it.
So, for example, if your problem set is
For some function f: N â N, write a program that, given n, computes f (n)
You know that there is at least one f
for which such a program cannot be given, because there are many f
.
I do not believe this analysis can be applied to the halting problem, although the halting problem consists of only 1 problem: "Given the code for a Turing machine, decide if, given the empty tape, it will eventually stop." This is just one problem with a countable number of possible inputs, so just by counting it looks potentially solvable. You will have to argue in another way so that it is not resolved.
Of course, the importance of counting and uncounting is much more varied than this one example. I hope other people can provide some more.
source to share
Countability is actually very important when it comes to the Turing machine and many other places in mathematics and science. A, since the Turing machine must perform operations sequentially, each step can be assigned a counting number. If the process goes on forever, then the process is endlessly endless.
An example of an operation for which a Turing machine would be inadequate would be to sum the squares of all numbers between 1 and 2. It can be easily shown that the entire list of rational numbers in this interval can be specified in a counting list in which each number can be mapped 1 by 1 s account number. So doing steps one at a time in this list of numbers can be done by a Turing machine. However, this could not be done with irrational numbers in this interval, because there are too many of them. It can be shown (not so easily) that a list of irrational numbers cannot be put into an ordered (countable) list. Thus, it is not the order in which each number in the interval can be specified, which means that the Turing machine could not complete the task even if it was given an infinite amount of time.
source to share