|
12
|
1 2010-12-12.txt:02:21:54: <Vorpal> elliott, "In spring of this year on the IRC channel I proposed a language called ℒ. ℒ is a severely restricted subset of your favourite indisputably Turing-complete language (say, Pascal) -- so severely restricted, in fact, that you can only write a single program in ℒ. But that program is a Universal Turing Machine simulator. Is ℒ Turing-complete? "
|
|
|
2 2011-07-08.txt:03:55:05: <elliott> Well... you only need two nested loops to implement BF in BF, and they're of finite, short length, but this is the ℒ debacle all over again.
|
|
|
3 2011-10-15.txt:18:30:37: <elliott> You can compile any TC language to any other TC language (modulo ℒ).
|
|
|
4 2011-10-15.txt:18:37:59: <elliott> <elliott> You can compile any TC language to any other TC language (modulo ℒ).
|
|
|
5 2011-10-15.txt:18:42:15: <Phantom___Hoover> <elliott> <elliott> You can compile any TC language to any other TC language (modulo ℒ).
|
|
|
6 2011-10-15.txt:18:42:33: <Phantom___Hoover> It's not just modulo ℒ, it's modulo which definition you use.
|
|
|
7 2011-10-15.txt:18:42:47: <elliott> Phantom___Hoover: I don't think anyone seriously believes ℒ is TC.
|
|
|
8 2011-10-15.txt:18:43:00: <elliott> Phantom___Hoover: Anyway, ℒ relies on input.
|
|
|
9 2011-10-15.txt:18:43:09: <Phantom___Hoover> You're using the compilation definition; ℒ is designed to flag up the absurdity of the UTM definition.
|
|
|
10 2011-10-15.txt:18:43:34: <elliott> If you embed the input into the program, then... congratulations, ℒ is a Brainfuck derivative where you have to escape the string according to Pascal's rule.
|
|
|
11 2011-10-15.txt:18:44:00: <elliott> Phantom___Hoover: So no, ℒ only demonstrates the absurdity of naively mixing input into the definition.
|
|
|
12 2011-10-15.txt:18:44:31: <elliott> Phantom___Hoover: The whole point of ℒ is that it contains a program that can be made to compute anything a UTM can /given the appropriate input/.
|
|
|
13 2011-10-15.txt:18:45:07: <elliott> Phantom___Hoover: Define ℒ for me.
|
|
|
14 2011-10-15.txt:18:45:24: <Phantom___Hoover> For every pair of a Turing-complete language L and a program P written in L that simulates a universal Turing machine (for example, by being an interpreter for a Turing-complete language) (L,P) is a member of ℒ.
|
|
|
15 2011-10-15.txt:18:48:30: <elliott> Phantom___Hoover: The UTM definition doesn't include any notion of input, so how the fuck does ℒ show it absurd?
|
|
|
16 2012-02-22.txt:19:46:11: <elliott> And call it ℒ.
|
|
|
17 2012-02-22.txt:19:46:32: <elliott> So it's ℒ(Pascal,BF interpreter) you have to prove Turing whatever.
|
|
|
18 2012-02-23.txt:03:22:32: <tswett> How come ℒ is in Unicode but a plain old italic L isn't?
|
|
|
19 2012-02-23.txt:18:20:19: <Friendship> Given that the computational class of ℒ is unclear, but there are languages which are plainly within its computational class, we can create a new (and intentionally ambiguous) computational class to describe it. ℒ-equivalent machines are those abstract machines for which the ability to describe all universal Turing machines is predicated upon the status of input or some other state which may be considered external to the machine proper. The set of ℒ-equ
|
|
|
20 2012-02-23.txt:18:20:19: <Friendship> ivalent machines is clearly a subset of [[Turing machines]], but whether it is a proper subset is a matter of philosophy. A language is said to be ℒ-hard if there exists a program in that language which is in ℒ, and ℒ-complete if it is ℒ-hard and not [[Turing-complete]].
|
|
|
21 2012-02-23.txt:18:27:04: <elliott> @tell Gregor "ℒ was originally described to generalize the question raised by Befunge/index.php." not quite true
|
|
|
22 2012-02-23.txt:18:29:07: <Friendship> `pastelogs ℒ
|
