3 ms·

> 3x+1 is, too, a programming language What does this mean? Isn't having a catalog essentially precomputing a function for every possible input?

jay_kyburz 5y ago
3x+1 produces binary, up or down, so perhaps the integers are shortcuts or an index to any binary sequence. The termination of the sequence is 4,2,1
romwell 5y ago
>What does this mean? A 3x + 1 program is a positive integer N. "Running" this program would be iterating 3x + 1 until it gets stuck in a loop (this would be the "halting condition"). The "output" would be a fixed function of the numbers in the loop (e.g. the loop itself; like 4, 2, 1). As far as we know, all "programs" in 3x + 1 output 4, 2, 1. This makes for a very boring language (essentially, one you can only make "Hello World!" in). But we don't have a proof that that's all there is to it. >Isn't having a catalog essentially precomputing a function for every possible input? Specifically, that means that given a Turing machine T and input X, we can compute a number N = N(T, X) such that the "output" of running our "language" on N is the same as the output of T on X. Which is what they do in FRACTRAN: they show how to encode an arbitrary program and its input as a number N, and how to read the output from the iteration.
- teruakohatu 5y ago
  > Which is what they do in FRACTRAN: they show how to encode an arbitrary program and its input as a number N, and how to read the output from the iteration. What I don't understand is the encoding part. Is the encoding not essentially the same as execution? In other words the encoding function needs to be turning complete? T(X) = N(E(T, X))
  - romwell 5y ago
    Encoding is not the same as execution because you only encode the program and its input. You don't know what the output is unless you execute it on the FRACTRAN machine; the thing that gets you the output is execution. Note that execution is not a function that gives a finite output, as some programs never halt, or never return an output at all. So while you can always encode, you don't always get an output from that encoding (like in cases where the Turing machine never halts). TL;DR: encoding is a function (finite #of bits -> finite #of bits). Execution is a function (finite #of bits -> ???), where ??? can be a finite or infinite sequence, or an empty set, and there is no way to tell which it is other than executing, which may take infinite time (see: Halting problem).
- natmaka 5y ago
  Why, adding an accumulator, can't the "output" be the number of steps before reaching 1?
  - romwell 5y ago
    Yes, it can be, lack of imagination on my part. As others pointed out, though, if it always gets stuck in a 4-2-1 loop, that would mean that every "program" terminates, which would imply that the language isn't Turing-complete.

jay_kyburz 5y ago

3x+1 produces binary, up or down, so perhaps the integers are shortcuts or an index to any binary sequence. The termination of the sequence is 4,2,1

romwell 5y ago

>What does this mean? A 3x + 1 program is a positive integer N. "Running" this program would be iterating 3x + 1 until it gets stuck in a loop (this would be the "halting condition"). The "output" would be a fixed function of the numbers in the loop (e.g. the loop itself; like 4, 2, 1). As far as we know, all "programs" in 3x + 1 output 4, 2, 1. This makes for a very boring language (essentially, one you can only make "Hello World!" in). But we don't have a proof that that's all there is to it. >Isn't having a catalog essentially precomputing a function for every possible input? Specifically, that means that given a Turing machine T and input X, we can compute a number N = N(T, X) such that the "output" of running our "language" on N is the same as the output of T on X. Which is what they do in FRACTRAN: they show how to encode an arbitrary program and its input as a number N, and how to read the output from the iteration.

teruakohatu 5y ago
> Which is what they do in FRACTRAN: they show how to encode an arbitrary program and its input as a number N, and how to read the output from the iteration. What I don't understand is the encoding part. Is the encoding not essentially the same as execution? In other words the encoding function needs to be turning complete? T(X) = N(E(T, X))
- romwell 5y ago
  Encoding is not the same as execution because you only encode the program and its input. You don't know what the output is unless you execute it on the FRACTRAN machine; the thing that gets you the output is execution. Note that execution is not a function that gives a finite output, as some programs never halt, or never return an output at all. So while you can always encode, you don't always get an output from that encoding (like in cases where the Turing machine never halts). TL;DR: encoding is a function (finite #of bits -> finite #of bits). Execution is a function (finite #of bits -> ???), where ??? can be a finite or infinite sequence, or an empty set, and there is no way to tell which it is other than executing, which may take infinite time (see: Halting problem).
natmaka 5y ago
Why, adding an accumulator, can't the "output" be the number of steps before reaching 1?
- romwell 5y ago
  Yes, it can be, lack of imagination on my part. As others pointed out, though, if it always gets stuck in a 4-2-1 loop, that would mean that every "program" terminates, which would imply that the language isn't Turing-complete.