2 added 153 characters in body
source | link

Your construction seems a bit tautological. The if statement is itself a form or branching through an array of two addresses, depending on a value that is 0 or 1. Actually, the if statement generalizes to the case statement, which may be implemented as branching through an array. Whether the array is code or static data is immaterial and pretty much in the eyes of the beholder.

Another way to state this is that your program could be simulated byyour program could be simulated by a Turing machine, which does not have any if statement, and could thus be a positive answer to your question.

Indeed, a Turing Turing machine, which does not have should be as good an if statement,answer as any more that a FSA has if statementsother state machine. What the TM has, that theCompared to a FSA does not, the only difference is an infinite tape on whichthat it can read and write on an infinite tape.

So, if you do not accept the Turing machine as an answer, I am wonderingwonder whether your problem is not more with eliminating this infinite memory tape, at the expense of replacing it with an infinite program (statesTM states and transitions).

Then, I am afraid you may just fall into something similar to a Turing Tar Pit, or much worse (a Turing hell  ?).

The main point is that the technique you are proposing will require your program to have an infinite size, if it is to be equivalent to the original program, using infinite matrices, i.e. really an infinite number of states.

You might not worrry about it, considering that we already work as if we could use unbounded integer in memory. That is true, but we use integer in a very precise way, that is finitely described. As a consequence, it is perfectly possible to mimic computation with arbitrary long integer, and it is actually done in some systems.

One fundamental principle of computer science (and I would add mathematics, but that has to be made precise) is that everything must be finitely definable.

To make any sense, your infinite program would similarly have to follow a finite specification, where your if statement would be back, or the TM with its infinite tape.

If you forget this constraint, then you drastically change the domain of discourse, as you get a continuous (rather than denumerable) infinity of different programs. You are no longer talking of computability with its accepted meaning, and its physical realizability. Actually, I suspect that you can then no longer consider a concept that would ressemble computability (but that is a somewhat fuzzy statement).

Your construction seems a bit tautological. The if statement is itself a form or branching through an array of two addresses, depending on a value that is 0 or 1. Actually, the if statement generalizes to the case statement, which may be implemented as branching through an array. Whether the array is code or static data is immaterial and pretty much in the eyes of the beholder.

Another way to state this is that your program could be simulated by a Turing machine, which does not have an if statement, any more that a FSA has if statements. What the TM has, that the FSA does not, is an infinite tape on which it can read and write.

So, I am wondering whether your problem is not more with eliminating this infinite memory tape, at the expense of replacing it with an infinite program (states and transitions).

Then, I am afraid you just fall into something similar to a Turing Tar Pit, or much worse (a Turing hell  ?).

The main point is that the technique you are proposing will require your program to have an infinite size, if it is to be equivalent to the original program, using infinite matrices, i.e. really an infinite number of states.

You might not worrry about it, considering that we already work as if we could use unbounded integer in memory. That is true, but we use integer in a very precise way, that is finitely described. As a consequence, it is perfectly possible to mimic computation with arbitrary long integer, and it is actually done in some systems.

One fundamental principle of computer science (and I would add mathematics, but that has to be made precise) is that everything must be finitely definable.

To make any sense, your infinite program would similarly have to follow a finite specification, where your if statement would be back, or the TM with its infinite tape.

If you forget this constraint, then you drastically change the domain of discourse, as you get a continuous (rather than denumerable) infinity of different programs. You are no longer talking of computability with its accepted meaning, and its physical realizability. Actually, I suspect that you can then no longer consider a concept that would ressemble computability (but that is a somewhat fuzzy statement).

Your construction seems a bit tautological. The if statement is itself a form or branching through an array of two addresses, depending on a value that is 0 or 1. Actually, the if statement generalizes to the case statement, which may be implemented as branching through an array. Whether the array is code or static data is immaterial and pretty much in the eyes of the beholder.

Another way to state this is that your program could be simulated by a Turing machine, which does not have any if statement, and could thus be a positive answer to your question.

Indeed, a Turing machine should be as good an answer as any other state machine. Compared to a FSA, the only difference is that it can read and write on an infinite tape.

So, if you do not accept the Turing machine as an answer, I wonder whether your problem is not more with eliminating this infinite memory tape, at the expense of replacing it with an infinite program (TM states and transitions).

Then, I am afraid you may just fall into something similar to a Turing Tar Pit, or much worse (a Turing hell?).

The main point is that the technique you are proposing will require your program to have an infinite size, if it is to be equivalent to the original program, using infinite matrices, i.e. really an infinite number of states.

You might not worrry about it, considering that we already work as if we could use unbounded integer in memory. That is true, but we use integer in a very precise way, that is finitely described. As a consequence, it is perfectly possible to mimic computation with arbitrary long integer, and it is actually done in some systems.

One fundamental principle of computer science (and I would add mathematics, but that has to be made precise) is that everything must be finitely definable.

To make any sense, your infinite program would similarly have to follow a finite specification, where your if statement would be back, or the TM with its infinite tape.

If you forget this constraint, then you drastically change the domain of discourse, as you get a continuous (rather than denumerable) infinity of different programs. You are no longer talking of computability with its accepted meaning, and its physical realizability. Actually, I suspect that you can then no longer consider a concept that would ressemble computability (but that is a somewhat fuzzy statement).

1
source | link

Your construction seems a bit tautological. The if statement is itself a form or branching through an array of two addresses, depending on a value that is 0 or 1. Actually, the if statement generalizes to the case statement, which may be implemented as branching through an array. Whether the array is code or static data is immaterial and pretty much in the eyes of the beholder.

Another way to state this is that your program could be simulated by a Turing machine, which does not have an if statement, any more that a FSA has if statements. What the TM has, that the FSA does not, is an infinite tape on which it can read and write.

So, I am wondering whether your problem is not more with eliminating this infinite memory tape, at the expense of replacing it with an infinite program (states and transitions).

Then, I am afraid you just fall into something similar to a Turing Tar Pit, or much worse (a Turing hell ?).

The main point is that the technique you are proposing will require your program to have an infinite size, if it is to be equivalent to the original program, using infinite matrices, i.e. really an infinite number of states.

You might not worrry about it, considering that we already work as if we could use unbounded integer in memory. That is true, but we use integer in a very precise way, that is finitely described. As a consequence, it is perfectly possible to mimic computation with arbitrary long integer, and it is actually done in some systems.

One fundamental principle of computer science (and I would add mathematics, but that has to be made precise) is that everything must be finitely definable.

To make any sense, your infinite program would similarly have to follow a finite specification, where your if statement would be back, or the TM with its infinite tape.

If you forget this constraint, then you drastically change the domain of discourse, as you get a continuous (rather than denumerable) infinity of different programs. You are no longer talking of computability with its accepted meaning, and its physical realizability. Actually, I suspect that you can then no longer consider a concept that would ressemble computability (but that is a somewhat fuzzy statement).