4 ms·

It is not that simple. I have a little problem with finding comprehensive definition of Turing completeness - in order to decide if certain machine is turing co

It is not that simple. I have a little problem with finding comprehensive definition of Turing completeness - in order to decide if certain machine is turing complete does one have to prove that it can also simulate infinite, not halting algorithms? If yes, then not being able to re-enter old states disqualifies C preprocessor as a turing complete machine by considering simple machine that goes left and right till the end of time. However, is it really an algorithm? If there is no output one could simply replace that with just empty machine that halts for sure, therefore it can be simulated in C preprocessor. On the other hand, if this is not requirement then we know that every algorithm we have to simulate to prove turing completeness halts eventually, there is no ability to re-enter old states but if algorithm halts we could just add enough more states (finitely many) that allows it to finish.

throwaway82740 13y ago
I would look at it a slightly different way. It's not that the definition of Turing completeness explicitly says that a language must be able to simulate "infinite" algorithms. It's that it must be able simulate what a Turing machine can do. Turing machines are quite capable of running non-halting algorithms, so the language must be able to as well. Contrived example: One algorithm a Turing machine could perform would be to write the characters "TM" every two cells on its entire tape. The tape is unbounded, so this algorithm is, colloquially speaking, infinite. Clearly, you cannot simulate this with a halting machine like the C preprocessor.
- ithinkso 13y ago
  This is exactly the problem I was talking about. In every definition I've read there was strict condition that set of all possible states Q is non-empty (and finite). But there is difference in definition of set of final states. In [1] there is a comparison - in columns labeled "Peter Linz" and "Wikipedia" F is defined as subset of Q. This implies that it also could be empty, although in column labeled "Michael Sipser" there is a special state q_accept that explicitly exist in Q, therefore F is not-empty. Unfortunately there is no information if q_accept has to be reachable from start state. But consider this: How one could say that this machine is actually writing "TM" every two cells? If you investigate tape states while machine is still running it might change (on meta-level you my expect that this is actually true but you might for example make some bug that you're not aware of). The only way to be able to see that "TM" has been written is after the machine halts. [1] http://www.cis.upenn.edu/~matuszek/cit596-2012/NewPages/turing-machine-definitions.html http://www.cis.upenn.edu/~matuszek/cit596-2012/NewPages/turi...
lisper 13y ago
> I have a little problem with finding comprehensive definition of Turing completeness http://lmgtfy.com/?q=turing+completeness http://lmgtfy.com/?q=turing+completeness > in order to decide if certain machine is turing complete does one have to prove that it can also simulate infinite, not halting algorithms? Yes.
- ithinkso 13y ago
  > Yes And you're saying this based on what? Thanks for googling this for me, although the key-word was "comprehensive" not any definition.
  - lisper 13y ago
    Ah, then what you're looking for is a comprehensive description, not a comprehensive definition. (I gather your native language is not English?) For that you will have to read a book on computability theory (at least -- it depends on just how "comprehensive" you want to get). > And you're saying this based on what? Based on the definition of Turing-completeness, and the (trivial) fact that there exist Turing machines that do not halt. A Turing-complete system is, by definition, a system that can emulate any Turing machine. Because some Turing machines don't halt, any system that never halts cannot emulate a Turing machine that does not halt, and so by definition is not Turing-complete.
    - ithinkso 13y ago
      You're right, maybe I do not understand because of different meaning of those words in english, which is not, in fact, my native language, but let me try explain you what I think. From wikipedia we read: Turing completeness A computational system that can compute every Turing-computable function is called Turing complete (or Turing powerful). Alternatively, such a system is one that can simulate a universal Turing machine. From the first part I think compute means that from some input A there is output B. It is later explained in 'computable function' article: Each computable function f takes a fixed, finite number of natural numbers as arguments. Note that the functions are partial in general, i.e. they may not be defined for every possible choice of input. If a computable function is defined for a certain input, then it returns a single natural number as output (this output can be interpreted as a list of numbers using a pairing function). So if computable function is returning something that means it halts. We are able to compute every halting algorithm in preprocessor hence it is turing complete. Second part of this definitions says that one has to simulate turing machine (and uses the word 'alternatively' so basically it has to be the same but I can go anyway). I think that 'simulate' in this context mean 'producing same output' rather than 'doing step by step the same'. Internal tape states at certain point in time should not matter because while running they might change (or if they matter we could just return list of pair {state,time} at the end). There is no doubt that non-halting turing machines exists but I'm not sure if that apply to this particular problem anyhow since they are not computing anything.

throwaway82740 13y ago

I would look at it a slightly different way. It's not that the definition of Turing completeness explicitly says that a language must be able to simulate "infinite" algorithms. It's that it must be able simulate what a Turing machine can do. Turing machines are quite capable of running non-halting algorithms, so the language must be able to as well. Contrived example: One algorithm a Turing machine could perform would be to write the characters "TM" every two cells on its entire tape. The tape is unbounded, so this algorithm is, colloquially speaking, infinite. Clearly, you cannot simulate this with a halting machine like the C preprocessor.

ithinkso 13y ago
This is exactly the problem I was talking about. In every definition I've read there was strict condition that set of all possible states Q is non-empty (and finite). But there is difference in definition of set of final states. In [1] there is a comparison - in columns labeled "Peter Linz" and "Wikipedia" F is defined as subset of Q. This implies that it also could be empty, although in column labeled "Michael Sipser" there is a special state q_accept that explicitly exist in Q, therefore F is not-empty. Unfortunately there is no information if q_accept has to be reachable from start state. But consider this: How one could say that this machine is actually writing "TM" every two cells? If you investigate tape states while machine is still running it might change (on meta-level you my expect that this is actually true but you might for example make some bug that you're not aware of). The only way to be able to see that "TM" has been written is after the machine halts. [1] http://www.cis.upenn.edu/~matuszek/cit596-2012/NewPages/turing-machine-definitions.html http://www.cis.upenn.edu/~matuszek/cit596-2012/NewPages/turi...

lisper 13y ago

> I have a little problem with finding comprehensive definition of Turing completeness http://lmgtfy.com/?q=turing+completeness http://lmgtfy.com/?q=turing+completeness > in order to decide if certain machine is turing complete does one have to prove that it can also simulate infinite, not halting algorithms? Yes.

ithinkso 13y ago
> Yes And you're saying this based on what? Thanks for googling this for me, although the key-word was "comprehensive" not any definition.
- lisper 13y ago
  Ah, then what you're looking for is a comprehensive description, not a comprehensive definition. (I gather your native language is not English?) For that you will have to read a book on computability theory (at least -- it depends on just how "comprehensive" you want to get). > And you're saying this based on what? Based on the definition of Turing-completeness, and the (trivial) fact that there exist Turing machines that do not halt. A Turing-complete system is, by definition, a system that can emulate any Turing machine. Because some Turing machines don't halt, any system that never halts cannot emulate a Turing machine that does not halt, and so by definition is not Turing-complete.
  - ithinkso 13y ago
    You're right, maybe I do not understand because of different meaning of those words in english, which is not, in fact, my native language, but let me try explain you what I think. From wikipedia we read: Turing completeness A computational system that can compute every Turing-computable function is called Turing complete (or Turing powerful). Alternatively, such a system is one that can simulate a universal Turing machine. From the first part I think compute means that from some input A there is output B. It is later explained in 'computable function' article: Each computable function f takes a fixed, finite number of natural numbers as arguments. Note that the functions are partial in general, i.e. they may not be defined for every possible choice of input. If a computable function is defined for a certain input, then it returns a single natural number as output (this output can be interpreted as a list of numbers using a pairing function). So if computable function is returning something that means it halts. We are able to compute every halting algorithm in preprocessor hence it is turing complete. Second part of this definitions says that one has to simulate turing machine (and uses the word 'alternatively' so basically it has to be the same but I can go anyway). I think that 'simulate' in this context mean 'producing same output' rather than 'doing step by step the same'. Internal tape states at certain point in time should not matter because while running they might change (or if they matter we could just return list of pair {state,time} at the end). There is no doubt that non-halting turing machines exists but I'm not sure if that apply to this particular problem anyhow since they are not computing anything.