Geek asks and answers

Is the turing dictionary finished

With a dictionary, I mean an array of key / value pairs with unique keys. If not, why? If long enough, you can use the key as an input, and the value as a result, and it can have the solution to as many problems as possible. He could “calculate” anything as long as he was long enough to hold all possible input. Which should not be infinite, as long as it is established that the input will have a certain number of bits. Therefore, if we agree that the input will be X bits, you only need a dictionary with 2 ^ X-elements, and you will have every possible device for turing that will accept X-bits as input.

Correctly? Well, I think I'm not for what?

+3
source share
3 answers

A simple Turing machine can add two integers - any two integers. The final dictionary cannot.

EDIT:
(I am editing my answer because soandos did too well to respond in a tight block of comments.)

Good question! Suppose we have an infinite dictionary listing the {key, value} pairs, where the keys are all possible combinations of Turing machines and their final inputs (or, which is the same, all possible finite input sequences for a universal Turing machine) in ascending order. Values ​​are corresponding end states, with the leading bit indicating [HALTS, NOT HALT]. I affirm that this is Turing. (The act of finding a record is trivially simple, and I don't think we should argue about that.)

JSoldi: [HALT, NOT HALT] , . , , , - ​​ . , - , . - ( , ), .

+4

, . , , / .

, X , X ^ 2, 2 ^ X. .

, /, , , , , - , .

0

Turing completeness is associated with a set of rules to do something, and not how to store data. See here .

-1
source

More articles:


All Articles