4
$\begingroup$

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?

$\endgroup$
16
  • 5
    $\begingroup$ IMO, such considerations are alien to the Turing Machine theory. In fact you can define a machine the way you want, for instance by stating that the tape can only be seen by the reading head. $\endgroup$ Feb 17 at 16:48
  • 5
    $\begingroup$ As I said, privacy is irrelevant to TM, so there is no reference. As if you were asking the color of a TM. $\endgroup$ Feb 17 at 17:42
  • 1
    $\begingroup$ Ignore what Yves Daoust said, as it is completely bogus. As in JohnL.'s answer, such restrictions are trivially captured by the very common concept of oracle TMs. And you may also be interested in reading about Arthur-Merlin games in the future. $\endgroup$
    – user21820
    Feb 18 at 12:18
  • 3
    $\begingroup$ @coolest10, I am afraid that you are using this website the wrong way by adding new question in the same question/answers page, especially with so many existing answers. This website is designed for one question and answers to that question, one of which can become accepted and all of which can be upvoted/downvoted. This is not a discussion forum nor a chat room. When you have a further question, the best way is usually to open a new question page, in which you can use links to relate to previous questions of yours. $\endgroup$
    – John L.
    Feb 19 at 8:23
  • 1
    $\begingroup$ @coolest10: Are you familiar enough with the rigorous definition of TMs? If so, then move on to the definition of oracle TMs as mentioned by JohnL., and note that your guess-number problem can easily be represented by having ask be an oracle TM $A$, in which case find_unknown_number would be represented by a TM $F$ relative to ask. So the guess is not in the input tape of $F$, since it is inside the oracle $A$. There are other natural extensions of the TM model to support encrypted tapes, but oracle TMs are clearly the right way the view this guess-number problem. $\endgroup$
    – user21820
    Feb 19 at 9:18

6 Answers 6

17
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ Please do not place exercises in answers. This is not the place to give exercise, now I am dealing with the question "wat is the mode popular model of computation?" and I did not have a course on computer science in a long time. Please do not introduce new unanswered exercises in answers. $\endgroup$
    – Cheiron
    Feb 20 at 14:55
  • $\begingroup$ @Cheiron, exercises are purely optional for you. My answer is complete without the exercise. Please ignore the exercise if you do not want to reinforce what is being taught here. Be content with yourself once you have understood the answer even if you missed the exercise. $\endgroup$
    – John L.
    Feb 20 at 15:05
  • $\begingroup$ If part of your answer can be ignored without loss of information, should that part of your answer not be removed? I just do not agree with the tone here, what if I conclude that the most popular model of computation must be the DFA (any other model requires something infinite after all!) I walk away with wrong information from your answer. Is that really what we want? $\endgroup$
    – Cheiron
    Feb 20 at 15:13
  • $\begingroup$ @Cheiron, yes and no. Let us chat at this chat room, an unanswered exercise is included in an answer. $\endgroup$
    – John L.
    Feb 20 at 16:22
  • $\begingroup$ @JohnL. re: most popular model of computation: is "register machine" the answer you're looking for? $\endgroup$ Feb 21 at 1:31
5
$\begingroup$

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.
$\endgroup$
4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ As I can understand, in your case, the chromatic variable would be deductible from the graph you design, so it would not need to be given as input. The only difference I see between the 2 problems exposed (yours and mine) is that in my case, the "guess" variable could vary in the low-high interval, whereas in your case, the chromatic number "x" is fixed i.e. there can only be one minimum number of colors per graph. Please correct me if I am wrong and try to refer to the answer of @YvesDaoust above + tell me your opinion on the correctness of his statement. Thank you very much! $\endgroup$
    – coolest 10
    Feb 17 at 16:59
  • 1
    $\begingroup$ I think you have misunderstood the point of your exercise. The exercise describes how to compute a value $x$ given that you can answer questions of the form "$x \leq b?$", and this is useful since sometimes there is a natural algorithm for the latter but no direct algorithm for the former. The problem is framed using an artificial ploy, but this should be ignored rather than given the spotlight. $\endgroup$ Feb 17 at 17:04
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Instead of a "traditional" hash, use a math function that is strictly increasing on the given domain and difficult to invert. Like a 5th degree polynomial. This preserves the needed relationship for a binary search. $\endgroup$
    – jaxad0127
    Feb 18 at 1:52
  • $\begingroup$ Preserving a relationship makes a solvable problem easier. $\endgroup$
    – Rob
    Feb 18 at 15:20
2
$\begingroup$

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.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.