Re:Show HN: You can program without loop and recursion and×÷...
by FooBarBizBazz on Sunday July 21, 2024 @03:50PM
(#41027619)
This doesn't look Turing complete to me.
This should be able to interpret programs written in other Turing-complete languages, including in itself.
I was about to say, "choose an encoding for this language in terms of integers that it understands, and then show me an interpreter that can run any program so encoded". But we have another more basic problem first. As others have noted, there is no notion of program input.
Well, fine, we can solve that easily enough. Suppose that at the start of your program you have a variable called "in" containing a single integer of arbitrary size.
Now choose an encoding of these programs into integers, and show a program that will run one of them.
I assert that it isn't possible.
In fact, I think I even have a sketch at a proof. We know that Turing machines have an "undecideability" property, i.e., you can't know in general whether any given program will terminate. But we can prove that any program in this language terminates.
To do that we will need to be a little more formal about exactly what this language is. I think a reasonable choice would be to say that programs are written in static single assignment (SSA) form using only those functions. It is trivial to show that the program terminates in a number of steps equal to the number of lines of the program.
...
Is this post actually a clever troll to make the point that there's only so much that a feedforward neural net can do?
This should be able to interpret programs written in other Turing-complete languages, including in itself.
I was about to say, "choose an encoding for this language in terms of integers that it understands, and then show me an interpreter that can run any program so encoded". But we have another more basic problem first. As others have noted, there is no notion of program input.
Well, fine, we can solve that easily enough. Suppose that at the start of your program you have a variable called "in" containing a single integer of arbitrary size.
Now choose an encoding of these programs into integers, and show a program that will run one of them.
I assert that it isn't possible.
In fact, I think I even have a sketch at a proof. We know that Turing machines have an "undecideability" property, i.e., you can't know in general whether any given program will terminate. But we can prove that any program in this language terminates.
To do that we will need to be a little more formal about exactly what this language is. I think a reasonable choice would be to say that programs are written in static single assignment (SSA) form using only those functions. It is trivial to show that the program terminates in a number of steps equal to the number of lines of the program.
...
Is this post actually a clever troll to make the point that there's only so much that a feedforward neural net can do?