"Guess the number" Problem on Turing machines

Question

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) && "<") || ((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 used to implement "privacy" in some specific tokens written on a Turing Machine?

Answer 1

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.

Answer 2

In casual words, a Turing machine can do anything computational, but nothing else; especially there's no IO. No keyboard, no mouse. It just takes a tape as input and runs a predefined program on it.

This means that you cannot use window.prompt or similar (anything that asks for user input) in the middle of your program, and therefore there is no equivalent of "Guess the number" program for TM. So, if you want to stick to the TM as the model of computation, you basically need a different problem that can be solved with binary search, without user input in the middle of the program.

Some examples of such problems include:

• An array of integers is given in strictly increasing order. Determine if a given number exists in the array.
• An array of integers is given, so that all odd numbers come before all even numbers. Find the first even number in the array.
• Given a polynomial and a range (upper and lower limits of the value of x), find a zero of the polynomial within the given range.

Answer 3

Here is how this kind of program could be useful. Suppose that you have a graph, and you are trying to find its chromatic number $\chi$, that is, the minimum number of colors needed to color the vertices of the graph so that each edge connects vertices of different colors.

Given a target number of colors $C$, you can attempt to color the graph using $C$ colors in various ways. This corresponds to an algorithm for answering the question ``is $\chi \leq C$?''. Using binary search, you can use such an algorithm to find $\chi$ exactly.

In this example, $\chi$ isn't written anywhere. Rather, we can check whether $\chi \leq C$ for any given $C$. This suffices for finding $\chi$ using only $\log n$ queries of this form, where $n$ is the number of vertices.

Answer 4

Is there any concept of "privacy" of tokens in the world of Turing Machines or some structure that can be used to implement "privacy" in some specific tokens written on a Turing Machine?

There is a concept of obfuscation. A software code is obfuscated to make it difficult to analyze the behavior of the program, even if the source code of the program is given. This concept is mostly applied to practical programming languages or machine codes but can be applied to more computation models, including Turing machines.

A theoretical concept of obfuscation is black-box obfuscation. Informally speaking, with such obfuscation, no one with a "debugger" can inspect the program to get more information than just running the program. It is proven no such scheme exists.

Answer 5

The way I understand your question, you are wondering why there is a need to do some extra computation (binary search in your case) if the TM can simply read the input, and it will already know the number to be searched, thus performing binary search is not necessary. This might not always be the case.

Consider, the situation, such that the input is the hash value $x'$ of the number that the TM will guess, instead of the actual number $x$. Here we assume that the hashing algorithm used to produce $x'$, is built internally to the TM, that is the TM can perform a hash. Now, as you might imagine, simply reading $x'$ will not help the TM to know what $x$ is. We will force it to actually guess. Although at this point, binary search might not be possible since the TM will not be able to know if the number is less than or greater than the middle value of the range. But instead it must perform the guessing brute-force, trying all values from the range. That is, the TM will start with the lowest value, compute its hash, test if it is equal with the input. If it is, then the TM guessed the number, otherwise it moves to the next number in the range and repeat until it found the right value or exhaust the range.

As a side note, the idea here is very much similar to what you would expect from log-in systems. Even though they can validate the password you enter when logging-in, they actually do not know your actual password, since they only store the hash of the password you initially set.

---

As @jaxad0127 in the comment suggested, you can change the hash function to be some other function $f()$ that is difficult to invert but preserves order. That is, for any two numbers $x_1$ and $x_2$ such that $x_1 \lt x_2 $, it is always guaranteed that $f(x_1) \lt f(x_2)$. This would now allow you to perform binary search. But still, reading the input $x'=f(x)$ will not give the TM any idea as to what the $x$ is and would be better-off performing binary search.

Answer 6

When you find X, you don't just find X but also any other information in the same location as X.

Imagine you have n pages, on each page is written a name and address. The pages are sorted alphabetically by name and numbered from 1 to n.

You wish to find the address for Drew Lee.

You could start at page 1 and just go page by page, but that will take a really long time if n is large.

Or you could do binary search, go to n/2, check if the name on page n/2 is greater than or less than Drew Lee, and then proceed...

So you are trying to find X where X is the number of the page that has Drew Lee on it. You can't just say you already know the name Drew Lee, because you actually need the page (to get the address). But the page isn't anywhere in the question to "peek" at, you can only find the page by searching.

This is a real problem that is really solved all the time, although usually by using a library/database/etc. that already has binary search (or even faster searches) implemented. (But a database isn't a Turing Machine, I hear you cry... Yes, but the search algorithm itself functionally is, you have some static input--the search term, the information to search--and it does it's thing and gives you some output.)