Talk:Volatile

From Esolang
Jump to navigation Jump to search

Possibly Turing-complete?

There is a way to push 1, ~:/ (well, a non-deterministic way, but the chance for it to fail is very low in practice), and so there is a way to build arbitrary constants. Then, we can also add, subtract, multiply and divide numbers, and loop while the top of stack is not 0. If it is possible to build an algorithm to check divisibility, and if stack elements are unbounded, it could be possible to build a theoretically infinite number of counters in only one stack element (by multiplying and dividing primes), proving Turing-completeness by reduction from a Minsky machine. TuxCrafting (talk) 18:05, 25 May 2019 (UTC)

I correct you on the number of stack elements. If only 1 stack element is allowed, numbers cannot be pushed. At least 3 elements are neccesary (the bottom is the counters, and the top two is used for representing numbers.) --A (talk) 03:25, 26 May 2019 (UTC)
By one stack element, I mean it is possible to store a lot of things in only one. Of course operations would require more than that. TuxCrafting (talk) 04:24, 26 May 2019 (UTC)
Also, Volatile can only be Turing complete that way iff a remainder algorithm exists, which hasn't been shown yet. Its Turing completeness is only hypothetical still. TuxCrafting (talk) 04:29, 26 May 2019 (UTC)
Although Turing-completeness is still in question, it is at least a PDA. I will partially revert your edit.--A (talk) 04:44, 26 May 2019 (UTC)
The remainder algorithm will be easy. x mod y will be equivalent to x - (x / y). (untested) --A (talk) 04:47, 26 May 2019 (UTC)
Oh, yeah, :N/N*- to get the remainder by a constant. TuxCrafting (talk) 04:53, 26 May 2019 (UTC)
Sorry about that, I've tested the algorithm and it is wrong. I have problems on it. --A (talk) 05:22, 26 May 2019 (UTC)
The correct algorithm is: x-(y*(x//y)); it seems fine in Python. --A (talk) 05:24, 26 May 2019 (UTC)

(Untested) 

- start with -- ~:/
- (where P(n) is the n-th prime)
- increment n-th counter -- P(n)*
- decrement n-th counter -- P(n)/
- loop while n-th counter is 0 -- ::P(n)/P(n)*-(:-+[body here]::P(n)/P(n)*-):-+

TuxCrafting (talk) 05:03, 26 May 2019 (UTC)

~(:/~:-)+ doesn't improve on ~:/ other than by making it crash in a different maneer if ~ returns 0. TuxCrafting (talk) 05:31, 26 May 2019 (UTC)
You are right. ~:-(:/~:-)+. makes the whole thing crash. --A (talk) 06:07, 26 May 2019 (UTC)

Here is a compiler from a language similar to Portable Minsky Machine Notation to Volatile. This therefore proves that Volatile is turing complete as long as ~ isn't a **** and pushes 0. (Not sure if 'failing sometimes' is acceptable for Turing completeness, but oh well.) 

primes = [2, 3]

def get_prime(n):
	if n < len(primes):
		return primes[n]
	l = len(primes)
	p = primes[l - 1]
	i = l - 1
	n -= l - 1
	while n:
		while 1:
			p += 2
			pr = 1
			for x in primes:
				if p % x == 0:
					pr = 0
					break
			if pr:
				break
		primes.append(p)
		i += 1
		n -= 1
	return p

def push_n(n):
	return "~:*~:*+:/" + ":" * (n - 1) + "+" * (n - 1)

def push_p(n):
	return push_n(get_prime(n))

def mod(n):
	return "::" + push_p(n) + "/" + push_p(n) + "*-"

def conv(l):
	s = ""
	for x in l:
		if x[0] == "INC":
			s += push_p(x[1]) + "*"
		elif x[0] == "DEC":
			s += push_p(x[1]) + "/"
		elif x[0] == "WHILE0":
			s += mod(x[1]) + "(:-+"
			s += conv(x[2])
			s += mod(x[1]) + "):-+"
		elif x[0] == "IF0":
			s += mod(x[1]) + "(:-+"
			s += conv(x[2])
			s += "~:-):-+"
		elif x[0] == "OUT":
			s += "."
	return s

def max_r(l):
	n = -1
	for x in l:
		if x[0] == "inc" or \
		   x[0] == "dec":
			n = max(n, x[1])
		elif x[0] == "while-dec":
			n = max(n, x[1])
			n = max(n, max_r(x[2]))
		elif x[0] == "if-dec":
			n = max(n, x[1])
			n = max(n, max_r(x[2]))
			if len(x) > 3:
				n = max(n, max_r(x[3]))
	return n

def _minsky(l, sysb):
	intr = []
	for x in l:
		if x[0] == "inc":
			intr.append(("INC", x[1]))
		elif x[0] == "dec":
			intr.append(("DEC", x[1]))
		elif x[0] == "out":
			intr.append(("OUT",))
		elif x[0] == "while-dec":
			intr += [
				("WHILE0", sysb, [
					("IF0", x[1], [
						("INC", sysb),
					]),
					("IF0", sysb, [
						("DEC", x[1]),
						*_minsky(x[2], sysb + 1),
					]),
				]),
				("DEC", sysb),
			]
		elif x[0] == "if-dec":
			intr += [
				("IF0", x[1], [
					("INC", sysb),
					*(
						[]
						if len(x) < 4
						else
						_minsky(x[3], sysb + 1)
					),
				]),
				("IF0", sysb, [
					("DEC", x[1]),
					*_minsky(x[2], sysb + 1),
					("INC", sysb),
				]),
				("DEC", sysb),
			]
	return intr

def minsky(l):
	return _minsky(l, max_r(l) + 1)

prg = [
	("inc", 0),

	("if-dec", 0, [
		("inc", 0),
	], [
		("if-dec", 1, [
			("inc", 2),
		]),
		("inc", 1),
	]),

	("out",),
]

print(push_n(0) + conv(minsky(prg)))

TuxCrafting (talk) 12:59, 26 May 2019 (UTC)

So, as for *how* it works: First, the Minsky machine code is compiled into an intermediate representation. This is mostly just simple substitutions: 

("inc", reg) -> ("INC", reg)

("dec", reg) -> ("DEC", reg)

("out",) -> ("OUT",)

("while-dec", reg, body) ->
("WHILE0", sysb, [
  ("IF0", reg, [
    ("INC", sysb)
  ])
  ("IF0", sysb, [
    ("DEC", reg)
    body
  ])
])
("DEC", sysb)

("if-dec", reg, if-body) ->
("IF0", reg, [
  ("INC", sysb)
])
("IF0", sysb, [
  ("DEC", reg)
  if-body
  ("INC", sysb)
])
("DEC", sysb)

("if-dec", reg, if-body, else-body) ->
("IF0", reg, [
  ("INC", sysb)
  else-body
])
("IF0", sysb, [
  ("DEC", reg)
  if-body
  ("INC", sysb)
])
("DEC", sysb)

The sysb placeholder indicates a register unique to the nesting level, which is normally nesting_level + max_register_number.

This intermediate representation is then directly translated into Volatile: 

("INC", reg) -> P(reg)*
("DEC", reg) -> P(reg)/
("OUT",) -> .
("WHILE0", reg, body) -> ::P(reg)/P(reg)*-(:-+body::P(reg)/P(reg)*-):-+
("IF0", reg, body) -> ::P(reg)/P(reg)*-(:-+body~:-):-+

Where P(n) pushes the n-th prime number (P(0)=2). In the Python compiler, numbers are pushed with ~:*~:*+:/[n-1 times ':'][n-1 times '+'].

The translated code must start with the value '1' pushed on the stack.

This should be enough to translate any Minsky machine into Volatile. TuxCrafting (talk) 13:16, 26 May 2019 (UTC)

This turing-completeness proof still seems to rely on a modulo trick that assumes that / performs floor division despite no indication that this is the case. DigitalDetective47 (talk) 21:16, 25 June 2023 (UTC)

Provided interpreter

The provided interpreter has a few problems: for example, it does not support nested loops, or arbitrary precision numbers. TuxCrafting (talk) 05:35, 26 May 2019 (UTC)

The implementation is not written by me; contact Helen to fix it. (They wrote this implementation). --A (talk) 05:49, 26 May 2019 (UTC)

Output Methods

Quick question: is it okay if the interpreter/compiler prints values as ASCII characters where possible? E.g. If the item to be printed was, say 72, is it permissable to print it as the letter "H"? --JonoCode9374 (talk) 08:14, 26 May 2019 (UTC)

It is acceptible, as long as the implementation does not do that as an extra instruction(as that will not conform the documentation). --A (talk) 08:39, 26 May 2019 (UTC)
Nice. I'll change my interpreter now --JonoCode9374 (talk) 09:24, 26 May 2019 (UTC)

Pushing 1

The current methods of pushing 1 fail if ~ returns 0, which has a reasonable chance of happening in long-running programs. So, there has to be a way to ensure ~ doesn't return 0; however, there is no way of looping on 0 without having access to 1, meaning that pushing 1 with a 100% probability is impossible. But, it is possible to have the error rate of pushing 1 get arbitrarly low, by chaining ~:*'s and adding the results together (the result of ~ is squared to ensure the number is always positive); this way, the error rate, assuming all numbers are chosen uniformly, becomes 1/(R^n), where R is the number of possibilities that ~ can return, and n is the number of repetitions of the snippet. So for example, if an interpreter returns an uniformly random 32-bit signed number, ~:*~:*+~:*+~:*+:/ would give an error with a probability of 1/(2^128), which is unlikely to happen in the lifetime of the universe. TuxCrafting (talk) 08:45, 26 May 2019 (UTC)

Reducing the Command Set

I noticed there has been mentions of reducing the number of commands in the command set. My idea is that you could easily remove the * command. But also, perhaps a bitshift command could be added to the language (In order to keep inspiration from Keg, I'd have to add a bitshift command to both the specs and the interpreter of course.) - this would replace the + command and potentially other commands. Just a thought. --JonoCode9374 (talk) 06:04, 27 May 2019 (UTC)

Pushing 1 deterministically is impossible.

If the ~ operator always possible to return 0, the pushing 1 deterministically is impossible. If the stack contents are initially nothing or all zeroes (NOAZ) and the ~ always returns 0 (the worst case), then: 

~: Will push zero
+: Will pop zero as long as there is at least one item at stack, otherwise undefined behavior.
-: Will pop zero as long as there is at least one item at stack, otherwise undefined behavior.
*: Will pop zero as long as there is at least one item at stack, otherwise undefined behavior.
/: Results in error
:: Will push zero
.: Will output zero
(...): Is a no-op.

So no matter what the program, if the stack is NOAZ, and ~ always returns 0, the stack contents will always be NOAZ all the way through the program.Akangka (talk) 13:14, 1 October 2019 (UTC)

Great proof, the only problem of this is that this had already been proven before. àÂse ëË y± comme×s! (Please sign your comments!) A (taÑ) 02:16, 3 August 2019 (UTC) 15:57, 1 October 2019 (UTC)
Retrieved from "https://esolangs.org/w/index.php?title=Talk:Volatile&oldid=110723"