HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

"Guess the number" Problem on Turing machines

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
problemnumberthemachinesturingguess

Problem

I am currently learning about the concept of Turing Machines and trying to relate it with my knowledge on the application of the Binary Search algorithm.

The problem I am working on is to write an algorithm that can find an unknown natural number between two given natural numbers by guessing.

A solution would look like the following code in JavaScript.
// fixed structure "generateAsk" is always provided to the problem
let generateAsk = function() {
let guess = window.prompt("Guess: ");
return function(x) {
return ((x guess) && ">") || "="
};
};

let ask = generateAsk();

let low = window.prompt("Low: ")
, high = window.prompt("High: ");

function find_unknown_number(low, high, ask) {
// uses Binary Search to search the unknown value
// and returns the unknown value when found or -1 otherwise
}

let result = find_unknown_number(low, high, ask)
console.log(result);


My question is not meant to ask for how to solve this problem, but to ask the practical use of any algorithm that can be introduced above.

To be clearer, as I know, mostly any program can be debugged. Isn't anyone able to just stop the program written above, during its execution, with a debugger and then just filter the body of the "ask" function parameter and extract the unknown value?

The way my question is related to the Turing Machines is that, for what I know, the Turing Machines receive input on a tape (so any character introduced on the tape may very well be "visible" from the outside during any execution phase of the algorithm).

Therefore, the questions that I present to you are:

How the implementation of a solution to this problem on a Turing Machine would not be pointless from the perspective in which one can stop the program, read the "ask" function body by reading the corresponding tokens on the Turing Machine and then return the "unknown" value?

Is there any concept of "privacy" of tokens in the world of Turing Machines or some structure that can be us

Solution

Yes, it is pointless and absurd to implement an algorithm to "guess the number" using the most common kind of Turing machine, whose head can read any cell on the tape, since, as you pointed out, there is no way to enforce the condition that the algorithm/the machine should not read "the number", which must be a part of the input.

Of course, that does not mean an algorithm that can "guess the number" (efficiently) without reading the number is not useful. For example, the binary search algorithm is used in many places in real life such as git-bisect or binary-search routines in the built-in libraries of many programming languages.

Rather, that just means that kind of Turing machine is not the right model of computation for that particular problem.
What is a model of computation?

In computer science ... a model of computation is a model which describes how an output of a mathematical function is computed given an input. A model describes how units of computations, memories, and communications are organized.

Which model of computation is for "guess the number"?

One suitable choice for "guess the number" is an oracle machine.

An oracle machine ... can be visualized as a Turing machine with a black box, called an oracle, which is able to solve certain problems in a single operation.

A version of the problem of "guess the number" can be stated as the following.

A number has been chosen between integer $low$ and integer $high$. There is an oracle which, given integer $k$, answers the question "is the chosen number smaller than $k$?". How can we design an oracle-machine with that oracle that will find the chosen number given input $low$ and $high$? The less number of times the oracle is used, the better the oracle-machine is.

Beside enabling a solution, the oracle above is used to, in your words, ensure 'the 'privacy' of tokens".
There are many models of computation

There are many different kinds of computational problems. There are also many models of computation. A problem/proposition/argument makes sense only in some models of computation.

Among all models of computation, (that common kind of) Turing machine is the simplest that "can" compute anything that is "effectively computable", basically. That is why you are directed to learn it. However, that does not imply we should/may express and solve every algorithmic problem with it. For another example, it does not make much sense to implement quantum computation on a conventional Turing machine.
Exercise. What is the most popular model of computation?

By "the most popular model of computation", I mean the one that is used, implicitly or explicitly, when big $O$-notations representing time-complexity or space-complexity are mentioned on almost all millions of web pages on programming. It is certainly not Turing machine.

Context

StackExchange Computer Science Q#149268, answer score: 17

Revisions (0)

No revisions yet.