Talk:Turing-complete

Computing the Ackermann function doesn't ensure Turing-completeness

I've removed the following incorrect statements from the article:

"In order to compute the Ackermann function for any values of m and n, however, a Turing-complete system is required. It is this meaning of Turing-complete which is more significant; if some computational system that can solve problems of size n can also always solve the same problems for size n+1, that system is Turing-complete."

One counterexample is the existence of languages in which all programs halt — so the language cannot be Turing-complete — yet can compute the Ackermann function (which is total). E.g., see Functions computable by total Turing machines.

Other counterexamples are languages constructed by modifying a Turing-complete language so it can only compute functions that never exceed some selected very-fast-growing computable function that everywhere exceeds the Ackermann function. Then it can compute Ackermann's function, but is not Turing-complete (because there are recursive functions, growing faster than the selected one, that it can't compute). --r.e.s. (Talk) 08:49, 17 November 2007 (UTC)

Or, of course, HQ9+ modified to add an Ackermann command. --ais523 13:13, 19 November 2007 (UTC)

Since HQ9+ is a joke language, I suppose you meant that as a joke (in the same sense as "add an Omega command" to magically compute Chaitin's Omega, for example. OTOH, it does suggest trivial counterexamples (which is what you might have intended); e.g., just take any language that has an Ack program in it, and restrict the language to that program alone — a one-program language. --r.e.s. (Talk) 19:54, 20 November 2007 (UTC)

I was trying to bring up the point of trivial counterexamples. HQ9+ is a joke, but it is quite mathematically interesting as a model for trivial counterexamples. Likewise, that sort of program gives a trivial proof that there are an infinite number of computational classes (some of which are more interesting than others). --ais523 10:35, 21 November 2007 (UTC)

incorrect description in terms of C

In the middle of the "Overspecification" section, we have:

"An interesting example of this is the C programming language; if, as the specification would seem to entail, sizeof(void*) must be finite, then it cannot be Turing-complete, because it cannot address an unbounded storage space."

This is an error. First, while it's true that a "void *" is a pointer, it points to nothing. Second, sizeof() on a pointer returns the size of the pointer, not the size of what the pointer points to. This author seems to be confusing the size of a regions of memory allocated to a type with the size of the type itself. It is true that sizeof() must return an integer value (an unsigned integer size_t for ANSI C, int or long for traditional C) which is of a limited range. This proves the inability of a C implementation to address an unbounded storage space. --(this comment by [[User:{{{2}}}|{{{2}}}]] at 00:27, 11 November 2009 98.243.106.85 UTC; please sign your comments with ~~~~)

There's nothing about C itself that says it needs to use two's complement integers (sign-magnitude and one's compliment can work, dc's source code even has a routine for that), or 8-bit bytes (the PDP-10 used bytes from 1-36 bits, usually 9), or even binary bytes (ternary, quinary, and decimal also work). For example, the IBM 1401 used decimal numbers not only for math, but for memory addresses. The "Tunguska" emulator has 3CC, a ternary C compiler. There's also no reason why sizeof(void *) has to equal sizeof(int) or sizeof(long) or why pointers can't be floats. Nvidia GPUs actually use float pointers[1] see: "Chapter 32 of this book discusses important limitations and errors associated with using floating-point rather than integer addresses, and those problems apply to the techniques presented in this section." The only problem is that C's pointer size depends on the size of the underlying computer, not the C language. Another possibility, if a computer supported bignum bytes, then it could still have a sizeof(void *) of 1, but that one "byte" can hold any integer value. An array of void * would then have a size of 1*(number of array elements), which can be infinity if it contained an infinite number of elements. And this is a rather interesting discussion about C pointers. Ian 22:21, 12 September 2010 (UTC)

Yes, I too have concluded that C is Turing-complete without the standard library, and with infinite-sized chars. (Of course, this only proves one particular variant of C Turing-complete -- C is actually a hugely varied family of languages in disguise, parametrised on a whole host of things.) Unfortunately, this cannot prove hosted C Turing-complete, because the standard library has the CHAR_BIT macro in limits.h. —ehird 18:32, 24 May 2011 (UTC)

Also, if you include the standard library, C is Turing-complete, even with a finite pointer size. The standard library is defined as part of the C standard, but itself cannot be implemented in pure C without inline assembly or non-portable compiler intrinsics (e.g. the <tgmath.h> and <setjmp.h> functions). With a file as a "tape" (on an unbounded storage medium) you can simulate a Turing Machine with FILE stream functions like fseek(), fread() and fwrite(). Functions like ftell() and fstat() are allowed to return EOVERFLOW if the file size or current position can't fit into the return data type. The only difficulty is that you can't fit the entire tape in memory at once (limited by SIZE_MAX) or seek to an absolute position. Ian 06:13, 24 May 2011 (UTC)

Yes, indeed, this is a viable way of proving hosted C Turing-complete. I think you can prove both unhosted and hosted C potentially Turing-complete (i.e. two members of the family, whose only difference is that one is hosted and one is unhosted, Turing-complete) using recursion and possibly setjmp/longjmp, but I'm not sure. —ehird 18:32, 24 May 2011 (UTC)

More incorrect

C is Turing-complete (but not its any implementation) because:

1. It is possible to write an interpreter of a universal Turing machine in C

OR

2. It is TC because its subset (e.g. without sizeof) is TC

Here is from http://www.iwriteiam.nl/Ha_bf_Turing.html

A language is said to be 'Turing-complete', if for each functions that can be calculated with a Turing Machine, it can be shown that there is a program in this language that performs the same function. There are basically three approaches to proof that a language is Turing-complete. These are:

1. Show there is some mapping from each possible Turing machine to a program in the language.

2. Show that there is a program in the language that emulates a Universal Turing Machine.

3. Show that the language is equivalent with (or a superset of) a language that is known to be Turing-complete.

--Oleg 06:28, 11 November 2009 (UTC)

Unbounded program length

If a language stores information in the programs source code (self-modifying) and is turing-complete except for the memory, and allows unbounded program length ("infinite"-stream too), is it turing-complete? --TehZ

If memory other than the source-code is limited, but in that case the read/write memory is in fact, unbounded, if it can read/write its unbounded source-codes? --Zzo38 19:58, 23 January 2011 (UTC)