3 ms·

I don't think Turing-Complete is much of a barrier anymore. I could write a Turing Machine in QBasic, or Java, or MineCraft. Ok, I couldn't do it in minecraft

by drakaal 13y ago

I don't think Turing-Complete is much of a barrier anymore. I could write a Turing Machine in QBasic, or Java, or MineCraft. Ok, I couldn't do it in minecraft cause I don't play, but I know that it is possible to do in minecraft. I could probably simulate a turing machine on a TI-81 graphing calculator depending on if it fit in memory. Saying something is Turing Complete is kind of like saying "Could you write a Nintendo emulator" for it. Once you get beyond a certain level of computational power and memory, you can, even if it would be very slow.

derleth 13y ago
> I could probably simulate a turing machine on a TI-81 graphing calculator depending on if it fit in memory. Depending on how you define 'Turing-equivalent' this is never a problem: Something is Turing-equivalent if and only if you always have enough memory for the current computation. Note that you do not have infinite memory, merely sufficient memory, another pedantic distinction sometimes harped upon. The above distinctions are frequently disregarded in actual conversations because they reduce a useful term to something which can only have application to the most theoretical parts of Computer Science. Finally, a third distinction: Problems are Turing-complete. Machines are Turing-equivalent. Cite: http://scienceblogs.com/goodmath/2007/01/05/turing-equivalent-vs-turing-co/ http://scienceblogs.com/goodmath/2007/01/05/turing-equivalen...
- mdxn 13y ago
  Your definitions of Turing-Complete and Turing Equivalent, as phrased, are incorrect or perhaps mistaken to some extent. I don't want to Arbitrarily scalable memory is just one necessary component for Turing-equivalence to a Turing Machine. Two machines are Turing Equivalent when they can simulate each other. Not that this does not necessarily extend to general computation and can actually be a limited for of such. Countably unbounded memory is not necessarily a requirement (ex. some symbolic systems), but might as well be for the class of machines that you are thinking of. A lot of models of computation become Turing-complete when they receive this benefit. You also need to keep in mind that some automata can have infinite memory, but don't have the ability to take advantage of it. Straightforward examples include pushdown automata and time bounded machines. Machines that do not have a logically complete algebra will also have this problem. I complete agree with you about the "finite memory" objection people like to use. I find it incredibly annoying and not very productive. It is almost ignorant to discussion going on as they are completely missing the point. It's insulting that they think others don't realize this. I'm glad someone else (you) here shares this feeling. :) I believe you meant that problems can be R.E.-complete (semidecidable in a complete way; ex. Halting problem). The term, Turing Complete, is inapplicable in this situation. It describes properties of a formal system and/or model of computation (which I'm certain you knew).
jlgreco 13y ago
> I could probably simulate a turing machine on a TI-81 graphing calculator depending on if it fit in memory. Well of course. A TI-81 is "a computer" in the layman's sense of the term. It has a general purpose Zilog z80 processor that can be programmed by the end user with a BASIC dialect, and (recently, with a exploit discovered in TI's software on it) with z80 assembly. Pointing out that a TI-81 is Turing equivalent is like pointing out that an iPhone is Turing equivalent. It was never pretending not to be.
lifeformed 13y ago
The point of this is that these things are entirely not intended to be computational systems, yet just through their complexity they ended up being Turing Complete unintentionally.

by drakaal 13y ago

derleth 13y ago

> I could probably simulate a turing machine on a TI-81 graphing calculator depending on if it fit in memory. Depending on how you define 'Turing-equivalent' this is never a problem: Something is Turing-equivalent if and only if you always have enough memory for the current computation. Note that you do not have infinite memory, merely sufficient memory, another pedantic distinction sometimes harped upon. The above distinctions are frequently disregarded in actual conversations because they reduce a useful term to something which can only have application to the most theoretical parts of Computer Science. Finally, a third distinction: Problems are Turing-complete. Machines are Turing-equivalent. Cite: http://scienceblogs.com/goodmath/2007/01/05/turing-equivalent-vs-turing-co/ http://scienceblogs.com/goodmath/2007/01/05/turing-equivalen...

mdxn 13y ago
Your definitions of Turing-Complete and Turing Equivalent, as phrased, are incorrect or perhaps mistaken to some extent. I don't want to Arbitrarily scalable memory is just one necessary component for Turing-equivalence to a Turing Machine. Two machines are Turing Equivalent when they can simulate each other. Not that this does not necessarily extend to general computation and can actually be a limited for of such. Countably unbounded memory is not necessarily a requirement (ex. some symbolic systems), but might as well be for the class of machines that you are thinking of. A lot of models of computation become Turing-complete when they receive this benefit. You also need to keep in mind that some automata can have infinite memory, but don't have the ability to take advantage of it. Straightforward examples include pushdown automata and time bounded machines. Machines that do not have a logically complete algebra will also have this problem. I complete agree with you about the "finite memory" objection people like to use. I find it incredibly annoying and not very productive. It is almost ignorant to discussion going on as they are completely missing the point. It's insulting that they think others don't realize this. I'm glad someone else (you) here shares this feeling. :) I believe you meant that problems can be R.E.-complete (semidecidable in a complete way; ex. Halting problem). The term, Turing Complete, is inapplicable in this situation. It describes properties of a formal system and/or model of computation (which I'm certain you knew).

jlgreco 13y ago

> I could probably simulate a turing machine on a TI-81 graphing calculator depending on if it fit in memory. Well of course. A TI-81 is "a computer" in the layman's sense of the term. It has a general purpose Zilog z80 processor that can be programmed by the end user with a BASIC dialect, and (recently, with a exploit discovered in TI's software on it) with z80 assembly. Pointing out that a TI-81 is Turing equivalent is like pointing out that an iPhone is Turing equivalent. It was never pretending not to be.

lifeformed 13y ago

The point of this is that these things are entirely not intended to be computational systems, yet just through their complexity they ended up being Turing Complete unintentionally.