-1
$\begingroup$

Imagine we have a program which does an infinite loop: while(true){loop}

We run the program on a linux machine(assume the compilation is ok), then this linux machine becomes an universal turing machine which run the program.

Questions are :

1.Does the linux machine recognize the infinite program? Why?

2.Does the linux machine decide the infinite program? Why?

The definition of Recognizable and Decidable(https://math.stackexchange.com/a/25808/677513):

A language is Recognizable iff there is a Turing Machine which will halt and accept only the strings in that language and for strings not in the language, the TM either rejects, or does not halt at all. Note: there is no requirement that the Turing Machine should halt for strings not in the language.

A language is Decidable iff there is a Turing Machine which will accept strings in the language and reject strings not in the language.

According to the definition of 'recognizable', the linux machine does not recognize the loop program, so the linux machine loop forever on the program. But this is counter-intuitive.

$\endgroup$
  • 4
    $\begingroup$ I am afraid that your question is incomplete. Have you followed the definition of "recognize" and "decide" in your textbook or course material carefully? For example, you should mention what are the accepting states of the linux machine when it is considered as a Turing machine. I would like to encourage you to study slowly. The slower, the faster. $\endgroup$ – Apass.Jack Jul 23 at 4:03
  • $\begingroup$ @Apass.Jack for 'recognize' and 'decide', please refer to math.stackexchange.com/a/25808/677513 I will update the question. $\endgroup$ – Anonemous Jul 23 at 4:07
  • 1
    $\begingroup$ @Evil No, I am just confusing about this problem. $\endgroup$ – Anonemous Jul 23 at 7:47
  • 1
    $\begingroup$ The point is, you should define the behavior of accept for the linux machine. $\endgroup$ – xskxzr Jul 23 at 14:06
  • 1
    $\begingroup$ It looks like this is the kind of question where the question asker is not able to clarify the question because, that is part of the question! An answer could be written to explain the meaning of "Recognizable" and "Decidable" as well as how to view a linux machine as a (universal) Turing machine that accepts programs reasonably, informally or formally. Hence, I will vote to leave this question open. $\endgroup$ – Apass.Jack Jul 23 at 18:21
2
$\begingroup$

The question doesn't make sense. Recognizability and decidability don't apply to a program. You're confusing several different concepts: languages, strings, programs.

A Turing machine operates on a string. A string is a finite sequence of symbols. A symbol is a member of a finite alphabet, for example the alphabet of 8-bit bytes (binary programs are written in this alphabet), or the alphabet of ASCII characters (most programming language source code is written in this alphabet).

A Turing machine recognizes a language. A language is a set of strings. This set can be finite or infinite. Some example languages are: the set of every string; the empty set; the singleton set containing only one particular string; the set of strings of length 3; the set of ASCII strings where the characters ( and ) are balanced; etc.

Imagine we have a program which does an infinite loop: while(true){loop}

Ok. This is not an “infinite program”. while(true){loop} is a 17-character ASCII string, which presumably has a meaning in some fictional programming language. The meaning of this string is a program that runs forever without consuming any input or emitting any output. So it's a non-terminating program.

If you compile it for a computer, you'll get a new string which is a binary executable. This is still a string, i.e. a finite sequence of symbols, this time on the alphabet of 8-bit bytes (assuming an 8-bit computer).

We run the program on a linux machine(assume the compilation is ok), then this linux machine becomes an universal turing machine which run the program.

Ok. You can consider the computer as a Turing machine that takes binary programs as inputs and whose behavior is to run the program. On this particular program, the Turing machine does not halt. The Turing machine does not accept or reject this particular program.

The Turing machine is not fully defined because you haven't defined which inputs it accepts. Here are a few examples of complete definitions of Turing machines that fit this mold. (I haven't fully formalized these definitions, but they're complete in the sense that I'm fully describing what the machine does. Note that they're still incomplete in the sense that each of them could be implemented in many different ways.) All of these machines take a program as input and run it without passing it any input (and don't halt if the program doesn't), then do something else.

  • Accept the program. This machine accepts all inputs that encode terminating programs, and does not halt on inputs that represent non-terminating programs.
  • Accept if the program emitted any output, and reject otherwise.
  • Accept if the program emitted a prefix of the decimal representation of $\pi$, and reject otherwise. Note that since the program halted, it can only print a finite sequence of digits. If the input is program that keeps printing digits forever, the Turing machine doesn't halt.
  • Accept if the program ran for an even number of clock cycles, and reject if the program ran for an odd number of clock cycles.
  • After running the program, loop forever. This machine doesn't halt on any input.

Each of these machines recognizes a different language: the language of terminating programs; the language of programs terminate and don't produce any input; the language of terminating programs that print a finite prefix of the decimal representation of $\pi$; the language of programs that run for an even number of clock cycles; the empty language. None of these machines decide any language, since they don't halt on every input.

Where things get really interesting is when you consider Turing machines that take (an encoding of) a program as input, and do things other than run it. That's the only way of getting interesting results about non-terminating programs. Here are a few possible behaviors for a Turing machine that takes a program as input:

  • Run the program for 1,000,000,000 clock cycles at most, and accept it iff it terminates before the timeout. This machine decides programs that terminate within a certain time.
  • Run the program for 1,000,000,000 clock cycles at most, and accept it iff it doesn't print any output. This machine decides programs with empty output that terminate within a certain time.
  • Accept the program iff its length is even. This machine decides the language of even-length programs.
  • Search for a termination or non-termination proof for the program. Accept the program if a termination proof is found, reject it if a non-termination proof is found. Don't halt as long as the search hasn't found anything — since there are infinitely many potential proofs, there's no guarantee that the search will ever terminate. Such a machine recognizes the language that is composed of programs that terminate. The unsolvability of the halting problem states that such a machine cannot halt on every input: the language of terminating programs is not Turing-decidable.
$\endgroup$
  • $\begingroup$ Assume the language contains only the binary executable sequence(infinite loop). So the linux machine does not recognize nor decide the binary executable sequence language. right? $\endgroup$ – Anonemous Jul 24 at 8:08
  • $\begingroup$ @Anonemous If the Linux machine runs the program, it can't decide anything, since it doesn't halt on every input. What it recognizes depends on how you define acceptance. A Turing machine can behave in one of three ways for each given input: accept, reject, or not-halt. If the machine runs the program, then compares the program binary to a fixed string, it recognizes but does not decide the singleton language containing this string. You could make a machine that does not run the program and just compares the binary: this machine would decide the singleton language. $\endgroup$ – Gilles Jul 24 at 8:59
  • $\begingroup$ According to the definition, recognizes means 'Turing Machine which will halt and accept only the strings in that language and for strings not in the language, the TM either rejects, or does not halt at all.' hence the linux machine loop forever on the binary sequence language, so the binary sequence language must not belong to the language which recognized by the linux machine. Right? $\endgroup$ – Anonemous Jul 24 at 9:20
  • $\begingroup$ Good answer! +1. $\endgroup$ – Apass.Jack Jul 24 at 11:47
  • 1
    $\begingroup$ @Apass.Jack Yes, I am reading it, currently on Chapter-5. $\endgroup$ – Anonemous Jul 24 at 11:56

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.