Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

May you can help me out with my problems with source codes. Well first of all we proved that for recursive functions $N:\mathbb N^2\rightarrow \mathbb N$ and $A^k: \mathbb N^k\rightarrow \mathbb N$ and for every goto programm (I am not 100% sure, but I think this is identical to a turing machine) there exist a source code $\mathcal{P}=<p_0,...,p_{L-1}>$ where $L$ is the number of lines of the program and $p_i$ is the code of the i-th line.

Question: How to construct a simple universal program $U$? I.e a program which delivers the ouput for the input $(\mathcal{P},n)$, this is what the program $P$ would give for the input $n$

This is nothing more than a goto-interpreter, similar to a java-interpreter, but what about a formal argument, why this program exist?

EDIT: Next to my original question (the construction of $U$), two other questions arises:Let $f(n)$ is the output of the universal program $U$ on the input $(n,n)$. Is $f$ recursiv? Same with $g(n)=f(n)+1$. Is it recursiv?

share|improve this question
    
If you are not sure if goto programms are the same as Turing machines, can you at least give a precise definition of goto program? –  Hagen von Eitzen May 15 '13 at 21:34
    
If you are interested in the source (it is in german), you find the document here: logic.univie.ac.at/~adler/docs/gml.pdf on page 30. In general we defined a goto program as a loop program (see here en.wikipedia.org/wiki/LOOP_%28programming_language%29) but instead using loops we use goto statements (=jump instructions). We replaced loops by "if x goto 42", which means the program jumps to line 42 if x holds. –  Babla May 15 '13 at 21:38

2 Answers 2

up vote 2 down vote accepted

You have to be a bit careful with asking "is $f(n)$" recursive, where $f(n) = U(n,n)$ and $U$ is a universal GOTO program (or recursive function or turing machine or whatever).

$f$ isn't total, so if you distinguish between recursive and partially recursive functions, it's obviously not recursive. It's partially recursive though, since every GOTO program (or turing machine or recursive function or whatever) is.

share|improve this answer
    
How do you know that f is not total? –  Babla May 16 '13 at 8:28
    
@Babla Let $n$ be the code of the program "1: IF TRUE GOTO 1". THen $U(n,x) = \bot$ ($\bot$ means undefined) for every $x$, thus $U(n,n) = \bot$ and so $f(n)=\bot$ –  fgp May 16 '13 at 8:38
    
Thank you. But this would mean that the function $g(n)=f(n)+1$ is indeed recursiv because it always goes one step further, right? –  Babla May 16 '13 at 8:42
    
No, because $\bot+1=\bot$ in a way. If you try to evaluate $g$ at $n$, you first have to evalutate $f(n)$. But you never finish doing that, you just keep on going. So the "+1" part never actually takes place, $g$ never finishes either, no result is produced, hence the value is $\bot$. –  fgp May 16 '13 at 8:45
    
Ok, that makes sense, so we know it is not recursiv, but is there a goto program for $g(n)$, or differently formulated: Let A be the source code, what U(A,A) mean? –  Babla May 16 '13 at 8:48

Quote from Wikipedia: "To show that something is Turing complete, it is enough to show that it can be used to simulate some Turing complete system. For example, an imperative language is Turing complete if it has conditional branching (e.g., "if" and "goto" statements, or a "branch if zero" instruction. See OISC) and the ability to change arbitrary memory locations (e.g., the ability to maintain an arbitrary number of variables). Since this is almost always the case, most if not all imperative languages are Turing complete if we ignore any limitations of finite memory"

share|improve this answer
    
I still do not see how we can construct an universal goto program now, may you can show me how to do that formally? –  Babla May 15 '13 at 22:19
    
I don't think that is trivial (I mean simple), but I might be wrong. I don't know how to do it. Actually, it is not that difficult: you can use the definition of any known universal Turing machine (many examples on the web) and make a Java program that simulates it! –  julian fernandez May 15 '13 at 22:21
    
Even if counter intuitive (at least at the beginning), the rule 110 cellular automata is universal. –  julian fernandez May 15 '13 at 22:35
    
Thanks, but still, the proof of universality of rule 110 is not so easy, I guess there must be a much simpler goto interpreter $U$ that delivers an output for an input $(\mathcal{P},n)$ –  Babla May 15 '13 at 22:41
    
I agree. Actually, I am not sure how complex is the translation of a simple simulated universal TM (easy to implement) to the code that maps it to an arbitrary machine (P,n). I guess you'll have to wait until somebody with more knowledge writes an answer. If you don't get an answer in a couple of days, perhaps you could try to ask the question in a more specific way, such as: How to...? –  julian fernandez May 15 '13 at 22:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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